排序算法

每个候选人都「会」排序——直到面试官问起,你知道的这些排序里哪些是稳定的,或者你的快排为什么突然退化成了平方级。第 2 课把整套家谱都走一遍——bubble、insertion、selection、merge、quick、counting、bucket、radix、heap、topological——但真正的大纲是排序「教会」你的东西:双指针代码里的区间不变式、把稳定性看成 swap 还是赋值的问题、递归形状(归并先递归,快排先 partition)、以及给任何分治定价的 master theorem。之后这节课把递归这面镜子对准斐波那契、爬楼梯和 Pow(x, n)——在这些题里,一个缓存变量就是 O(n) 和 O(log n) 的全部差距。

一个 comparator,九种算法

这节课开场是一个看似不起眼的观察:排序算法从来不知道「更大」是什么意思——顺序完全取决于你的 comparator。partition、merge、swap 都是通用机器,顺序是被注入进去的。这就是为什么 LC 179 Largest Number 暗地里是一道排序题,而你只需要写一个 comparator:要从 [3, 30, 34] 拼出最大的数,把这些值当字符串按 a+b > b+a 排序,剩下的交给任意一个 O(n log n) 排序。当面试官丢给你「按某个奇怪规则排序」,答案几乎从来不是一个新算法——而是一个 comparator。

这节课的点名册:1) bubble,2) insertion(外加它的 shell 变种),3) selection,4) merge,5) quick,6) counting/bucket,7) radix,8) heap,9) topological。头两个一口气带过:冒泡排序比较相邻两个,内层循环缩到 arr.length - i,因为尾巴已经排好了;插入排序养出一段有序前缀,把每个新元素向左下沉到位。都是 O(n²),都是热身。

两项需要澄清。堆排序不是「用堆来排序」——把所有东西塞进 PriorityQueue 再一个个 poll 出来确实能排,但那是个多花 O(n) 空间的取巧;真正的堆排序在原地把数组 heapify。而拓扑排序根本不是基于比较的排序——它把一个 DAG(有向无环图)的依赖边线性化,所以它归在图的课里,而不在这儿。

选择排序:先想清楚指针停在哪

思路一句话:在剩下的数里选出最小的,再 swap 到位。这节课真正操练的,是一个被称作「站肩」(两个指针踩在彼此肩膀上)的纪律:在写下任何一行循环之前,先确定循环结束时每个指针必须停在哪。这里,外层指针 i 停在倒数第二个就够了——一旦它前面全都安顿好,剩下的单个元素按定义就是有序的。内层指针 j 永远从 i + 1 开始,一直跑到末尾。

public int[] selectionSort(int[] arr) {
    if (arr == null || arr.length <= 1) return arr;
    for (int i = 0; i < arr.length - 1; i++) {   // i 停在倒数第二个——最后一个天然有序
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        swap(arr, i, minIndex);                  // 和 minIndex 交换——不是那个游走的 j
    }
    return arr;
}

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

时间复杂度 O(n²),但面试时要说出精确版本:比较次数是 (n−1) + (n−2) + … + 1,一个等差数列。空间 O(1),还有个值得主动交代的细节——选择排序最多做 n−1 次 swap,当 swap 代价昂贵时这一点很关键。一个经典翻车点:拿游走的 j 而不是 minIndex 去 swap,编译毫无问题,却什么都排不好。

归并排序:先递归,回溯时才排序

归并排序是分治的教科书范例:把大问题拆成小问题,再用同样的方法解决它们。这节课对递归的概括值得引用:递归的核心在于「访问」和「处理」的顺序是反的。归并排序一路递归到底才开始干真正的活——排序发生在回溯的路上,随着调用栈一层层弹出。递归 → 栈 → 树遍历:归并排序的递归树本质上就是一次后序遍历,把过程画出来一目了然。拿 6 4 2 0 | 1 3 5 7:divide 阶段一直拆到单个元素——base case,再也没法分了——然后 conquer 阶段把成对的元素拉链式合并回去:4 6、0 2、1 3、5 7,接着 0 2 4 6 和 1 3 5 7,最后是完全有序的整体。conquer 这一步正是 comparator 决定优先级的地方——这也是 LC 179 能如此自然地骑在归并排序背上的原因。

public class MergeSort {
    private int[] numbers;
    private int[] helper;   // 只分配一次——不是每次 merge 都 new

    public void sort(int[] values) {
        this.numbers = values;
        this.helper = new int[values.length];
        mergeSort(0, values.length - 1);
    }

    private void mergeSort(int low, int high) {
        if (low < high) {                        // base case:只剩一个元素,无法再分
            int middle = low + (high - low) / 2;
            mergeSort(low, middle);              // 先递归……
            mergeSort(middle + 1, high);
            merge(low, middle, high);            // ……回溯时才干活
        }
    }

