第27讲 归并、基数排序.ppt

归并排序 基数排序 * 回顾： 交换排序法有哪些？时间复杂度分别是？ 快速排序的过程？ 选择排序法有哪些？时间复杂度分别是？ 上述排序算法的稳定性？ 树形选择排序有何缺点？ §10.5 归并排序 基本思想：将两个或两个以上的有序表“归并”为一个新的有序表。 初始序列含有n个记录，可看成是n个长度为1的有序子序列；然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，…，如此重复直到得到一个长度为n的有序序列。——2路归并 例：归并排序(49,38,65,97,76,13,27). 　　在内部排序中，通常采用的是2-路归并排序。即：将数组中前后相邻的两个有序子序列 归并为一个新的有序序列 有 序 序 列 R[i..n] 有序子序列 R[i..m] 有序子序列 R[m+1..n] 这个操作对顺序表而言，是轻而易举的。 一趟归并的算法： void Merge (RcdType SR[], RcdType TR[], int i, int m, int n) { // 将有序的记录序列 SR[i..m] 和 SR[m+1..n]归并为有序的记录序列 TR[i..n] } for (j=m+1, k=i; i=m j=n; ++k) { if (SR[i].key=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } if (i=m) TR[k..n] = SR[i..m]; // 将剩余的 SR[i..m] 复制到 TR if (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] 分别按关键字有序， 则利用上述归并算法很容易将它们归并成一个有序序列。 由此，应该先分别对这两部分进行归并排序。 void Msort ( RcdType SR[], RcdType TR1[], int s, int t ) { // 将SR[s..t] 归并排序为 TR1[s..t] } if (s= =t) TR1[s]=SR[s]; m = (s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t] Msort (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] else { } 对顺序表 L 作2-路归并排序: void MergeSort (SqList L) { MSort(L.r, L.r, 1, L.length);} 例：归并排序递归算法的执行过程 52, 23, 80, 36, 68, 14 (s=1, t=6) [ 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] 归并排序的算法分析： 每一趟归并调用(n/2h)次Merge算法将SR中前后相邻长度为h的有序段进行两两归并，故每一趟时间复杂度为 O(n)， 整个归并排序总共需进行 ?log2n? 趟， 对 n 个记录进行归并排序的时间复杂度为Ο(nlogn)； 由于需要和待排序记录等数量的辅助空间，所以S(n)=O(n)； 稳定性：稳定的算法 基本思想：借助“多关键字排序”的思想来实现“单关键字排序” 。 §10.6 基数排序（Radix Sorting） §10.6.1 多关键字的排序 设有n 个记录的序列 { R1, R2, …，Rn}, 且每个记录Ri有d个关键字(Ki0, Ki1,…,Kid-1) 。 序列对关键字 (Ki0, Ki1,…,K