归并排序ppt课件.ppt

《归并排序ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、10.5归并排序基本思想将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列。r[i]r[m]r[m+1]r[n]有序有序有序r[i]r[n]10.5归并排序如何进行两路归并？将两个有序表的元素进行比较，小者复制到目标表中。（5，24，35，74，222）（19，23，30）()5243574222()192330()ij()k5192324303574222两路归并动画演示ikjkjkikjk[s][m][t][m+1]10.5归并排序voidMerge(int

2、r[],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归并排序原理假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。然后

3、两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……如此重复，直至得到一个长度为n的有序序列为止。初始时：[49][38][65][97][76][13][27]初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]voidMsort(ElemSR[],ElemTR1[],ints,intt){/****将SR[s..t]进行归并排序为TR1[s..t]****/if(s==t

4、)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归并排序10.5归并排序性能分析一趟归并操作是将r[1]~r[n]中相邻的长度为h的有序序列进行两两归并，这需要O(n)时间。整个归并排序需要进行log2n趟，因此，总的时间代价是O(nlog2n)。10.5归并排序性能分析算法在执行时，需要占用与原始记录序列

5、同样数量的存储空间，因此空间复杂度为O(n)。10.5归并排序总结最好、最坏、平均时间复杂度均为O(nlogn);空间复杂度高，为O(n);是高效算法中唯一“稳定”的排序方法；较少用于内部排序，多用于外部排序。10.6基数排序基本思想基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。10.6基数排序多关键码排序问题以扑克牌排序为例。每张扑克牌有两个“关键码”：花色和面值。其有序关系为：花色：面值：2<3<4<5<6<7<8<9<10

6、每堆再按“面值”排；最后，收成一堆。扑克牌“排序”为例10.6基数排序“面值”优先先分成13堆；每堆再按“花色”排；扑克牌“排序”为例10.6基数排序多关键码排序假设有n个记录……的序列{R1,R2,…，Rn}每个记录Ri中含有d个关键字(Ki0,Ki1,…,Kid-1)。则有序是指：对于序列中任意两个记录Ri和Rj(1≤i

7、低位码优先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910.6.2链式基数排序对于单关键字，可以看成是由多个数位构成的多关键字；基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。例如：对下列这组关键字（每个关键字有3位）{209,386,768,185,247,606,230,834,539}10.6.2链式基数排序基本思想从关键字的最“低位”开始，将关键字分配到r(基数）个堆（桶）中；按桶的编号将关键字收集起来；然后，以“

8、次低位”将关键字又分配到r个桶中；再收集，……，重复直到“最高位”为止，这时，以按关键字有序。