数据结构课件：第11章 外部排序.ppt

外部排序是针对大量数据无法一次性装入内存进行排序的一种处理方式。当待排序的数据量过大，内存不足以一次性容纳所有数据时，就需要将数据分批调入内存进行排序，然后将排序好的部分写回外存，通过多次内外存之间的数据交换和归并，最终完成整个数据集的排序。这个过程涉及的主要方法是归并排序，尤其是多路平衡归并排序。 1. **外部排序的基本概念**： - 当数据量超出内存容量时，需要借助外部存储设备，如磁盘，进行排序。 - 排序过程中数据需要在内存和外存之间反复传输，增加了排序的复杂性。 - 主要分为两个阶段：划分阶段和归并阶段。划分阶段将数据分段并在内存中进行初步排序，归并阶段将这些有序段逐步合并成一个大的有序序列。 2. **多路平衡归并排序**： - 在多路平衡归并排序中，数据被划分为多个段，每个段分别在内存中进行排序，然后进行多路归并。 - 归并路数 k 决定了每次归并的段数，从而影响总的读写次数 d。k 越大，d 可能越小，但同时也可能增加内部归并的比较次数。 - 归并趟数 s 由归并路数 k 和初始段数 m 决定，s = ⌈log_k m⌉。 3. **归并过程中的优化**： - 通过增加归并路数 k 可以减少总的磁盘读写次数 d，但同时会增加比较次数，因此需要权衡 k 的选取。 - 减少初始段数 m 也可以减小 d，但这可能会增加单次归并的工作量，需要考虑内存与外存之间的平衡。 - 使用败者树技术可以在 k 较大时减少选择最小元素的比较次数，降低归并的计算复杂性。 4. **计算成本**： - 外部排序的总时间包括内部排序时间、外存读写时间和内部归并时间。 - 归并趟数 s 影响了外存读写的次数 d，而 d 对排序效率的影响通常远大于内部排序和归并操作。 - 因此，优化外部排序主要是通过调整归并策略来减少 d，如选择合适的 k 值和败者树技术。 总结来说，外部排序是处理大数据量场景下的关键算法，通过多路平衡归并等策略优化内外存交互，减少磁盘读写次数，提升整体排序效率。败者树等数据结构的应用进一步减少了比较次数，使得大规模数据的排序成为可能。在实际应用中，需要根据系统资源和数据特性灵活选择合适的外部排序策略。