数据结构-内排序.ppt

数据结构(C语言版),第10章,内排序,3,本章目标,10.1基本概念10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.6各种内排序方法的比较,10.1基本概念,5,10.1.1排序的定义和术语1-1,排序(sorting)是数据处理中一种很重要的运算，同时也是很常用的运算，一般数据处理工作25%的时间都在进行排序简单地说，排序就是把一组记录(元素)按照关键字的递增(由小到大)或递减(由大到小)的次序重新排列的过程排序码待排序的记录中的一个属性。它可以是任何一种可比的数据类型，它可以是记录的关键字，也可以是非关键字正序和逆序若有序表是按排序码升序排列的，则称为升序表或正序表，否则称为降序表或逆序表。不失普遍性，我们一般只讨论正序表,P219,6,10.1.1排序的定义和术语1-2,稳定的和不稳定的排序方法对具有同一排序码值的多条记录，若采用的排序方法使排序后记录的相对次序与排序前一致，则称此排序方法是稳定的，否则是不稳定的。如2,2,1，排序后若为1,2,2，则该排序方法是稳定的，若为1,2,2，则该排序方法是不稳定的内排序和外排序按照排序过程中使用内、外存的不同将排序方法分为内排序和外排序。若待排序记录全部在内存中，称为内排序；若待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中需要进行内、外存交换，称为外排序。本章仅讨论内排序内排序可分为五大类：插入排序、交换排序、选择排序、归并排序和基数排序,P220,7,10.1.1排序的定义和术语1-3,排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以用算法中的数据比较次数及数据移动次数来衡量若一种排序方法使排序过程在最差或平均情况下进行的比较和移动次数越少，则认为该方法的时间复杂性就越好分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的稳定性等指标,P220,8,10.1.2排序的存储表示,为简单起见，数据的存储结构采用记录的数组形式，同时假定排序码是关键字，为整型。记录数组的类型说明如下,typedefstructintkey;datatypeother;RecType;RecTypeRn;/n条记录,P220,10.2插入排序,10,基本原理,每步将一个待排序的记录，按其关键字大小，插入到前面已经排好序的一组记录中的适当位置上，直至记录全部插入为止。分为,11,10.2.1直接插入排序举例,对无序序列21,25,49,25*,16,8排序,12,直接插入排序的基本思想,把n个待排序的记录看成一个有序子表和一个无序子表的组合，开始时有序子表中只包含一个记录，无序子表中包含n-1个记录。排序过程每次从无序子表中取出第一个记录，把它的排序码依次与前面的有序子表中记录的排序码进行比较，将它插入到有序子表中适当的位置上，使有序子表进一步扩大，直至扩大到包含全部记录为止,13,直接插入排序算法实现,voidinsert_sort(RecTypeR,intn)/待排序元素用一个数组R表示，数组有n个记录for(inti=1;i=0,14,直接插入排序的性能分析2-1,最佳情况：排序前序列已经是正序。此时每个待排序的记录仅需和有序子表中最后一个元素比较一次即可。因此，比较操作的执行次数共为n-1次。移动操作为0次最差情况：排序前序列是逆序。此时每个待排序的记录需要和有序子表中每一个元素进行比较。分别比较1次、2次、3次、n-1次。因此，比较操作的执行次数共为1+2+3+(n-1)=n(n-1)/2=O(n2)次。移动操作亦为n(n-1)/2=O(n2)次平均情况：若待排记录是随机的，即待排序列中的记录可能出现的各种排列的概率相等，则我们可取上述最小值和最大值的平均值，作为直接插入排序时所需进行关键字间的比较次数和移动次数，约为n2/4。由此，直接插入排序的平均时间复杂度为O(n2)直接插入排序是一种稳定的排序方法,P222,15,直接插入排序的性能分析2-2,16,10.2.2Shell排序,Shell排序又称“缩小增量排序”，是1959年由Shell提出来的该方法的基本思想是：先将整个待排序列分割成若干个子序列(每个子序列由相隔某个“增量”的元素组成)，分别进行直接插入排序，然后将增量递减，又得到若干个子序列，对它们再分别进行直接插入排序待整个序列中的元素基本有序(增量减小到1)时，再对全体元素进行一次直接插入排序,P223,17,Shell排序举例,对无序序列21,25,49,25*,16,8排序,18,Shell排序算法实现,voidshell_sort(RecTypeR,intdelta)for(intk=0;ksizeof(delta)/sizeof(int);+k)shell_insert(R,n,deltak);,19,Shell排序算法实现,为什么shell排序的时间性能优于直接插入排序呢？因为直接插入排序在基本有序时所需时间较少。在shell排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快。后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但组内元素已经过多次排序，数组已经比较接近有序状态，所以新的一趟插入排序过程也较快,voidshell_insert(RecTypeR,intn,intdelta)for(inti=delta;i0,20,Shell排序的性能分析,Shell排序的时间复杂度在O(nlog2n)和O(n2)间，Knuth的统计结论是，平均比较次数和记录平均移动次数在n1.25与1.6n1.25之间Shell排序是一种不稳定的排序方法最后谈一下delta的取法。Shell最初的方案是delta=n/2，delta=delta/2，直到delta=1。Knuth的方案是delta=delta/3+1。其它方案有：都取奇数为好；或delta互质为好等等。而使用象1,2,4,8,或1,3,6,9,这样的增量序列就不太合适，因为这样会使几个元素多次被分到一组中，从而造成重复排序，产生大量无用的比较操作总之，增量delta的选择应尽量避免两个元素先后出现在同一组中，增加不必要的重复比较的次数,10.3交换排序,22,基本原理,两两比较待排序的记录的关键字，如果发生逆序，则交换之，直到全部记录都排好序为止。分为,23,10.3.1冒泡排序举例,对无序序列21,25,49,25*,16,8排序,注意顺序,24,冒泡排序的基本思想,把n个待排序的记录看成一个有序子表和一个无序子表的组合，开始时有序子表中只包含一个记录，无序子表中包含n-1个记录。排序过程通过对无序子表中的元素从后向前(从下标较大的元素开始)，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从无序子表的后部移向前部(从下标较大的单元移向下标较小的单元，就象水下的气泡一样逐渐向上冒)，移到无序子表的表头时合并进有序子表，使有序子表进一步扩大，直至扩大到包含全部记录为止另外，在无序子表中向前移动的过程中，如果没有交换元素，则说明无序子表已有序，无须再做排序,P226,25,冒泡排序算法实现,voidbubble_sort(RecTypeR,intn)/待排序元素用一个数组R表示，数组有n个记录inti,j;boolswap=TRUE;/判断无序子表是否已有序的变量RecTypetemp;for(i=0;ii;-j)if(Rj.keyRj-1.key)swap=TRUE;tempRj-1;/交换Rj和Rj-1Rj-1=Rj;Rjtemp;,26,冒泡排序的性能分析,最佳情况：排序前序列已经是正序。比较操作的执行次数为n-1=O(n)次。移动操作为0次最差情况：排序前序列是逆序。比较操作的执行次数共为(n-1)+(n-2)+(n-3)+1=n(n-1)/2=O(n2)次。移动操作的执行次数亦为(n-1)+(n-2)+(n-3)+1=n(n-1)/2=O(n2)次平均情况：若待排记录是随机的，即待排序列中的记录可能出现的各种排列的概率相等，则我们可取上述最小值和最大值的平均值作为冒泡排序时所需进行关键字间的比较次数和移动次数，约为n2/4。由此，冒泡排序的平均时间复杂度为O(n2)冒泡排序是一种稳定的排序方法,P227,27,10.3.2快速排序,快速排序(quicksort)是迄今为止所有内排序算法中速度最快的一种，因此叫快速排序它的基本思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排序元素分为左右两个子序列。左子序列元素的排序码均小于基准元素，右子序列的排序码均大于等于基准元素，然后分别对两个子序列继续按上述方法排序(因此可以采用递归方法)，直至整个序列有序快速排序是对冒泡排序的一种改进，排序码较大的元素一次就能够交换到后面的子序列，排序码较小的记录一次就能够交换到前面的子序列，记录每次移动的距离较远，因而总的比较和移动次数较少通常，这个基准元素叫支点(pivot),P227-228,28,快速排序举例3-1,快速排序举例：49,38,65,97,76,13,27,49*,29,快速排序举例3-2,从上图可知，通过一次划分，将一个区间以基准值49分成两个子区间，左子区间的值小于基准值，右子区间的值大于等于基准值然后，分别对两个子区间重复此划分步骤，则可以得到快速排序的结果,30,快速排序算法实现,/划分函数intpartition(RecTyepR,intlow,inthigh)Rectypepivot=Rlow;/暂存支点while(low=pivot.key)-high;Rlow=Rhigh;while(lowhigh,P228算法9.4,31,快速排序算法的性能分析4-1,快速排序出现的最佳情况是每次划分使得左、右子区间的长度大致相等，此时，快速排序的最佳时间复杂度为O(nlog2n)理论上证明：快速排序的平均时间复杂度也为O(nlog2n)快速排序出现的最差情况是每次划分成两个子区间，但其中的一个是空的，即划分后，支点总是落在端点上。这种现象在待排序列已经有序或基本有序时最常发生。此时，快速排序蜕化为冒泡排序，其时间复杂度为O(n2)，这是快速排序的最差情况此外，在快速排序中，我们也可以选择序列起点、终点和中间点三者的中间值作为支点快速排序是一种不稳定的排序方法,32,快速排序算法的性能分析4-2,10.4选择排序,34,基本原理,将待排序的记录分为已排序子序列和为未排序子序列两组，依次将未排序的子序列中排序码最小的元素交换到已排序组的组尾。分为,35,10.4.1简单选择排序的基本思想,第一次从R0Rn-1中选取最小值，与R0交换，第二次从R1Rn-1中选取最小值，与R1交换，第三次从R2Rn-1中选取最小值，与R2交换,第i次从Ri-1Rn-1中选取最小值，与Ri-1交换，,第n-1次从Rn-2和Rn-1中选取最小值，与Rn-2交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列,P230,36,简单选择排序举例,37,简单选择排序算法实现,voidselect_sort(RecTypeR,intn)RecTypetemp;intmin;for(inti=0;in-1;+i)min=i;for(intj=i+1;jn;+j)if(Rj.key的结点都是叶结点，因此都已是堆。这样，我们只需依次将序号为,-1,.，1的结点作为根的子树都调整为最大堆即可,42,建立初始最大堆5-1,例：关键字序列为42,13,91,23,24,16,5,88，共八个关键字，建立初始最大堆我们从4号结点开始依次向前调整为最大堆,43,建立初始最大堆5-2,44,建立初始最大堆5-3,45,建立初始最大堆5-4,46,建立初始最大堆5-5,47,建立初始最大堆算法6-1,每次将一个指定的结点为根的子树调整为最大堆可以用下面的伪代码描述,heap_adjust()p=子树的根;while(p不是叶结点,48,建立初始最大堆算法6-2,其C语言实现为,voidheap_adjust(RecTypeR,inti,intlast)/将以i为根的树调整为最大堆intchild=i*2;/child为结点i的左孩子while(child=1;-i)heap_adjust(R,i,n);/建立初始最大堆for(inti=n;i1;-i)/堆排序swap(R1,Ri);/交换首尾排序码的值heap_adjust(R,1,i-1);/重建最大堆,P236算法9.8,65,堆排序的性能分析,从前面的算法可知，在整个堆排序中，共需要进行n/2+n-1=O(n)次调整(heap_adjust)运算每次调整运算进行双亲和孩子结点的排序码的比较和移动，次数不会超过完全二叉树的深度，故每次调整运算的时间复杂度为O(log2n)故整个堆排序过程的时间复杂度为O(n)*O(log2n)=O(nlog2n)，这是最佳、平均和最差情况下的时间复杂度相对于快速排序来说，堆排序的时间复杂度相当稳定，与输入排序码的顺序无关，这是堆排序的最大优点堆排序是一种不稳定的排序方法,P237,10.5归并排序,67,归并排序的基本思想,归并(merge)是指将两个有序序列合并成一个有序序列归并排序的基本思想是：将两个有序子序列合并成一个更大的有序序列。一次合并完成后，有序子序列的数目减少一半，而每个子序列的长度增加一倍，当序列长度从1增加到n时，序列变为一个，则该序列就是我们所需的排序结果,P237,68,归并排序举例,对无序序列46,55,13,42,94,5,17排序,69,归并操作,首先让我们看一下归并操作归并操作是指将两个有序表合并成一个有序表的过程。这个算法我们在第二章中提到过归并操作的算法实现,voidmerge(RecTypeS,RecTypeT,inti,intm,intn)/将有序子表Si.m和Sm+1.n归并为有序表Ti.nfor(k=i,j=m+1;i=m,P238算法9.9,70,归并排序算法实现,归并排序一般有两种实现方法：递归算法和迭代算法递归算法首先把整个待排序列划分为两个长度大致相等的部分，分别称为左子表和右子表。对这两个子表分别递归地进行排序，然后再把排好序的子表进行归并,71,归并排序的递归算法,voidMSort(RecTypeS,RecTypeT,ints,intt)/将无序表Ss.t归并为有序表Ts.tRecTypeT1=newRecTypet-s;if(s=t)Ts=Ss;elsem=(s+t)/2;/将Ss.t平分为Ss.m和Sm+1.tMSort(S,T1,s,m);/将无序表Ss.m归并为有序表T1s.mMSort(S,T1,m+1,t);/将无序表Sm+1.t归并为有序表/T1m+1.tmerge(T1,T,s,m,t);/将有序表T1s.m和有序表/T1m+1.t归并为有序表Ts.t/