数据结构讲义 第10章 排序 - 归并与基数排序.pdf

数据结构讲义 第10章排序 第10章排序 - 归并与基数排序 10.4 归并排序 10.4 归并排序 归并——将两个或两个以上的有序表组合成一 个新的有序表，叫~ 2-路归并排序 – 设初始序列含有n个记录，则可看成n个有序 的子序列，每个子序列长度为1。 – 两两合并，得到n/2个长度为2或1的有序子 序列。 – 再两两合并，……如此重复，直至得到一个 长度为n 的有序序列为止。 例子：合并两个有序表 例子：合并两个有序表 顺序比较两者的相应元素，小者移入另一表中，反复 如此，直至其中任一表都移入另一表为止。 i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 3 i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7 4 i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7 5 i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7 13 6