数据结构精品课件-归并排序、分配类排序.pptVIP

* * 9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序法 9.4 选择类排序法 9.5 归并排序 9.6 分配类排序 9.7 各种排序方法的综合比较 第九章 内部排序 9.8 总结与提高 9.5 归并排序 　　归并排序的过程基于下列基本思想进行： 将两个或两个以上的有序子序列 “归并” 为一个有序序列。 　在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个有序的序列。 有 序 序 列 r[l..n] 有序子序列 r[l..m] 有序子序列 r[m+1..n] 这个操作对顺序表而言，是轻而易举的。 归 并 例： (19) (13) (05) (27) (01) (26) (31) (16) (13,19) (05,27) (01,26) (16,31) (05,13,19,27) (01,16,26,31) (01,05,13,16,19,26,27,31) 52, 23, 80, 36, 68, 14 [ 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] 完整的归并排序过程为：先分组再归并。 合并算法 void Merge ( RecordType r1[], int low, int mid, int high, RecordType r[]) /*r1[low..mid]和r1[mid+1..high]分别有序，将它们合并*/ {i=low；j=mid+1； k=low； while ( (i=mid)(j=high) ) {if ( r1[i].key=r1[j].key ) {r[k]=r1[i] ； ++i；} else {r[k]=r1[j] ； ++j；} ++k ； } if ( i=mid ) r[k..high] =r1[i..mid]； if ( j=high ) r[k..high] =r1[j..high]； } 2-路归并排序算法 void MergeSort (RecordType r1[], int low, int high, RecordType r[]) /*r1[low..high]经排序后放在r[low..high]中,r2[low..high]为辅助空间 */ { RecordType r2 [hight-low+1] ； if ( low==high ) r[low]=r1[low]； else{mid=(low+high)/2； MergeSort(r1，low， mid, r2)； MergeSort(r1，mid+1，high, r2)； Merge (r2，low，mid，high， r)；} } 稳定？ 归并排序的复杂度分析： 　容易看出，对 n 个记录进行归并排序的时间复杂度为Ο(nlogn)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 ?log2n? 趟。 归并排序的空间复杂度较高，需要有长度为n的辅助数组，即为O(n)。 返回 9.6 分配类排序 　基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 多关键字的排序 基数排序 n 个记录的序列 { R1, R2, …，Rn} 对关键字 (Ki0, Ki1,…,Kid-1) 有序是指： 其中: K0 被称为 “最主/最高”位关键字 Kd-1 被称为 “最次/最低”位关键字 对于序列中任意两个记录Ri 和 Rj (1≤ij≤n) 都满足下列(词典)有序关系： (Ki0, Ki1, …,Kid-1) (Kj0, Kj1, …