归并排序 ppt课件.ppt
10.5 归并排序,基本思想将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列。,ri rm rm+1 rn,有序,有序,有序,ri rn,10.5 归并排序,如何进行两路归并？将两个有序表的元素进行比较，小者复制到目标表中。,（5，24，35，74，222）,（19，23，30）,(),5,24,35,74,222,(,),19,23,30,(,),(,),5,19,23,24,30,35,74,222,两路归并动画演示,s,m,t,m+1,10.5 归并排序,void Merge(int r,int r1,int s,int m,int t)/*将有序列rs.m和rm+1.t两路归并为r1*/i=s;j=m+1;k=s;while(i=m/后一个子序列剩下的,10.5 归并排序,原理 假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止。,初始时：49 38 65 97 76 13 27,void Msort(Elem SR,Elem TR1,int s,int t)/*将SRs.t进行归并排序为TR1s.t*/if(s=t)TR1s=SRs;else m=(s+t)/2;/将SRs.t分割 Msort(SR,TR1,s,m);/递归地排序子序列SRs.m Msort(SR,TR2,m+1,t);/递归地排序子序列SRm+1.t Merge(TR2,TR1,s,m,t);/归并,10.5 归并排序,10.5 归并排序,性能分析 一趟归并操作是将r1rn中相邻的长度为h的有序序列进行两两归并，这需要O(n)时间。整个归并排序需要进行log2n趟，因此，总的时间代价是O(nlog2n)。,10.5 归并排序,性能分析 算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此空间复杂度为O(n)。,10.5 归并排序,总结最好、最坏、平均时间复杂度均为O(nlogn);空间复杂度高，为O(n);是高效算法中唯一“稳定”的排序方法；较少用于内部排序，多用于外部排序。,10.6 基数排序,基本思想,基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。,10.6 基数排序,多关键码排序问题,以扑克牌排序为例。每张扑克牌有两个“关键码”：花色和面值。其有序关系为：花色：面值：2 3 4 5 6 7 8 9 10 J Q K A,10.6 基数排序,“花色”优先先分成4堆；然后，每堆再按“面值”排；最后，收成一堆。,扑克牌“排序”为例,10.6 基数排序,“面值”优先先分成13堆；每堆再按“花色”排；,扑克牌“排序”为例,10.6 基数排序,多关键码排序,假设有n个记录的序列 R1,R2,，Rn每个记录Ri中含有d个关键字(Ki0,Ki1,Kid-1)。则有序是指：对于序列中任意两个记录Ri和Rj(1ijn)都满足下列(词典)有序关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)其中K0被称为“最高”位关键字，Kd-1被称为“最低”位关键字。,10.6 基数排序,多关键码排序实现多关键码排序通常有两种方法：低位码优先LSD高位码优先MSD,(3 J 8 9 9 3 1 7),先按花色：8 1 3 7 J 9 3 9,再按面值：1 8 3 7 9 J 3 9,10.6.2 链式基数排序,对于单关键字，可以看成是由多个数位构成的多关键字；基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。,例如：对下列这组关键字（每个关键字有3位）209,386,768,185,247,606,230,834,539,10.6.2 链式基数排序,基本思想从关键字的最“低位”开始，将关键字分配到r(基数）个堆（桶）中；按桶的编号将关键字收集起来；然后，以“次低位”将关键字又分配到r个桶中；再收集，重复直到“最高位”为止，这时，以按关键字有序。,例如：对下列这组关键字进行基数排序 209,386,768,185,247,606,230,834,539,基数为10,分别按“个位”、“十位”、“百位”进行3趟分配与收集,0,1,2,3,4,5,6,7,8,9,10.6.2 链式基数排序,实现思想为了便于分配与收集，采用链表为存储结构r个桶用r个链式队列表示；收集的时候直接将队列的头尾指针连接实现；,例,例,例,有序,10.6.2 链式基数排序,基数排序算法,10.6.2 链式基数排序,分配算法,10.6.2 链式基数排序,收集算法,10.6.2 链式基数排序,性能分析若每个关键码有d 位，需要重复执行d 趟“分配”与“收集”。而每趟对n 个对象进行“分配”，对r 个队列进行“收集”。总时间复杂度为O(d(n+r)。若基数r相同，对于数据个数较多而关键码位数较少的情况，使用链式基数排序较好。需要增加 n+2r个附加链接指针。稳定的排序方法,10.6 内部排序方法的比较讨论,对排序算法应该从以下几个方面综合考虑：时间复杂性；空间复杂性；稳定性；算法简单性；待排序记录个数n的大小；记录本身信息量的大小；关键码的分布情况,时间复杂度,空间复杂度,算法稳定性,简单性 一类是简单算法，包括直接插入排序、直接选择排序和冒泡排序，另一类是改进后的算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法较复杂,10.6 内部排序方法的比较讨论,10.6 内部排序方法的比较讨论,待排序记录个数比较 n越小，采用简单排序方法越合适。n越大，采用改进的排序方法越合适。因为n越小，O(n2)同O(nlog2n)的差距越小，并且输入和调试简单算法比 高效算法要容易,10.6 内部排序方法的比较讨论,数据的信息量比较 信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。,10.6 内部排序方法的比较讨论,数据的分布情况比较当待排序数据初始有序时，插入排序和冒泡排序能达到O(n)的时间复杂度；对于快速排序而言，这是最坏的情况，此时性能蜕化为O(n2)；选择排序、堆排序和归并排序的性能不受影响。,结束，谢谢！,
