归并排序-课件

10.5归并排序基本思想将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列。r[i]r[m]r[m+1]r[n]有序有序有序r[i]r[n]10.5归并排序基本思想r[i]r[110.5归并排序如何进行两路归并？将两个有序表的元素进行比较，小者复制到目标表中。（5，24，35，74，222）（19，23，30）()10.5归并排序如何进行两路归并？（5，24，35，7425243574222()192330()ij()k5192324303574222两路归并动画演示ikjkjkikjk[s][m][t][m+1]5243574222()192330()ij()k51923310.5归并排序voidMerge(intr[],intr1[],ints,intm,intt){/***将有序列r[s..m]和r[m+1..t]两路归并为r1[]***/i=s;j=m+1;k=s;while(i<=m&&j<=t){//两表中元素比较if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}while(i<=m)r1[k++]=r[i++];//前一个子序列剩下的while(j<=t)r1[k++]=r[j++];//后一个子序列剩下的}10.5归并排序voidMerge(intr[]410.5归并排序原理假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……如此重复，直至得到一个长度为n的有序序列为止。初始时：[49][38][65][97][76][13][27]10.5归并排序原理初始时：[49][385初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]初始关键字：[49][38][65]6voidMsort(ElemSR[],ElemTR1[],ints,intt){

/****将SR[s..t]进行归并排序为TR1[s..t]****/

if(s==t)TR1[s]=SR[s];

else{m=(s+t)/2;//将SR[s..t]分割Msort(SR,TR1,s,m);//递归地排序子序列SR[s..m]Msort(SR,TR2,m+1,t);//递归地排序子序列SR[m+1..t]Merge(TR2,TR1,s,m,t);//归并

}}

10.5归并排序voidMsort(ElemSR[],ElemT710.5归并排序性能分析一趟归并操作是将r[1]~r[n]中相邻的长度为h的有序序列进行两两归并，这需要O(n)时间。整个归并排序需要进行log2n趟，因此，总的时间代价是O(nlog2n)。10.5归并排序性能分析810.5归并排序性能分析算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此空间复杂度为O(n)。10.5归并排序性能分析910.5归并排序总结最好、最坏、平均时间复杂度均为O(nlogn);空间复杂度高，为O(n);是高效算法中唯一“稳定”的排序方法；较少用于内部排序，多用于外部排序。10.5归并排序总结1010.6基数排序基本思想基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。10.6基数排序基本思想基数排序1110.6基数排序多关键码排序问题以扑克牌排序为例。每张扑克牌有两个“关键码”：花色和面值。其有序关系为：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A10.6基数排序多关键码排序问题以扑克牌排1210.6基数排序“花色”优先先分成4堆；然后，每堆再按“面值”排；最后，收成一堆。扑克牌“排序”为例10.6基数排序“花色”优先扑克牌“排序”为例1310.6基数排序“面值”优先先分成13堆；每堆再按“花色”排；

扑克牌“排序”为例10.6基数排序“面值”优先扑克牌“排序”为例1410.6基数排序多关键码排序假设有n个记录……的序列

{R1,R2,…，Rn}每个记录Ri中含有d个关键字(Ki0,Ki1,…,Kid-1)。则有序是指：对于序列中任意两个记录Ri和Rj(1≤i<j≤n)都满足下列(词典)有序关系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中K0被称为“最高”位关键字，Kd-1被称为“最低”位关键字。10.6基数排序多关键码排序假设有n个记录……的1510.6基数排序多关键码排序实现多关键码排序通常有两种方法：低位码优先LSD高位码优先MSD(3J899

317)先按花色：

8137

J

9

3

9再按面值：

1

837

9

J

3

910.6基数排序多关键码排序(3J1610.6.2链式基数排序对于单关键字，可以看成是由多个数位构成的多关键字；

基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。例如：对下列这组关键字（每个关键字有3位）{209,386,768,185,247,606,230,834,539}10.6.2链式基数排序对于单关键字，可以看成是由多个1710.6.2链式基数排序基本思想从关键字的最“低位”开始，将关键字分配到r(基数）个堆（桶）中；按桶的编号将关键字收集起来；然后，以“次低位”将关键字又分配到r个桶中；再收集，……，重复直到“最高位”为止，这时，以按关键字有序。10.6.2链式基数排序基本思想18例如：对下列这组关键字进行基数排序{209,386,768,185,247,606,230,834,539}基数为10分别按“个位”、“十位”、“百位”进行3趟分配与收集0123456789例如：对下列这组关键字进行基数排序基数为10分别按“个位”、1910.6.2链式基数排序实现思想为了便于分配与收集，采用链表为存储结构r个桶用r个链式队列表示；收集的时候直接将队列的头尾指针连接实现；10.6.2链式基数排序实现思想20例初始状态：278109063930589184505269008083109589269278063930083184505008r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：例初始状态：27810906393058918450526921505008109930063269278083184589第二趟收集：083184589063505269930r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269第一趟收集：例50500810993006326927808318458922008063083109184269278505589930第三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589第二趟收集：例有序0080630831091842692785055899302310.6.2链式基数排序//分配//收集基数排序算法10.6.2链式基数排序//分配//收集基数排序算法2410.6.2链式基数排序分配算法10.6.2链式基数排序分配算法2510.6.2链式基数排序收集算法10.6.2链式基数排序收集算法2610.6.2链式基数排序性能分析若每个关键码有d位，需要重复执行d趟“分配”与“收集”。而每趟对n个对象进行“分配”，对r个队列进行“收集”。总时间复杂度为O(d(n+r))。若基数r相同，对于数据个数较多而关键码位数较少的情况，使用链式基数排序较好。需要增加n+2r个附加链接指针。稳定的排序方法10.6.2链式基数排序性能分析2710.6内部排序方法的比较讨论对排序算法应该从以下几个方面综合考虑：⑴时间复杂性；⑵空间复杂性；⑶稳定性；⑷算法简单性；⑸待排序记录个数n的大小；⑹记录本身信息量的大小；⑺关键码的分布情况10.6内部排序方法的比较讨论对排序算法应该从以下几个方28排序方法平均情况最好情况最坏情况直接插入排序O(n2)O(n)O(n2)希尔排序O(nlog2n)O(n1.3)O(n2)冒泡排序O(n2)O(n)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)简单选择排序O(n2)O(n2)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)归并排序O(nlog2n)O(nlog2n)O(nlog2n)时间复杂度排序方法平均情况最好情况最坏情况直接插入排序O(n2)O(n29排序方法辅助空间直接插入排序O(1)希尔排序O(1)冒泡排序O(1)快速排序O(log2n)~O(n)简单选择排序O(1)堆排序O(1)归并排序O(n)空间复杂度排序方法辅助空间直接插入排序O(1)希尔排序O(1)冒泡排序30排序方法辅助空间直接插入排序稳定希尔排序不稳定冒泡排序稳定快速排序不稳定简单选择排序稳定堆排序不稳定归并排序稳定算法稳定性排序方法辅助空间直接插入排序稳定希尔排序不稳定冒泡排序稳定快31简单性

一类是简单算