排序算法入门（五）：怎么选 —— 复杂度、稳定性与工程实践

前四篇把冒泡、选择、插入、快排、归并、堆排逐个看过了。真写业务代码时，问题从来不是“堆排怎么实现”，而是“这里该用哪个”。我的做法是先问三件事：数据量级多大、结果要不要稳定、对最坏时间和额外内存有没有硬约束。下面这张表是复习时整理的总账。

几处容易记错。冒泡最好 O(n) 靠“一趟没有交换就提前结束”，不带标记位它恒为 O(n²)；选择排序的比较次数恒为 n(n-1)/2，唯一优势是交换少；插入排序近乎有序时是 O(n)，JDK 的小数组也切成它。快排的 O(log n) 是递归栈，已有序又固定取首元素当 pivot 仍会退化成 O(n²)。

稳定性到底什么时候要

定义是：比较相等的两个元素，排序后相对次序不变。两类场景里它是硬需求。

一是两遍排序。工单列表要求“按状态分组、组内按创建时间从早到晚”，常见写法是先按时间排一遍，再按状态排一遍。第二遍若不稳定，第一遍排好的时间顺序会在同一状态内部被打乱——快排的分区和堆排的建堆都会搬动相等元素。

二是链式 Comparator。Comparator.comparing(...).thenComparing(...) 把多个键合成一个全序，只要任一键分出胜负，先后就唯一确定，与算法稳不稳定无关；真正吃稳定性的是最后一层——所有键都相等时，稳定排序保证输出顺序等于输入顺序，分页和“结果可复现”的测试断言都靠它。

JDK 里到底用了什么

很多人以为 Java 的 sort 就是快排，实际上按元素类型分了两条路。

基本类型数组，Arrays.sort(int[]) 以及 long[]、char[]、double[] 等，走 DualPivotQuicksort：双轴快排用两个 pivot 把区间切成三段，短数组切成插入排序，递归过深时切堆排序，最坏压回 O(n log n)。

对象数组与集合，Arrays.sort(Object[])、Arrays.sort(T[], Comparator)、Collections.sort、List.sort，走 TimSort：先扫出天然有序的 run，过短的用插入排序补到最小长度再归并，归并的本质决定了它是稳定的。Arrays.parallelSort 则是 Fork/Join 的并行归并，数组够大才真的拆线程。

为什么这么分？基本类型没有“身份”，两个 int 相等就是同一个值，交换它们没有可观察的差别，不必为稳定性付代价。对象则可能 compareTo 返回 0 却是两个不同实例，带着别的字段、可能已被别处引用；打乱它们会让“先按时间排、再按状态排”失效，用户看到的顺序也会变。

决策清单

• 几十个元素：直接用 Arrays.sort / list.sort，别自己写。
• 要稳定：对象排序用 List.sort / Arrays.sort(T[]) / Arrays.sort(T[], Comparator)，都是 TimSort；自己实现就用归并。
• 内存极紧且最坏要可控：堆排序，O(1) 空间、恒 O(n log n)，代价是缓存不友好、不稳定。
• 数据近乎有序：插入排序，接近 O(n)。
• 只要前 K 个：别全排，用大小为 K 的堆扫一遍是 O(n log K)。
• 整数且值域小：计数排序 O(n+k)；位数少的长整数用基数排序，值域一大收益就被 k 吃掉。
• 通用且不在乎稳定：快排，随机化 pivot 防退化，常数最小。

常见坑

Comparator 不满足传递性。 现象是 Arrays.sort(list, cmp) 抛 IllegalArgumentException: Comparison method violates its general contract!，常在数据量涨上来后才出现。起因多为两种：(a, b) -> a.value - b.value 在 a.value 为 Integer.MIN_VALUE、b.value 为正数时溢出，符号反了；比较键取自外部可变状态（时间戳、随机数、别处正在改的字段），排序中键自己变了，比较自然不自洽。TimSort 在归并和二分插入时会检查比较关系的自洽性，能发现“a 该在 c 前却排在后面”的矛盾并报错；快排只做分区、从不检查，坏 Comparator 在它手里往往“跑得挺正常”，只是顺序悄悄不对——这就是同一段代码换到 TimSort 才炸的原因。修法：用 Integer.compare / Comparator.comparingInt，别用减法，比较键在排序期间必须是不变量。