    private void merge(int low, int middle, int high) {
        for (int i = low; i <= high; i++) helper[i] = numbers[i];
        int i = low, j = middle + 1, k = low;    // j = middle + 1,经典的差一位现场
        while (i <= middle && j <= high) {
            if (helper[i] <= helper[j]) {        // <= 保持相等元素的原有顺序 → 稳定
                numbers[k++] = helper[i++];
            } else {
                numbers[k++] = helper[j++];
            }
        }
        while (i <= middle) numbers[k++] = helper[i++];
        // 右半边剩余元素已在最终位置——无需拷贝
    }
}

时间:树的每一层做 O(n) 的合并工作,共有 log n 层 → O(n log n),对任何输入都有保证。空间:递归栈是 O(log n)。helper 看着更吓人——log n 层 × 每层 O(n),像是 O(n log n)——但递归是一次 DFS:任一时刻只有一条从根到叶的路径活着,所以即便你每次调用都 new 一个新缓冲区,垃圾回收也会把峰值压在 O(n)。而最佳实践正是上面代码所做的:一开始就分配一个 helper 数组并复用它。

两个面试官爱抠的 merge 细节:为什么 j = middle + 1(右半边从 middle 之后开始——写成 middle 会把一个元素数两遍),以及为什么末尾那个拷贝循环只处理左半边(右半边任何剩余元素都已经躺在它们的最终位置上了)。

快排:先 partition,再递归

这节课把快排概括为:通过反复递归地解 sort2 来解 sortK——它的递归形状是归并排序的镜像:先排序,后递归。选一个 pivot,把它停到最后一个位置,然后让两个指针相向而行:left 从第一个元素开始,right 从倒数第二个开始。左指针去找那些应该待在另一侧的元素(≥ pivot),右指针去找 < pivot 的元素;两边都卡住时,swap 一下再各走一步。当 left 越过 right,把 pivot swap 到 left 的位置。

让这段代码不出 bug 的纪律是区间不变式。在任意时刻:[lo, i) 装着 < pivot 的元素(已完成),[i, j] 尚未探索,(j, hi−1] 装着 ≥ pivot 的元素(已完成)。每一步循环都必须维持这三句话——只要你能背出它们,就能在高压下把代码重新推导出来。

private Random rand = new Random();

private void quickSort(int[] arr, int lo, int hi) {
    int pivotIndex = lo + rand.nextInt(hi - lo + 1);   // 随机 pivot 守住平均情况
    int pivot = arr[pivotIndex];
    swap(arr, pivotIndex, hi);                         // 把 pivot 停到末尾

    int i = lo, j = hi - 1;
    // 不变式:[lo,i) < pivot | [i,j] 未探索 | (j,hi-1] >= pivot
    while (i <= j) {
        while (i <= j && arr[i] < pivot) i++;          // 左指针找一个大的
        while (i <= j && arr[j] > pivot) j--;          // 右指针找一个小的
        if (i <= j) swap(arr, i++, j--);
    }
    swap(arr, i, hi);                                  // pivot 落到它的最终下标

    if (lo < i - 1) quickSort(arr, lo, i - 1);
    if (i + 1 < hi) quickSort(arr, i + 1, hi);
}

要记住的那句话:每一轮之后,pivot 恰好就在它在最终有序数组里的位置上。这一个事实本身就是一整个算法的雏形——快速选择:如果你只需要第 k 个元素,就只递归进一侧,另一侧整个跳过(它会在第 12 课再登场)。

时间:pivot 选得好时递推是 T(n) = 2T(n/2) + O(n) → O(n log n),这既是最好也是平均情况。pivot 选得差时——比如在已经有序的数组里永远挑第一个元素——总有一侧是空的,你就得付 O(n²)。两种防御:随机挑 pivot(如上),或者采样 4–5 个候选取它们的中位数。空间:辅助空间 O(1);算上递归栈,最好情况 O(log n),最坏 O(n)。

两种 partition 范式——以及 LC 283

相向的 left/right 只是 partition 的一种方式。另一种是同向的 slow/fast:[0, slow) 装 < pivot 的元素(已完成),[slow, fast) 装 ≥ pivot 的元素(已完成),[fast, …] 尚未探索。fast 指针向前扫描找小元素;每找到一个,就把它 swap 回 slow,然后两个指针一起前进。最后,把 pivot swap 进 slow。这节课把这个选择压缩成一句值得记住的口诀:相向的 left/right → 不用想直接写 while;同向的 slow/fast → 不用想直接写 for。

