外部排序归并算法
todo: 整理笔记。https://geodoer.blog.csdn.net/article/details/83076081
外部排序归并算法¶
| 外部排序归并操作法 | 涉及的内容 | 说明 | 文件内容 |
|---|---|---|---|
| 文件中存有n个数，但内存大小只能存放m个数 | 15 19 04 83 12 27 11 25 16 34 26 07 10 90 06 |
||
| 第一阶段 | 置换-选择排序 | 将文件中的数据处理成多个 有序子序列 | 【第一种结果】每个子序列长度相同：4 12 15 19 83 | 11 16 25 27 34 | 6 7 10 26 90【第二种结果】每个子序列长度不同： 4 12 15 19 25 27 34 83 | 7 10 11 16 26 90 | 6 |
| 可选步骤 | 最佳归并树（生成哈夫曼树的方法） | 计算最优的归并方案 | 文件中生成了3个有序子序列，但长度都不相同。在进行二路归并时，策略就有很多：12先归并；再和3；13先归并,再和2；23先归并, 再和1 归并方案很多，如何取最优的归并方案呢？ |
| 第二阶段 | 败者树（选择每个归并段的最小值） | 对文件中的 多个有序子序列 进行归并操作 | 4 6 7 10 11 12 15 16 19 25 26 27 34 83 90 |
性能分析¶
【空间复杂度】O(1)
【时间复杂度】
| 步骤 | 说明 | 时间复杂度 | I/O操作 |
|---|---|---|---|
| 【第一阶段】初始归并段的生成 | 置换选择排序 | 选择最值那一步的时间复杂度要根据考试要求选择算法而定 | 所有记录都要进行两次I/O操作 |
| 【可选阶段】最佳归并树 | 生成哈夫曼树 | ||
| 【第二阶段】选择最值 | 用败者树选择最值 | 1. 【败者树建树】O(klog2k) 2. k路归并的败者树高度⌈log2k⌉+1，从k个记录中选择最值需要进行⌈log2k⌉此比较，即时间复杂度是O(log2k) |
|
| 【第二阶段】归并 | 归并 | m个初始归并段进行k路归并，归并的趟数⌈logkm⌉ | 每次归并，所有记录都要进行两次I/O操作 |
置换-选择排序¶
最佳归并树¶
【I/O次数计算方法I/O次数=带权路径长度*2】 I/O次数=2*WPL=446
败者树¶
