知识点归并排序与基数排序

《知识点归并排序与基数排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、10.5归并排序（知识点三）归并的含义是将两个或两个以上的有序表组合成一个新的有序表。归并排序可分为两路归并排序,或多路归并排序，既可用于内排序，也可用于外排序。这里仅对内排序的两路归并方法进行讨论。两路归并排序算法思路：假设初始序列含有ｎ个记录，首先把ｎ个记录看成ｎ个长度为１的有序序列，进行两两归并，得到ｎ／２个长度为２的关键字有序序列，再两两归并直到所有记录归并成一个长度为ｎ的有序序列为止。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。有序序列R[i..n]有序子序列R[

2、i..m]有序子序列R[m+1..n]这个操作对顺序表而言，是轻而易举的。例：已知关键字序列：46,55,13,42归并排序过程如下：[4655][1342]voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){//将有序的记录序列SR[i..m]和SR[m+1..n]//归并为有序的记录序列TR[i..n]}//Mergefor(j=m+1,k=i;i<=m&&j<=n;++k){//将SR中记录由小到大地并入TRif(SR[i].key<=SR[j].key)TR[k]=SR[i

3、++];elseTR[k]=SR[j++];}……if(i<=m)TR[k..n]=SR[i..m];//将剩余的SR[i..m]复制到TRif(j<=n)TR[k..n]=SR[j..n];//将剩余的SR[j..n]复制到TR归并排序的算法如果记录无序序列R[s..t]的两部分R[s..(s+t)/2]和R[(s+t)/2+1..t]分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。由此，应该先分别对这两部分进行2-路归并排序。例如：52,23,80,36,68,14(s=1,t=6)[

4、52,23,80][36,68,14][52,23][80][52][23,52][23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]voidMsort(RcdTypeSR[],RcdType&TR1[],ints,intt){//将SR[s..t]归并排序为TR1[s..t]if(s==t)TR1[s]=SR[s];else{}}//Msort……m=(s+t)/2;//将SR[s..t]平分为SR[s..m]和SR[m+1..t]Msort(

5、SR,TR2,s,m);//递归地将SR[s..m]归并为有序的TR2[s..m]Msort(SR,TR2,m+1,t);//递归地SR[m+1..t]归并为有序的TR2[m+1..t]Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]voidMergeSort(SqList&L){//对顺序表L作2-路归并排序MSort(L.r,L.r,1,L.length);}//MergeSort容易看出，对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即：每一趟归并的时

6、间复杂度为O(n)，总共需进行log2n趟。10.6基数排序基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。多关键字的排序链式基数排序一、多关键字的排序n个记录的序列{R1,R2,…，Rn}对关键字(Ki0,Ki1,…,Kid-1)有序是指：其中:K0被称为“最主”位关键字Kd-1被称为“最次”位关键字对于序列中任意两个记录Ri和Rj(1≤i

7、最高位优先MSD法最高位优先MSD法:先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，...…，依次类推，直至最后对最次位关键字排序完成为止。最低位优先LSD法:先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。无序序列对K2排序对K1排序对K0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,

8、202,1,201,2,153,2,302,3,181,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下:二、链式基数排序假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”