Arrays.asList(...) 拿到的是视图不是副本。 它是 Arrays 内部的固定长度 List：set 会写回原始数组，add、remove 抛 UnsupportedOperationException；对它调 sort 合法，但会就地改写你传进去的那个数组，很多人以为 asList 复制了一份。更隐蔽的是 Arrays.asList(new int[]{3, 1, 2}) 得到的是只有一个元素的 List<int[]>（泛型不自动装箱），排序毫无意义。

用 == 比较 Integer。 Integer.valueOf 缓存 -128 到 127 的实例（上限可用 -XX:AutoBoxCacheMax 调高），所以该区间内 Integer a = 100, b = 100 时 a == b 为 true，出界就是 false。Comparator 里用 == 判等、或直接比 Integer 字段，测试数据都是小数值时全绿，线上 id 到五位数就开始错。判等用 equals，比大小用 Integer.compare。

自定义对象没实现 Comparable。 现象是 Arrays.sort(arr) / Collections.sort(list) 抛 ClassCastException: class com.demo.Task cannot be cast to class java.lang.Comparable——Arrays.sort(Object[]) 内部把元素当 Comparable 强转，编译期不报错、运行期才炸。修法二选一：让类 implements Comparable<T>，或改调带 Comparator 的重载 Arrays.sort(arr, cmp) / list.sort(cmp)。集合里混放不同类型时，compareTo 同样会抛。

多字段稳定排序

下面这段能直接跑：status 主键、createdAt 次键，先用链式 Comparator 一次排完，再用“两遍排序”的写法对照。

import java.time.LocalDateTime;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class MultiKeySort {

    enum Status { PENDING, RUNNING, DONE }

    static class Task {
        final String id;
        final Status status;
        final LocalDateTime createdAt;

        Task(String id, Status status, LocalDateTime createdAt) {
            this.id = id;
            this.status = status;
            this.createdAt = createdAt;
        }

        Status getStatus() { return status; }
        LocalDateTime getCreatedAt() { return createdAt; }

        @Override
        public String toString() {
            return String.format("%-4s %-8s %s", id, status, createdAt);
        }
    }

    static List<Task> newTasks() {
        return new ArrayList<>(List.of(
                new Task("t1", Status.DONE,    LocalDateTime.of(2024, 5, 1, 9, 0)),
                new Task("t2", Status.PENDING, LocalDateTime.of(2024, 5, 3, 10, 30)),
                new Task("t3", Status.RUNNING, LocalDateTime.of(2024, 5, 2, 8, 15)),
                new Task("t4", Status.PENDING, LocalDateTime.of(2024, 5, 1, 20, 45)),
                new Task("t5", Status.DONE,    LocalDateTime.of(2024, 5, 4, 11, 0)),
                new Task("t6", Status.RUNNING, LocalDateTime.of(2024, 5, 2, 8, 15))));
    }

    public static void main(String[] args) {
        List<Task> tasks = newTasks();
        System.out.println("==== 排序前 ====");
        tasks.forEach(System.out::println);

        // 主键 status（按枚举声明顺序），次键 createdAt 升序。
        // List.sort 底层是 TimSort，稳定：t3 与 t6 两键全等，排完仍是 t3 在前。
        tasks.sort(Comparator.comparing(Task::getStatus)
                .thenComparing(Task::getCreatedAt));
        System.out.println("==== 链式 Comparator 排序后 ====");
        tasks.forEach(System.out::println);

        // 等价的两次排序写法：先按时间升序，再按状态升序。
        // 第二遍必须稳定，否则第一遍排好的时间顺序会在同一状态内部被打乱。
        List<Task> twice = newTasks();
        twice.sort(Comparator.comparing(Task::getCreatedAt));
        twice.sort(Comparator.comparing(Task::getStatus));
        System.out.println("==== 先按时间、再按状态排序后 ====");
        twice.forEach(System.out::println);
    }
}

输出里 t3 始终排在 t6 前面，两种写法结果一致——这不是 Comparator 的功劳，是 TimSort 稳定的功劳：换成不稳定排序，两遍写法的结果就会变。想要确定的先后，就让比较键唯一，别指望排序算法兜底。发现自己在实现排序时，先过一遍决策清单，多数时候是容器或数据结构选错了。