它还点名了写任何指针代码之前要回答的三个问题:每个区间是什么含义,每个指针是什么含义,以及每个边界是开还是闭。大部分 partition bug 都是这三个问题里有一个没答。

这个套路也能适配重复元素:在一个像 0 1 1 0 0 1 1 0 的 0/1 数组上,partition 条件干脆变成「它是 0 还是 1」——这恰好是 LC 283 Move Zeroes 的无序版本:如果你不在乎相对顺序,就用一对相向指针把所有 0 赶到右边:

public int[] moveZeroes(int[] nums) {
    if (nums == null || nums.length <= 1) return nums;
    int left = 0, right = nums.length - 1;
    // [0,left) 非零 | [left,right] 未探索 | (right,n-1] 零
    while (left < right) {
        if (nums[left] != 0) left++;             // 用 if,不是嵌套 while——那会冲出边界
        else if (nums[right] == 0) right--;
        else swap(nums, left++, right--);
    }
    return nums;
}

注释是这节课的原话警告:用嵌套 while 而不是 if 来推进,会让一个指针「飞出去」越过另一个,因为内层循环不再重新检查 left < right。而 if/else 链每一步都重新测一遍守卫条件。(真正的 LC 283 要求你保持相对顺序——那就得用 slow/fast 版本,它靠赋值把非零元素向前挪,而它稳定的原因恰好就是下一节要讲的。)

稳定性:swap 破坏它,赋值保住它

拿 5a 5b 2a 2b——两对键相等的元素,按它们原始的顺序打上标签——按数值排序。稳定排序必须输出 2a 2b 5a 5b。快排给不了这个保证:它的长距离 swap 把一个元素瞬移到数组另一头,顺手就把 2b 甩到了 2a 前面。归并排序从不 swap——它按遇到的顺序把元素赋值进输出,而它的 <= 比较遇到相等时总是先取左边那份。这节课的经验法则可以推广:基于 swap 的排序(selection、quick、heap)不稳定;基于赋值的排序(insertion、merge、counting)稳定。

为什么有人在乎:多关键字排序。先把员工按姓名排,再按部门做稳定排序——每个部门内部姓名依然有序。而马上要讲的基数排序,就是搭在稳定这一趟趟之上的;换成不稳定的内层排序,它根本不工作。

JDK 到底用了什么

Java 标准库就是这个取舍的活案例。对基本类型数组,Arrays.sort 用的是调优过的快排(JDK 6 及更早)或双轴快排(JDK 7+)——都是 O(n log n),双轴版本通常更快。对对象数组,它用的是改良版归并排序:稳定,即便最坏情况也是 O(n log n),数组部分有序时更快。理由就是上面那套稳定性的说法:两个相等的 int 无法区分,稳定性因此毫无意义,纯速度胜出;两个「相等」的对象却仍可能是不同的对象,重排它们是可被观察到的行为。能答上「Arrays.sort 到底跑的是什么?」是个廉价的显资深的办法。

突破 O(n log n):counting、bucket、radix

基于比较的排序无法突破 O(n log n)。线性时间的那几种排序绕过它的办法是压根不比较——但入场费是,序列必须有结构,比如取值被限制在一个已知的小范围内,像 1–5。

计数排序:对范围 1–5 的 1 3 5 2 2 4 3 5 1 2,维护一个 int[5] 计数器——count(1)=2、count(2)=3、count(3)=2、count(4)=1、count(5)=2——然后按顺序把这些计数重放出来。一趟数数,一趟写回:O(n) 时间,O(range) 空间。

桶排序:同样的思路,但每个桶保留实际的元素(List<List<Integer>>),所以当值带着负载、或需要桶内再排序时它也能用。桶均衡时仍是 O(n)。

基数排序:对多位数字,每一位做一趟稳定排序,从最低位开始。对 123 254 120:个位那趟给出 120 123 254,十位那趟保持 120 123 254,百位那趟确认 120 123 254。d 位数字就是 O(d·n)——注意那个依赖:每一趟都必须稳定(内层引擎通常就是计数排序),否则前面几位排好的功夫会被打乱。这就是稳定性在交房租,就在我们定义它的一节之后。

给递归定价:master theorem

这节课的两半——那些 O(n log n) 排序,和随后的递归题——由同一个公式定价。对形如 T(n) = a·T(n/b) + O(n^k) 的递推,拿 c = log a / log b 和 k 比较:

• 若 c > k——叶子主导:T(n) = O(n^c)。
• 若 c < k——根部主导:T(n) = O(n^k)。
• 若 c = k——每一层花费相同:T(n) = O(n^k · log n)。

