数据结构-清华大学-殷人昆-07

第7章排序清华大学计算机系殷人昆数据结构课件第七章排序从来处来往去处去次序之美美在规矩利在行方159-2概述插入排序交换排序选择排序归并排序表排序基数排序各种内排序方法的比较外排序第7章排序159-3概述排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(datalist):它是待排序数据记录的有限集合。排序码(key):通常数据记录有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分记录,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。本章所涉及排序码的值允许重复。159-4排序算法的稳定性:如果在记录序列中有两个记录r[i]和r[j],它们的排序码值k[i]==k[j],且在排序之前,记录r[i]排在r[j]前面。如果在排序之后,记录r[i]仍在记录r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。内排序与外排序内排序是指在排序期间数据记录全部存放在内存的排序；外排序是指在排序期间全部记录个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。159-5排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。内排序的时间开销可用算法执行中的排序码比较次数与数据移动次数来衡量；外排序的时间开销要看读写外存的次数。算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受记录排序码序列初始排列及记录个数影响较大的，需要按最好情况和最坏情况分别进行估算。算法执行时所需的附加存储:评价算法好坏的另一标准。159-6从排序过程中数据的总体变化趋势来看，排序方法的处理可以分为两大类。(1)有序区增长：将数据表分成有序区和无序区，在排序过程中逐步扩大有序区，缩短无序区，直到有序区扩大到整个数据表为止。如插入排序、选择排序、起泡排序、堆排序、归并排序等。(2)有序程度增长：数据表不能明确区分有序区和无序区，随着排序过程的执行，逐步调整表中元素的排列，使得表中的有序程度不断提高，直到完全有序。如快速排序、希尔排序、基数排序等。159-7待排序数据表的结构定义constintDefaultSize=100;typedefintDataType;typedefstructElement{//表元素定义DataTypekey;//排序码otherdata;//其他数据成员};typedefstructdataList{//数据表定义Elementelem[DefaultSize];//存储数组intn;//当前元素个数}159-8插入排序(InsertSorting)基本方法是：每步将一个待排序的记录，按其排序码值的大小，插入到前面已经排好序的一组记录的适当位置上,直到记录全部插入为止。直接插入排序的基本思想是：当插入第i(i＞0)个记录时，前面的elem[0],elem[1],…,elem[i-1]已经排好序。这时，用elem[i]的排序码与elem[i-1],elem[i-2],…的排序码顺序比较，找到插入位置即将elem[i]插入,原来位置上的记录向后顺移。直接插入排序(InsertSort)159-9各趟排序结果i=1012345672125491608523725*012345672125491608523725*012345672125491608523725*i=22521，无需移动4925，无需移动159-10i=301234567temp21251608523725*01234567temp16085237i=401234567temp085237i=54925*49，49…后移4925*25211649，49…后移0849，49…后移4925*252116159-1101234567temp25081625*49523721i=601234567temp25081625*523721i=752494901234567temp37495225081625*21375252,49后移结果159-12直接插入排序的算法voidInsertSort(dataList&L){Elementw;inti,j;for(i=1;iL.n;i++)//插入n-1趟if(L.elem[i].keyL.elem[i-1].key){w=L.elem[i];L.elem[i]=L.elem[i-1];for(j=i-1;j0;j--)//从后向前比较if(w.keyL.elem[j-1].key)//比j-1元素小L.elem[j]=L.elem[j-1];//让j-1元素后移elsebreak;L.elem[j]=w;}}159-13算法分析设待排序记录个数为n，则该算法的主程序执行n-1趟。排序码比较次数和记录移动次数与记录排序码的初始排列有关。最好情况下,排序前记录已按排序码的值从小到大有序，每趟只需与前面有序记录序列的最后一个记录比较1次，移动0次记录，总的排序码比较次数为n-1,记录移动次数为0。最坏情况下，第i趟时第i个记录必须与前面i个记录都做排序码比较，并且每做1次比较就要做1次数据移动。159-14因此，在最坏情况下，总排序码比较次数KCN和记录移动次数RMN分别为在平均情况下的排序码比较次数和记录移动次数约为n2/4。因此，直接插入排序的时间复杂度为O(n2)。直接插入排序是一种稳定的排序方法。直接插入排序需要一个附加记录暂存待插记录。1n1i21n1i2/2n1)/24)(n(n2)(iRMN/2,n1)/2n(niKCN159-15折半插入排序(BinaryInsertsort)折半插入排序的基本思想是:设在顺序表中有一个记录序列elem[0],elem[1],…,elem[n-1]。其中,elem[0],elem[1],…,elem[i-1]是已经排序的数据记录。在插入elem[i]时，不是利用顺序查找从后向前寻找插入位置，而是利用折半查找法寻找elem[i]的插入位置。voidBinaryInsSort(dataList&L){Elementw;inti,k,left,right,mid;for(i=1;iL.n;i++){折半插入排序的算法159-16left=0;right=i-1;w=L.elem[i];while(left=right){//在elem[0..i-1]内寻找elem[i]插入位置mid=(left+right)/2;//中间位置if(w.keyL.elem[mid].key)//小于中点值right=mid-1;//左缩区间elseleft=mid+1;//右缩区间}for(k=i-1;k=left;k--)L.elem[k+1]=L.elem[k];//空出left位置L.elem[left]=w;}//for}159-17折半搜索比顺序搜索查找快,所以折半插入排序就平均性能来说比直接插入排序要快。它所需的排序码比较次数与待排序记录序列的初始排列无关,仅依赖于记录个数。在插入第i个记录时,需要经过log2i+1次排序码比较,才能确定它应插入的位置。因此，将n个记录元素（为推导方便,设为n=2k，k=log2n），折半插入排序所进行的排序码比较次数为：算法分析159-18这是折半查找算法分析得到的结果。折半查找的时间复杂度为O(nlog2n)，这是指排序码比较次数的时间开销，但记录移动次数就不同了。折半插入排序的记录移动次数比直接插入排序多一点，依赖于记录元素的初始排列。折半插入排序是一个稳定的排序方法。折半插入排序需要一个附加记录暂存待插记录。1k21021n1i2222kkk332211)ilog(1nnlog*n11)n(log*n12*1)(k2*k2*32*22*122k1k210--159-19希尔排序(ShellSort)希尔排序方法又称为缩小增量排序。该方法的基本思想是:设待排序记录序列有n个记录,首先取一个整数gapn作为间隔,将全部记录分为gap个子序列,所有距离为gap的记录放在同一个子序列中,在每一个子序列中分别施行直接插入排序。然后缩小间隔gap,例如取gap=gap/2，重复上述的子序列划分和排序工作。直到最后取gap=1,将所有记录放在同一个序列中排序为止。159-20i=1gap=4160123456721254925*0837521621254925*0837521621254925*0837521621.21后移16210825.25后移0825159-21160123456721254925*0837521621254925*08375225*371621254908525249.无需移动3725.无需移动i=2gap=2159-222116084925*2537524916082125*253752结果4921160825*2537524916无需移动214949后移5249无需移动214925*08无需移动25=25无需移动3725无需移动159-23i=3gap=1012345674916082125*2537522508162125*524937160816后移254949后移375252,49后移253708165249159-24i=3gap=1490123456716082125*2537522508162125*49524937开始时gap的值较大，子序列中的记录较少，排序速度较快；随着排序进展，gap值逐渐变小，子序列中记录个数逐渐变多，由于前面工作的基础，大多数记录已基本有序，所以排序速度仍然很快。159-25希尔排序的算法voidShellSort(dataList&L){Elementw;inti,j,gap=L.n/2;while(gap!=0){//循环,直到gap为零for(i=gap;iL.n;i++){w=L.elem[i];//直接插入排序for(j=i;j=gap;j=j-gap)if(w.keyL.elem[j-gap].key)L.elem[j]=L.elem[j-gap];elsebreak;L.elem[j]=w;}gap=gap/2;}}159-26开始时gap的值较大，子序列中的记录较少，排序速度较快；随着排序进展，gap值逐渐变小，子序列中记录个数逐渐变多，由于前面工作的基础，大多数记录已基本有序，所以排序速度仍然很快。gap取法有多种。最初shell提出取gap=n/2，gap=gap/2，直到gap=1。knuth提出取gap=gap/3+1。对特定的待排序记录序列，可以准确地估算排序码的比较次数和记录移动次数。算法分析159-27但想要弄清排序码比较次数和记录移动次数与增量选择间的依赖关系，并给出完整的数学分析，还没有人能够做到。Knuth利用大量实验统计资料得出:当n很大时，排序码平均比较次数和记录平均移动次数约在n1.25到1.6n1.25的范围内。后来Hibbard提出一个稍微不同的增量序列，让gap=2k-1,2k-1-1,...,7,3,1，最坏情况下结果更好，运行时间在理论上证明可达到O(n3/2)，但实际模拟结果可达到O(n5/4)。希尔排序是个不稳定的排序方法。159-28基本思想是两两比较待排序记录的排序码,如发生逆序(即排列顺序与排序后的次序正好相反)则交换之。直到所有记录都排好序为止。起泡排序的基本思路是：设待排序记录序列中的记录个数为n。最多作n-1趟起泡，i=1,2,,n-1。在第i趟中从后向前，j=n-1,n-2,,i，顺次两两比较elem[j-1]和elem[j]。如果发生逆序，即elem[j-1]＞elem[j]，则交换elem[j-1]和elem