数据结构课件-排序.ppt
第10章 排序一、基本概念排序：将文件中的记录按照关键字值递增或递减的顺序排列起来。排序的稳定与不稳定：若关键字相同的记录在排序后先后顺序仍然不变，则称所用的排序方法是稳定的，否则就是不稳定的。内部排序：全部在内存中进行的排序外部排序：排序中需使用内存与外存内部排序：插入排序，交换排序，选择排序，归并排序，基数排序等。,内部排序与存储结构：（1）一维数组作为存储结构：对记录进行物理重排；（2）以链表作为存储结构：无须移动记录，仅需修改指针即可；（3）建立索引表辅助排序排序算法的评价标准：（1）时间；（2）执行算法所需的附加空间；（3）算法复杂度。主要是时间代价：算法的比较次数和移动次数。注：简单的排序方法，时间复杂度O(n2);先进的排序方法，时间复杂度O(nlogn)；基数排序，时间复杂度O(dn)。,以数组作为文件的存储结构#define MAXSIZE 100 typedef struct KeyType key;InfoType otherinfo;RecType;typedef struct RecType rMAXSIZE+1;/r0闲置或作为哨兵单元 int length;SqList;如：以某课程考试成绩为关键字的排序,二、插入排序(Insertion Sort)定义：将待排序记录分为有序区和无序区，每次将无序区中的第一个记录按其关键字值的大小插入到有序区中的适当位置，直到无序区记录全部插入为止。1 直接插入排序方法：在插入第i个记录时，R1,R2,，Ri-1已排好序，将关键字ki依次与关键字ki-1,ki-2,k1进行比较，从而找到应该插入的位置，然后将记录Ri插入。,对R1Rn进行排序，R0为监视哨,47 33 61 82 72 11 25 47 47 33 61 82 72 11 25 47 33 33 47 61 82 72 11 25 47/334733 33 47 61 82 72 11 25 4733 33 47 61 82 72 11 25 4772 33 47 61 72 82 11 25 4711 33 47 61 72 8282 25 47/1182 11 33 47 61 7272 82 25 47/117211 33 47 6161 72 82 25 47/1161 11 33 4747 61 72 82 25 47/114711 3333 47 61 72 82 25 47/113311 11 33 47 61 72 82 25 47/结束11的插入排序25 11 25 33 47 61 72 82 47/47 11 25 33 47 47 61 72 82,中间过程,算法：void InsertSort(SqList/插入到正确位置,时间复杂度O(n2)，稳定,2、希尔排序（Shells method）“缩小增量排序”(Diminishing Increment Sort)基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。步骤：对整个待排记录序列，按间隔d1分组，组内排序取d2 d1（缩小增量），继续以d2为距离排序直到dn=1（同直接插入排序）为止,47 33 61 82 72 11 25 47 57 02 d=5,11 25 47 57 02 47 33 61 82 72,11 25 47 57 02 47 33 61 82 72 d=3,11 02 47 33 25 47 57 61 82 72,02 11 25 33 47 47 57 61 72 82 d=1,记录分组：某一趟希尔排序的增量为d，文件分为d组：(R1,Rd+1,R2d+1,),(R2,Rd+2,R2d+2,),，(Rd,R2d,R3d,)确定Ri属于哪一组？Ri必然和Ri-d*m（i-d*m0）、Ri+d*m(i+d*m=n)同组,void ShellInsert(SqList,性能分析：,逆转数：在关键字前面比此关键字大的关键字个数关键字 47 33 61 82 72 11 25 47 57 02 逆转数 0 1 0 0 1 5 5 3 3 9总逆转数=0+1+0+0+1+5+5+3+3+3+9=30d=5：11 25 47 57 02 47 33 61 82 72 逆转数 0 0 0 0 4 1 3 0 0 1总逆转数=0+0+0+0+4+1+3+0+0+1=9d=3：11 02 47 33 25 47 57 61 82 72 逆转数 0 1 0 1 2 0 0 0 0 1总逆转数=0+1+0+1+2+0+0+0+0+1=5,当d=1时，逆转数=0当d=1时，同直接插入，是否比直接插入快？直接插入排序，一次比较移动只减少一个逆转数希尔排序，一次比较移动减少逆转数可能147 33 61 82 72 11若中间数介于47 和11之间，必然减少逆转数,不稳定,三、选择排序（Selection Sort）基本思想：每一趟在待排序的记录中选出关键字最小的记录，依次放在已排序的记录序列的最后，直至全部记录排完为止。,1.简单选择排序 第一趟排序：在无序区R1Rn中选出关键字最小的记录，将它与R1交换；第二趟排序：在无序区R2Rn中选出关键字最小的记录，将它与R2交换；第i趟排序：R1Ri-1已是有序区，在当前无序区RiRn中选出关键字最小的记录Rk，将它与Ri交换；进行n-1趟排序后，整个文件就是递增有序的。,49 38 65 97 76 13 27 49,13 38 65 97 76 49 27 49,13 27 65 97 76 49 38 49,13 27 38 97 76 49 65 49,13 27 38 49 76 97 65 49,13 27 38 49 49 97 65 76,13 27 38 49 49 65 97 76,13 27 38 49 49 65 76 97,13 27 38 49 49 65 76 97,算法流程：1 for i=1 to n-1 j=i for k=i+1 to n if(RjRk)then j=k end(k)if(ji)then ri与rj互换End(i)return,void SelectSort(SqList,时间复杂度O(n2)，稳定,2.堆排序,堆：n个元素的序列k1,k2,kn，当且仅当满足以下关系时，称之为堆。,时间复杂度O(nlogn)，不稳定,把堆看作一棵完全二叉树，所有非终端结点的值均不大于（或不少于）其左右孩子结点的值。堆顶元素是堆序列的最小值（最大值）,堆排序：输出堆顶最小值（最大值）后，使得剩余的元素序列重又建成一个堆，得到次小值（次大值）。如此反复执行得到一个有序序列的过程。堆排序步骤：1.从无序序列构建初始堆 2.反复筛选输出有序序列 第1步其实也是一个反复筛选的过程，因此筛选是堆排序的关键,筛选过程,构建初始堆,四、交换排序基本思想：两两比较待排序记录的关键字，发现两个记录逆序时即进行交换，直至没有逆序的记录为止。,1 起泡排序（Bubble method）基本思想：通过对相邻关键字的比较和交换，使全部记录排列有序。过程：每两个相邻的关键字进行比较，若为逆序，则将两记录交换位置，反复进行这一操作。如此一趟排序后，可将关键字最大的记录安排在最后一个记录的位置上，然后对前n-1个记录重复同样操作，再将次小关键字安排再倒数第二个记录的位置上。重复进行，直至某一趟没有记录交换完成排序。,4733618272112547,3347617211254782,3347611125477282,3347112547617282,3311254747617282,1125334747617282,1125334747617282,1125334747617282,1125334747617282,设置指示变量，以判断每次扫描时是否有记录交换,void BubbleSort(SqList,时间复杂度O(n2)，稳定,2 快速排序（Quick Sort）基本思想：通过一趟排序将原有记录分成两部分，然后分别对这两部分进行排序以达到最后所有记录有序。即在当前无序子区R1Rh中任取一个记录作为比较的基准，用此基准将当前无序区划分为左右两个较小的无序子区：R1Ri-1和Ri+1Rh，左边无序子区记录关键字均小于或等于基准关键字，右边则大于或等于基准关键字。反复进行，直至无序子区记录已排好序为止。,对当前无序子区R1Rh进行划分的方法：设置两个指示器i和j，它们的初值分别为：i=1,j=h。设基准temp为无序子区中的第一个记录Ri(即R1)。将j自h起向左扫描，直至找到第一个关键字小于temp.key的记录Rj，将Rj移至i所指的位置上；然后，令i自i+1起向右扫描，直至找到第一个关键字大于temp.key的记录Ri，将Ri移至j所指的位置上；接着令j自j-1起向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至i=j时，i便是基准x的最终位置，将x放在此位置上就完成了一次划分。,O(nlogn)，不稳定,49 38 65 97 76 13 27 49,i,j,49 38 65 97 76 13 27 49,i,j,27 38 65 97 76 13 49 49,i,j,27 38 65 97 76 13 49 49,i,j,27 38 49 97 76 13 65 49,i,j,49 38 65 97 76 13 27 49,i,j,49 38 65 97 76 13 27 49,i,j,27 38 65 97 76 13 49,i,j,27 38 65 97 76 13 49,i,j,27 38 97 76 13 65 49,i,j,/一趟快速排序int partition(SqList,/快速排序void QSort(SqList,五、归并排序（Merge Sort）归并：将两个或两个以上有序表合成一个新有序表。二路归并排序：将初始表的n个记录看成n个有序的子表（长度为1），然后两两合并，得到n/2个长度为2或1的有序子表，再两两合并，如此反复，直至得到一个长度为n的有序子表为止。算法实现：设RlowRm和Rm+1Rhigh是两个有序子文件，R1lowR1high为合并的目标文件，设置三个指示器i,j和k，初值分别为这三个记录区的起始位置。合并时依次比较Ri和Rj的关键字，取关键字较小的记录复制到R1k中，将指向被复制记录的指示器和指向复制位置的指示器k加1，重复进行，直至全部记录被复制到目标文件。,49 38 65 97 76 13 27 49,49 38 65 97 76 13 27 49,38 49 65 97 13 76 27 4938 49 65 97 13 27 49 7613 27 38 49 49 65 76 97,O(nlogn)，稳定,六、基数排序（Radix Sorting）基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法，其中单逻辑关键字可以分解为多个关键字。多关键字排序:以扑克牌排序为例，假设花色是黑红梅方，然后是点数，按13个点数 的自然数顺序排序，另外假设花色优先级比点数高 排序有两种方式：1.先花色，再点数（最高位优先MSD）2.先点数，再花色（最低位优先LSD）,链式基数排序是借助分配和收集两种操作使用链表作为组织结构对单逻辑关键字进行排序的方法。,各种排序方法的比较（10.7）,本节重点：1 各种排序算法的原理与实现2 各种排序算法特点及相互比较,作业1,任选2种排序算法，对单链表元素进行现场排序。,作业2,引入“三者取中”，“冒泡排序”对快速排序算法进行改进,
