知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.10 · 生成模型:未记录

归并先排子区间再合并

理解等级:中级

归并排序先按位置把区间分成两半,分别递归排好,再将两份有序结果合为一份。单元素自然有序,回归时每一步都以两份已排序子区间为前提;这和快排先按枢轴值建立分区不同。

两路合并分别用游标指向当前首个未消费项,比较后取更小的一项并推进该边游标;一边耗尽后复制另一边剩余项。每项只输出一次,合并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)之外,它以可预见的方式合并有序分区和数据,这种特性让我们很容易管理数据,使这些数据可以在内存中高效地读入读出。 问:假设我们正在一个用户界面中维护一个有序元素的列表。这个列表相对较小,而

    参考来源

    - 位置:《算法精解:C语言描述》第12章《归并排序的描述》(spine1344;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1310.html;u212-ch12-011)。 - 结论依据:212全部分治/两路合并/大数据段实读,214及02961两路合并完整图已读,为游标机制具体支撑;未把外排序用途当示例已实现。 - 原始内容:将两个有序的数据集合并成一个有序的数据集。正如我们看到的,合并两个有序数据集的过程是高效的,因为我们只需要遍历一次即可。根据以上事实,再加上该算法是按照可预期的方式来划分数据的,这使得归并排序在所有的情况下都能达到快速排序的平均性能。 遗憾的是,归并排序需要额外的存储空间来运行,这也是它的一个缺点。 - 位置:《算法精解:C语言描述》第12章《归并排序的实现与分析》(spine1346;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1312.html;u214-ch12-011)。 - 结论依据:214/02964–02965初始化ipos=i、jpos=j+1、mpos=0,循环两边任一仍有项;耗尽一侧后复制另一侧全部剩余。每次推进一个游标,最后把缓冲写回a[i*esize]再free。 - 原始内容:ipos和jpos指向每个有序集的头部。只要数据集中还有元素存在,合并过程就将持续下去。如果数据集中没有元素,进行如下操作:如果一个集合没有要合并的元素,那么将另外一个集中要合并的元素全部放到合并的集合中。否则,首先比较两个集合中的首元素,判断哪个元素将要放到合并的集合中,然后将它放置进去,接着根据 - 位置:《算法精解:C语言描述》第12章《问与答》(spine1357;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1323.html;u225-ch12-011)。 - 结论依据:225投资公司按客户名排序只是外排序使用场景:分块排有序段再逐路归并,适合不一次装入全部数据;与资金不变量/事故无关,不造支付案例。 - 原始内容:一次将所有数据读入内存。这种情况下应该选择哪种排序算法? 答:归并排序。除了它的排序时间可以维持在O(nlg n)之外,它以可预见的方式合并有序分区和数据,这种特性让我们很容易管理数据,使这些数据可以在内存中高效地读入读出。 问:假设我们正在一个用户界面中维护一个有序元素的列表。这个列表相对较小,而