8.2.1 直接插入 8.2.2 折半插入 8.2.3 希尔排序 8.3.1 冒泡排序 8.3.2 快速排序 8.3.3 快排优化 8.4.1 简单选择 8.4.2 堆排序 8.4.3 堆操作 8.5.1 归并排序 8.5.2 迭代归并 8.6.1 LSD基数 8.6.2 LSD vs MSD 8.7.1 雷达图 8.7.2 决策器 8.8.1 外部排序 8.8.2 最佳归并树
点击播放开始外部排序演示
阶段一:生成初始归并段
将数据按内存大小分成若干块,每块内部排序
读: 0 写: 0
阶段二:k路归并
将各归并段进行多路归并
?
外部排序说明

外部排序用于处理无法一次性装入内存的大规模数据。分为两个阶段:

1. 生成初始归并段:将文件分成若干段,每段读入内存进行内部排序,再写回外存。

2. 多路归并:使用k路归并将多个有序归并段合并成一个完整的有序文件。

时间复杂度 O(n log n) 主要开销:磁盘I/O