知识卡片
归并先排子区间再合并
归并排序先按位置把区间分成两半,分别递归排好,再将两份有序结果合为一份。单元素自然有序,回归时每一步都以两份已排序子区间为前提;这和快排先按枢轴值建立分区不同。
两路合并分别用游标指向当前首个未消费项,比较后取更小的一项并推进该边游标;一边耗尽后复制另一边剩余项。每项只输出一次,合并q与p项为O(q+p)元素操作。
本书数组实现先写临时缓冲再复制回原区间,并非所有归并算法都必须用同样的额外数组。分块排序后逐步合并也适合超过一次内存容纳量的数据,但此处源码仍是内存数组版本,不是完整外排序系统。
214/02964–02965初始化ipos=i、jpos=j+1、mpos=0,循环两边任一仍有项;耗尽一侧后复制另一侧全部剩余。每次推进一个游标,最后把缓冲写回a[i*esize]再free。
225投资公司按客户名排序只是外排序使用场景:分块排有序段再逐路归并,适合不一次装入全部数据;与资金不变量/事故无关,不造支付案例。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 归并先排子区间再合并
- · 归并排序的实现与分析
- · 问与答
原书出处 · 3 处
- · 查看原书依据
将两个有序的数据集合并成一个有序的数据集。正如我们看到的,合并两个有序数据集的过程是高效的,因为我们只需要遍历一次即可。根据以上事实,再加上该算法是按照可预期的方式来划分数据的,这使得归并排序在所有的情况下都能达到快速排序的平均性能。 遗憾的是,归并排序需要额外的存储空间来运行,这也是它的一个缺点。
- · 查看原书依据
ipos和jpos指向每个有序集的头部。只要数据集中还有元素存在,合并过程就将持续下去。如果数据集中没有元素,进行如下操作:如果一个集合没有要合并的元素,那么将另外一个集中要合并的元素全部放到合并的集合中。否则,首先比较两个集合中的首元素,判断哪个元素将要放到合并的集合中,然后将它放置进去,接着根据
- · 查看原书依据
一次将所有数据读入内存。这种情况下应该选择哪种排序算法? 答:归并排序。除了它的排序时间可以维持在O(nlg n)之外,它以可预见的方式合并有序分区和数据,这种特性让我们很容易管理数据,使这些数据可以在内存中高效地读入读出。 问:假设我们正在一个用户界面中维护一个有序元素的列表。这个列表相对较小,而