外观
08 - 排序算法怎么选:稳定性、内存与数据分布
摘要
给订单排序时,除了按哪个字段比较,还要决定同值订单如何排列、数据能否放入内存,以及能否接受最坏情况下的耗时。本文先解释插入、归并、快速和堆排序的基本过程,再从稳定性、空间和数据分布选择方案,并说明 Java 排序 API 的使用边界。
1. 场景:同分订单为什么顺序乱了
假设业务要求“先按优先级排列,同优先级按创建时间排列”。可以先按创建时间排序,再按优先级排序;第二次只比较优先级。如果第二次排序不稳定,同优先级订单原有的时间顺序就可能被破坏。
稳定排序保证比较结果相等的元素保持排序前的相对顺序。例如订单 A、B 优先级相同,第一次排序后 A 在 B 前,稳定的第二次排序仍会让 A 在 B 前。分阶段排序时,应先排次要字段,再用稳定排序处理主要字段。
稳定性只保留已有顺序,不会自动生成业务需要的次级顺序。也可以用一个比较器一次定义“优先级、创建时间”的比较规则,第 6 节会说明这种写法。
2. 四类核心排序
以下讨论数组的升序排序:允许相邻值相等,也称非递减顺序。n 表示元素数量,假设一次比较和一次元素移动的成本为常数。四种算法的区别在于如何逐步建立有序性:
- 插入排序:维护一个有序前缀,每次把下一个元素插入前缀中的正确位置,较大的元素向右移动。
- 归并排序:把数组拆成两半,分别排序,再合并两个有序区间;合并时比较两边尚未取出的第一个元素,取较小者。
- 快速排序:选一个基准值,先把较小值和较大值分到两侧,再分别排序。分区后两侧各自还不一定有序。
- 堆排序:用数组构建大顶堆,即父节点不小于子节点的树形结构,根节点是最大值;反复把根移到未排序区末尾,再恢复堆的约束。这里的堆是数据结构,与 JVM 用于分配对象的堆内存含义不同。
下表对应这些常见实现,归并排序使用临时数组,堆排序使用迭代调整:
| 算法 | 平均时间 | 最坏时间 | 额外空间 | 稳定性 |
|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 可稳定 |
| 快速排序 | O(n log n) | O(n²) | 递归栈 | 通常不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
表中的稳定性取决于实现细节:插入时只移动严格大于当前值的元素,归并时相等优先取左侧元素,才能保留相对顺序。
“原地”通常指直接在输入数组内交换或移动元素,但仍要说明是否计入递归栈。每次递归调用都要保存返回位置和局部状态;快速排序分区较均衡时栈深为 O(log n),持续失衡时可达 O(n)。本例归并排序也有递归栈,但临时数组占用的 O(n) 是额外空间的主要部分。
3. 快速排序的分区思想
基准值(pivot)用来划分大小关系。下面是需要放入 Java 类中的局部方法:a 非 null;对非空区间,要求 0 <= left <= right < a.length,两端都包含在排序范围内。left >= right 时直接返回。
i 从左寻找不小于基准的值,j 从右寻找不大于基准的值。两者尚未交错时交换这两个值,再各前进一步。相等值也会触发交换并推进下标,因此循环不会停在重复值上。
java
static void quickSort(int[] a, int left, int right) {
if (left >= right) return;
int i = left;
int j = right;
int pivot = a[left + (right - left) / 2];
while (i <= j) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
}
quickSort(a, left, j);
quickSort(a, i, right);
}循环结束后,[left, j] 中的值不大于基准,[i, right] 中的值不小于基准;接下来递归处理这两个区间。这个实现不保证把某个基准元素放到最终位置,因此不能把它理解成“先固定一个元素,再排序左右两边”。
每轮分区扫描当前区间。若两侧规模接近,每层总扫描量为 O(n),约有 log n 层;若反复分成一个很小区间和一个很大区间,扫描量接近 n + (n - 1) + …,最坏时间就会达到 O(n²),递归栈也随之加深。选择中间位置的元素并不等于选到中位数,不能保证分区均衡。
这是教学实现,生产优先使用经过充分验证的标准库。大量重复值对性能的影响取决于分区写法;本例会推进相等值上的下标,但交换仍可能改变相等元素的相对顺序。
4. 为什么近乎有序数据适合插入思路
逆序对是下标满足 i < j、值却满足 a[i] > a[j] 的一对元素。插入排序把当前值向左插入时,需要把前面比它大的值右移,因此移动次数与逆序对数量有关。数组已经有序时,每轮只需检查前一个元素,不需要移动,总时间为 O(n);逆序对较少时,移动工作也较少。
这里的“近乎有序”应从逆序对或可利用的有序片段来判断,不能只凭外观看起来变化不大。TimSort 是利用已有连续有序片段,再合并这些片段的排序策略之一;它并不是对整个数组简单执行插入排序。
Java Arrays.sort 对基本类型和对象数组使用不同策略,具体实现随 JDK 版本变化;依赖稳定性或最坏行为时应查看目标 JDK 文档与源码。
这里应区分接口契约和实现事实:契约是调用方可以依赖的行为保证,具体算法则可能变化。Arrays.sort 的对象数组排序保证稳定;具体使用 TimSort、Dual-Pivot Quicksort(双轴快速排序)或其他实现,属于 JDK 版本事实,不能当作跨版本保证。本文未核对某个具体 JDK 的文档和源码,使用时应确认目标版本及重载方法。
并行排序把工作拆成多个任务,还涉及线程调度、共享线程池和额外空间。这些开销可能抵消并行收益,因此数据量大并不足以证明它更快,还要在目标环境中比较。
5. 完整可运行示例:插入、归并、快速与堆排序
下面的类对应文件名 SortingDemo.java,包含 main 入口。四个排序方法都要求数组非 null,直接修改数组并按升序排列;空数组和单元素数组无需调整。归并方法使用 [l, r) 左闭右开区间,快速排序使用 [l, r] 闭区间,不要混用结束下标。
java
import java.util.Arrays;
/**
* 可运行示例:排序算法怎么选:稳定性、内存与数据分布。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class SortingDemo {
static void insertion(int[] a) {
for (int i = 1; i < a.length; i++) {
// 循环开始时,[0, i) 已经有序,本轮把 a[i] 插入正确位置。
int v = a[i],
j = i - 1;
// 只移动严格大于 v 的元素;相等元素不交换,因此保持稳定性。
while (j >= 0 && a[j] > v) a[j + 1] = a[j--];
a[j + 1] = v;
}
}
static void mergeSort(int[] a) {
merge(a, new int[a.length], 0, a.length);
}
static void merge(int[] a, int[] t, int l, int r) {
if (r - l < 2) return;
int m = (l + r) >>> 1;
// 先递归保证左右半区各自有序。
merge(a, t, l, m);
merge(a, t, m, r);
int i = l,
j = m,
k = l;
// 每次取两个有序区间中较小的队首;相等时优先左侧以保持稳定。
while (i < m || j < r)
t[k++] = j >= r || (i < m && a[i] <= a[j]) ? a[i++] : a[j++];
System.arraycopy(t, l, a, l, r - l);
}
static void quickSort(int[] a) {
quick(a, 0, a.length - 1);
}
static void quick(int[] a, int l, int r) {
if (l >= r) return;
// 使用中间元素作为基准,避免总选端点在有序输入上的明显退化。
int i = l,
j = r,
p = a[l + (r - l) / 2];
while (i <= j) {
// 左边找不小于基准的元素,右边找不大于基准的元素。
while (a[i] < p) i++;
while (a[j] > p) j--;
if (i <= j) swap(a, i++, j--);
}
quick(a, l, j);
quick(a, i, r);
}
static void heapSort(int[] a) {
// 最后一个非叶子节点是 length/2-1,自底向上构建大顶堆。
for (int i = a.length / 2 - 1; i >= 0; i--) down(a, i, a.length);
for (int end = a.length - 1; end > 0; end--) {
// 堆顶是未排序区最大值,把它交换到数组末尾。
swap(a, 0, end);
down(a, 0, end);
}
}
static void down(int[] a, int root, int size) {
while (root * 2 + 1 < size) {
int c = root * 2 + 1;
if (c + 1 < size && a[c + 1] > a[c]) c++;
if (a[root] >= a[c]) return;
swap(a, root, c);
root = c;
}
}
static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
// 运行入口:让四种算法分别处理同一组含重复值的数据。
public static void main(String[] args) {
int[] source = { 5, 1, 4, 2, 8, 2 };
for (int type = 0; type < 4; type++) {
int[] a = Arrays.copyOf(source, source.length);
if (type == 0) insertion(a);
else if (type == 1) mergeSort(a);
else if (type == 2) quickSort(a);
else heapSort(a);
System.out.println(Arrays.toString(a));
}
}
}main 为每种算法复制一份输入,避免后面的算法拿到已经排好的数组。手工推导,预期输出四行 [1, 2, 2, 4, 5, 8];这不是实际运行记录,也不能代替边界测试。
归并时用 <=,相等值先从左半区取出,因而保留原相对顺序。仅打印 int[] 无法观察两个相同值是否交换了身份;验证稳定性需要带原始位置或标识的记录。快速排序和堆排序的远距离交换通常不保留这种顺序。
手工推演:归并 [4,1,3,2]
先拆成 [4,1] 与 [3,2],继续拆到单元素;分别合并为 [1,4] 和 [2,3],最后比较两个有序序列的队首,依次取出 1、2、3、4。
递归树约有 log n 层,每层合并的元素总数都是 n,所以时间复杂度为 O(n log n);临时数组需要 O(n) 空间。
四种算法的正确性抓手
- 插入排序:每轮结束后
[0,i]有序。 - 归并排序:子区间先有序,合并时每次取剩余最小元素。
- 快速排序:分区后两个待递归区间分别不大于、不小于基准,并且区间缩小;递归完成后得到整体有序结果。
- 堆排序:每轮把未排序区最大值放到末尾,已排序区不断扩大。
如何选择
先确认是否需要完整排序;只取最大的 K 个元素时,可以阅读下一篇 Top K,避免为其余元素建立完整顺序。需要排序时,按约束筛选:
- 近乎有序且规模较小:可考虑插入排序,因为移动较少、实现简单;无序且规模大时,其平方级成本仍需关注。
- 要求稳定性:优先考虑稳定的标准库接口或归并类方案,同时计入临时数组的内存预算。
- 内存严格受限且要求最坏
O(n log n):可考虑迭代堆排序,代价是它不稳定。 - 使用快速排序:要评估分区失衡和递归深度,不能只依赖平均复杂度。
通用业务代码优先使用标准库,通过 Comparator 明确业务顺序。以上是根据算法机制给出的筛选思路,不是性能测量结论。
6. Comparator 必须自洽
Comparator 是比较器,用来定义两个对象的先后关系:返回负数表示第一个在前,返回 0 表示两者在此排序规则下等价,返回正数表示第一个在后。排序算法依赖这些判断相互一致。
下面都是局部表达式,依赖调用方定义具有 score()、createdAt() 方法的 Order 类型,并导入 java.util.Comparator。反例:
java
(a, b) -> a.score() >= b.score() ? 1 : -1分数相等时,交换参数仍返回 1,甚至对象与自身比较也返回 1,无法形成一致的顺序。正例:
java
Comparator.comparingInt(Order::score)
.thenComparingLong(Order::createdAt)这个比较器先按分数升序,分数相等再按创建时间升序;它定义了次级排序键,不是依靠稳定性保留输入顺序。两个字段都相等时,稳定排序才会保留它们的原相对顺序。
不要用 a - b 比较整数,差值超出 int 范围时可能溢出并改变符号,应使用 Integer.compare(a, b)。
比较器至少应满足以下约束:
- 反对称性:交换参数后,结果符号应相反;对象与自身比较应为 0。
- 传递性:如果 A 在 B 前、B 在 C 前,那么 A 应在 C 前。
- 等价关系一致:如果 A 与 B 比较为 0,它们分别与任意 C 比较时,结果符号应相同。这里的“等价”是排序规则上的等价,不要求两个对象的所有字段都相同。
比较器不自洽时,排序结果可能错误,某些实现还可能抛出违反比较契约的异常。比较期间,参与比较的字段也应保持不变,否则同一对对象的判断可能前后矛盾。
7. 内存放不下时:外部排序
外部排序是把不能同时放入内存的数据分批排序,并借助外部存储合并结果。当数据无法整体放入 JVM 堆时,即使采用原地排序,也解决不了输入本身占用的内存。常见过程如下:
- 按内存预算读取数据块并分别排序;
- 将有序块写入临时文件;
- 使用小顶堆执行多路归并;
- 控制打开文件数、顺序 I/O、临时空间和失败清理。
多路归并同时合并多个有序块:每个块只把当前最小的未读记录放入小顶堆,取出堆顶后,再补入该记录所属块的下一条。因为各块内部有序,这些候选中的最小值就是所有剩余记录中的最小值。
归并路数指一次合并的有序块数量。路数越多,需要同时维护的读取缓冲区和打开文件也越多;超过资源预算时要分多轮归并。块大小则受可用内存限制,还要为排序临时空间和缓冲区留出预算。
这类任务常受磁盘 I/O(读写)限制;数据跨节点时还需计入网络 I/O。块大小、归并路数和读写轮数往往比单次比较的常数更值得先检查,但实际瓶颈仍需测量。
8. 如何验证选型
先验证正确性,再比较性能。可按 A - 算法正确性、测试与基准方法做性质测试,即检查不同输入下都应成立的约束:
- 有序性:相邻元素满足比较器定义的顺序。
- 元素守恒:排序前后每种元素的数量不变,不能只检查是否有序。
- 稳定性:仅对承诺稳定的实现,检查比较为 0 的记录是否保留原相对顺序。
正确性测试应覆盖空数组、单元素、随机、已有序、逆序和大量重复值。性能测试至少覆盖这些典型数据分布,以及基本类型与对象类型;每轮应使用相同的初始输入,避免把前一次排序的结果作为下一次输入。
同时观察吞吐(单位时间完成的工作量)、分配率(单位时间分配的内存量)、GC(垃圾回收)与尾延迟(较慢那部分请求的延迟)。记录输入规模、比较器成本、JDK、硬件、预热方式和重复测量方法,才能解释差异。
“某算法更快”必须绑定输入分布、数据类型、JDK 和硬件。
9. 容易踩的坑
- 忽略稳定性,导致相等元素顺序变化。
- 对已经有序的数据仍反复全量排序。
- 手写排序没有处理重复值和递归深度。
- Comparator 不满足反对称性或传递性。
- 把内存排序用于无法装入内存的数据,应考虑外部排序。
- 把当前 JDK 的内部排序实现当成长期不变的 API 契约。
10. 总结
排序选型取决于稳定性、最坏情况、空间限制和数据分布,而不是只看平均复杂度。
- 稳定性可能直接承载业务顺序语义。
- 标准库通常优于临时手写实现,但要理解其类型与版本边界。
- 比较器契约错误会让任何优秀排序算法都失去正确性。
下一篇:Top K 与堆。排序形成的有序边界还会用于区间问题统一解法和贪心算法与正确性证明。