这节课的三个例子:T(n) = 3T(n/3) + O(n) 有 c = 1 = k → O(n log n)。T(n) = 3T(2n/3) + O(1) 有 c = log 3 / log 1.5 ≈ 2.7 > k → O(n^2.7)。T(n) = 4T(n/2) + O(n) 有 c = 2 > 1 → O(n²)。而要内化的是这个:T(n) = 2T(n/2) + O(n)——归并排序永远如此,快排在最好情况下如此——落在 c = k = 1 这一支,因此是 O(n log n)。当面试官问「归并排序为什么是 n log n?」,master theorem 就是那句一行答案;递归树的图景(每层 n 的工作量,共 log n 层)是它背后的直觉。

递归入门:斐波那契与爬楼梯

递归函数不过是一个调用自己的函数,这节课把它们归成两种轮廓:sol(n) → sol(n−1), sol(n−2)——线性递归——和 sol(n) → sol(n/2)——分治。写法的配方永远是同样两样东西:一个 base case(一个空链表、一棵空树、一个平凡的 true/false)和一条递归规则——f(n) = F(f(n−1))。

LC 70 Climbing Stairs 是最干净的标本:sol(n) = sol(n−1) + sol(n−2),base case 是 sol(0) 和 sol(1)。自顶向下解,它是递归的胚胎;自底向上解——从 base case 出发,朝目标一步步搭——它是动态规划的胚胎。两种方式的 base case 完全一样;变的只是行进方向。

斐波那契数列(0 1 1 2 3 5 8 13 21 34 55 89 144…)展示了方向为什么要紧。画出 fib(5) 的递归树:fib(3) 出现两次,fib(2) 三次——到处是重复的值,不存下来就是白算。每层的宽度是 1, 2, 4, …,所以朴素版本要花 O(2ⁿ)。要么给自顶向下的版本加 memoization,要么干脆走自底向上:

// 朴素:T(n) = T(n-1) + T(n-2) → O(2ⁿ)——递归树反复重算 fib(3)、fib(2)……
public long fibNaive(int n) {
    if (n < 0) throw new IllegalArgumentException();
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// 自底向上:转移只碰 i-1 和 i-2 → 两个变量足矣。O(n) 时间,O(1) 空间
public long fib(int n) {
    if (n <= 0) return 0;
    long fib1 = 0, fib2 = 1;   // f(i-2), f(i-1)
    for (int i = 2; i <= n; i++) {
        long sum = fib1 + fib2;
        fib1 = fib2;
        fib2 = sum;
    }
    return fib2;
}

这节课精准地给自底向上的世界观命了名:动态规划就是数学归纳法。归纳规则就是状态转移方程——mem[i] = mem[i−1] + mem[i−2]——而 mem[n] 在推进过程中被存下来。它还递给你一个标准的优化动作:DP 的时间复杂度通常难以压缩,那就压空间——读状态转移方程,看它实际碰到哪些状态(这里:只有 i−1 和 i−2),然后砍掉那一维:O(n) 空间变 O(1),数组变成两个变量。这个动作——降维——是 DP 课里反复出现的技巧。

LC 50 Pow(x, n):一个缓存变量,两个复杂度等级

实现 myPow(x, n)。解法 1 把 x 连乘 n 次——O(n),没问题,无聊。解法 2 看着像分治:myPow(x, n/2) * myPow(x, n − n/2),把 n 劈成两半(n − n/2 处理 n 为奇数的情况)。面试陷阱来了:它仍然是 O(n)。两次未缓存的递归调用意味着节点数每层翻倍——1, 2, 4, …, 2^(log n) ≈ n 个节点,每个做 O(1) 的活。劈开这个问题什么都没换来,因为两半各自独立地算出了同一个值。

解法 3 只改一行:把那一半算一次,存进一个变量,再平方。递归树坍缩成一条 log n 帧的链:

public double myPow(double x, int n) {
    if (n == 0) return 1;
    if (n < 0) {
        if (n == Integer.MIN_VALUE) {   // -n 会让 int 溢出——先剥掉一个因子
            n++;
            n = -n;
            x = 1 / x;
            return x * myPow(x, n);    // 多出来的 x 补上被剥掉的那个指数
        }
        n = -n;
        x = 1 / x;
    }
    double tmp = myPow(x, n / 2);      // 缓存那一半——关键优化
    return (n % 2 == 0) ? tmp * tmp : x * tmp * tmp;
}

负指数的处理是筛掉候选人的地方。自然的动作——n = −n; x = 1/x——藏着一个溢出:Integer.MIN_VALUE 是 −2,147,483,648,取负后放不进 int。修法:把 n 加一次(剥掉单独一个 1/x 因子),对现在安全的值取负,再把那个剥出来的因子乘回到递归调用前面。这恰好是这节课排序那一半的缓存教训和 corner case 教训,压缩进了十行代码。

刷题清单