【数据结构】排序算法系列——外排序（完结篇）

外排序

外排序是一种处理极大量以及海量数据的排序方法，适用于数据量大到无法完全加载到内存的情况。外排序通常采用”排序-归并“的策略，在面对海量数据的时候，会将数据分块处理并存储在外部存储的介质例如磁盘上，然后依次将这些数据读入内存并进行排序。

实际上外排序可以看成：将内存作为排序的过渡区间，读入内存主要进行分块数据的排序操作，其他时候数据是放在外部存储介质中进行保存的。

外归并排序

外归并排序是外排序的典型例子，它使用归并排序的思想，执行先排序再归并的操作，从而进行所有数据的排序。这里我们假设总共1GB的数据需要进行排序，而内存只有100MB，它按照如下方法操作：

1. 读入100MB数据进入内存中，将其进行排序（常规排序即可）
2. 将排序完成的数据重新写入磁盘
3. 进行1与2的过程直到1GB的数据都分次排序完成
4. 按照归并排序来进行所有数据的合成与排序（这里通常使用多路归并算法，K路归并利用优先[[队列]]或者堆来选择当前最小的元素，依次输出到最终的结果文件中）

外排序不仅仅只有外归并排序这一种算法，但这里只对其进行简单介绍，如果以后有时间将会介绍其他几种算法。另外还有外分配排序，其原理类似于内排序中的桶排序。在归并排序和桶排序之间存在数学上的某种对偶性。此外还有一些不耗费附加磁盘空间的原地排序算法。

外排序的特点

• I/O密集型：由于涉及大量的读写操作，外排序的性能很大程度上取决于磁盘I/O的效率。
• 适用于大数据集：外排序能够处理超大规模的数据集，这些数据集远超出内存的容量限制。

优化性能

• 并行计算
  • 用多个磁盘驱动器并行处理数据，可以加速顺序磁盘读写。[4]
  • 在计算机上使用多线程，可在多核心的计算机上得到优化。
  • 使用异步输入输出，可以同时排序和归并，同时读写。
  • 使用多台计算机用高速网络连接，分担计算任务。[5]
• 提高硬件速度
  • 增大内存，减小磁盘读写次数，减小归并次数。
  • 使用快速的外存设备，比如15000 RPM的硬盘或固态硬盘。
  • 使用性能更优良个各种设备，比如使用多核心CPU和延迟时间更短的内存。
• 提高软件速度
  • 对于某些特殊数据，在第一阶段的排序中使用基数排序。
  • 压缩输入输出文件和临时文件。