C++算法
数据结构：外部排序原理与优化方法
本文介绍外部排序的基本原理，包括外存与内存间的数据处理逻辑、初始归并段的构造、多趟归并过程及时间开销分析。内容涵盖多路归并优化、败者树的应用以减少比较次数、置换 - 选择排序生成初始归并段的方法，以及基于哈夫曼树思想的最佳归并树构建策略。重点阐述了如何通过平衡读写操作和减少归并段数量来提升排序效率。
本文介绍外部排序的基本原理，包括外存与内存间的数据处理逻辑、初始归并段的构造、多趟归并过程及时间开销分析。内容涵盖多路归并优化、败者树的应用以减少比较次数、置换 - 选择排序生成初始归并段的方法，以及基于哈夫曼树思想的最佳归并树构建策略。重点阐述了如何通过平衡读写操作和减少归并段数量来提升排序效率。
特点：外存大，存储数据多；内存小，存储数据少。 规定：外存的数据只有读到内存之后才能进行修改，修改之后还要写回到外存（可以写回原来不同的位置）。
简单来说，因为外存数据又多又杂，就要一点一点读入到内存中排序，然后再写回外存。 逻辑：外存–>读出数据–>内存–>在内存有序排列数据（比如一个块三个数据 632 排成 236）–>写回外存。
因为内存腾出了两个存放数据块的位置（输入缓冲区）和写出数据的位置（输出缓冲区），2–>1，二合一就是二路归并。
从外存读入两个数据块放入内存的输入缓冲区内，然后就可以对这两个数据块进行归并排序了。
得到两个有序数列。
将这两个有序数列写回外存，这样就构成了一个有序的归并段。
经过 16 次读和 16 次写，外存就变成了左边的 8 个归并段。
接下来就需要我们把归并段们继续归并排序：
注意：写回的位置是另外一片，不是原来的存放未排序数据的位置。
出现一整个缓冲区空白的情况，就继续读入一个数据块，然后继续进行归并排序：
第一趟归并结束后，就成功得到了四个大的归并段：
和之前一样，挑出两个归并段中最小的一组，继续进行合并：
第二趟合并后，就得到了两个更大的归并段：
最后，把这两个更大的归并段进行合并：
最终就得到了有序的数据：
我们先对读写外存的这部分时间进行优化。
我们可以在内存多申请几个输入缓冲区，实现多路归并，一次读入两个数据段和一次读入四个数据段，当然是后者 I/O 次数更小，还可以减少归并的趟数。
假设：第一趟归并用 4 路归并
第一次归并后就得到两个归并段，只需要再一趟就可以完全有序：
比如之前的我们的初始归并段是 8 个，现在减少为 4 个：
4–>2–>1，得到初始归并段后再归并两次就可以完全有序了
外存的总数据块数不变，初始归并段越长，初始归并段越少。
重点在平衡这两个字上：
多路平衡归并：一个数要和很多个数都要比一次，才能找到最小的那个数字，就很浪费时间。
就是两个人战斗，失败的留下，胜利的上去，继续和另一组胜利的人继续比，最终选出一个冠军。
这个时候冠军跑路了：
由派大星顶替它原来的位置
那么难道我们还要重新比 7 次么？！
答案是不需要，右侧的根本没被派大星影响，右侧胜利的依旧是孙悟空； 而派大星需要代替天津饭，先和阿乐比，赢了再和程龙比，赢了再和孙悟空比； 只需要比对三次就可以了
同样的规则，我们就可以搬到归并段上使用。
画出败者树：
每个归并段都排除自己最小的一个数字参赛：
最终回合：6>2，6 留，2 上，所以结点是 2 所在的归并段 5；
这样就找出了最小的一个数
注意：结点中记录的是来自的归并段，而不是真实数字
所以再需要接着比赛选出最小的冠军，就只需要踩着前人的脚印，继续向上比拼。比如：
纯一块一块构造。
注意：这里的输出缓冲区省略了，但不代表没有
选择工作区内最小的但比 4 大的数字写出：
按照这个规律一直写出： 这里我们发现最小的一个数字是 10<13，而我们只能写出比 13 大的，所以就放着先不要动
当工作区内的数字都比 MINIMAX 小，不可以写出的时候：
我们就需要开一个新的归并段，经过写出最后是这样：
最后就得到了三个不定长的归并段：
注意：是有输出缓冲区存在的，只不过我们省略了而已
归并过程中的磁盘读写次数=归并树的 WPL*2 也就是最佳归并树是哈夫曼的形式
如果减少一个归并段，那么单纯地按照哈夫曼树的逻辑处理得到的就不是最佳归并树了：
我们需要添加一个结点 0，然后再按照正常的步骤继续进行：
情景：类似于上面缺少一个归并段的时候，我们需要添加几个结点 0？ 结论：图片最后两行（代入例子更好理解）
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online