算法随笔：Morris 遍历、快速排序与荷兰国旗

这几种算法表面上没有共同点：一个遍历二叉树，一个排序数组，一个整理三种颜色。但它们都在做同一件事：用更精确的不变量管理原地修改，从而省掉额外空间或避免退化路径。写对主循环不难，真正容易出错的是“指针何时移动”“区间是否还包含边界”“临时结构何时恢复”。

Morris 中序遍历：借用右指针，再原样归还

二叉树中序遍历的常规写法需要递归栈或显式栈，空间是树高 O(h)。Morris Traversal 通过临时把当前节点的中序前驱右指针指回当前节点，建立一条返回路径；当第二次回到当前节点时，再把这条线索拆掉。于是整个过程只用 O(1) 额外空间。

LeetCode Hot 100 中的 94. 二叉树的中序遍历 可以用它完成。规则是：当前节点没有左孩子，访问自己并向右；有左孩子则找到左子树最右节点。若它的右指针为空，连回当前节点并向左；若已经连回当前节点，说明左子树已经处理完，断开连接、访问当前节点、再向右。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            ans.add(cur.val);
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                pred.right = cur;       // 第一次到达：建立返回线索
                cur = cur.left;
            } else {
                pred.right = null;      // 第二次到达：恢复树形结构
                ans.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return ans;
}

时间仍是 O(n)：虽然有寻找前驱的内层循环，但每条边至多被走常数次。最重要的约束是恢复 pred.right = null，遗漏它会改变原树结构，后续遍历可能陷入环。Morris 适合极端空间限制；日常业务代码若可读性优先，栈写法往往更合适。

Lomuto 分区与 LC 912 的退化问题

快速排序的核心不是“选一个 pivot 然后递归”，而是分区后建立区间不变量。Lomuto 分区把最后一个元素作为 pivot，扫描时维护 [left, i) 都小于 pivot，遇到小元素就扩展该区间；扫描结束后交换 pivot 到 i。

int partition(int[] a, int left, int right) {
    int pivot = a[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (a[j] < pivot) {
            int t = a[i]; a[i] = a[j]; a[j] = t;
            i++;
        }
    }
    int t = a[i]; a[i] = a[right]; a[right] = t;
    return i;
}

它非常容易理解，但对于 LeetCode 912. 排序数组，如果输入已接近有序、pivot 恰好总是最小或最大元素，分区会退化成 n-1 和 0，时间 O(n²)，递归深度也可能溢出。重复元素同样糟糕：所有等于 pivot 的元素会不断落入同一侧。

实践中的修正有三层：随机选择 pivot，优先递归较短一边以控制栈深度，以及使用三路分区把等于 pivot 的元素一次性跳过。后者特别适合 912 这类大量重复数字的输入。

三路快排与荷兰国旗不变量

三路分区维护四段：[left, lt) 小于 pivot，[lt, i) 等于 pivot，[i, gt] 尚未处理，(gt, right] 大于 pivot。扫描到小元素，交换到左区并同时移动 lt、i；扫描到大元素，交换到右区，只移动 gt，因为换过来的元素还没检查；相等时只移动 i。

void quickSort3(int[] a, int left, int right) {
    if (left >= right) return;
    int pivot = a[left + (int) (Math.random() * (right - left + 1))];
    int lt = left, i = left, gt = right;
    while (i <= gt) {
        if (a[i] < pivot) swap(a, lt++, i++);
        else if (a[i] > pivot) swap(a, i, gt--);
        else i++;
    }
    quickSort3(a, left, lt - 1);
    quickSort3(a, gt + 1, right);
}

荷兰国旗算法正是这个三分思想的更直接版本。LeetCode Hot 100 的 75. 颜色分类 中，数组只有 0、1、2；将 0 放左、2 放右、1 留在中间即可。它的关键细节是遇到 2 后不能移动当前指针，因为从右端交换来的数可能仍是 0 或 2。

public void sortColors(int[] nums) {
    int zero = 0, cur = 0, two = nums.length - 1;
    while (cur <= two) {
        if (nums[cur] == 0) swap(nums, zero++, cur++);
        else if (nums[cur] == 2) swap(nums, cur, two--);
        else cur++;
    }
}

写这类题时，不要只背交换顺序。先在纸上写出每个指针两侧分别代表什么，再检查每一种交换是否会把“未检查元素”带回当前位置。Morris 的线索、三路快排的等值区、荷兰国旗的中间区，本质上都是靠不变量把临时混乱控制在一个明确范围内。

为什么普通快排在 912 上经常翻车

题目本身不禁止 O(n²)，但测试数据会专门覆盖递增、递减、全相同、重复值极多与接近有序等输入。若总取首元素或末元素作 pivot，递增数组每轮只能把一个元素放到最终位置，递归树变成长度为 n 的链。Java 的递归栈随之加深，既会超时，也可能栈溢出。

随机 pivot 不是把最坏情况从理论上消灭，而是让对手难以稳定构造最坏输入；三路分区则真正改善重复值场景。工程实现还可以在小区间改用插入排序，并始终先递归较小半边、用循环处理较大半边，将额外栈深控制在 O(log n)。

void quickSortSafe(int[] a, int left, int right) {
    while (left < right) {
        int[] middle = partition3(a, left, right); // [left, middle[0]) < p, (middle[1], right] > p
        if (middle[0] - left < right - middle[1]) {
            quickSortSafe(a, left, middle[0] - 1);
            left = middle[1] + 1;
        } else {
            quickSortSafe(a, middle[1] + 1, right);
            right = middle[0] - 1;
        }
    }
}

这里的细节是区间长度比较，而不是随意选一边递归。把大区间留给 while，调用栈永远只保存较小区间。面试中写不出完整优化没有关系，但要能说明 Lomuto 对重复值的退化、随机 pivot 的目的和三路分区的收益。

三路分区最常见的指针错误

a[i] > pivot 时交换 a[i] 与 a[gt]，只能 gt--，不能 i++。因为右边换回来的新元素来自未知区，它还没有被归类。相反，a[i] < pivot 时与 lt 交换后可以移动两个指针：原 lt 位置必然属于等于 pivot 的区，换到 i 后无需再次检查。

可以用几个极小数组手推不变量：[2,0,1] 检查右侧交换后的重检；[1,1,1] 检查等值区是否一次完成；[0,2,0,2] 检查左右边界是否越界；空数组与单元素数组检查循环条件。原地算法的正确性大多藏在这些最小反例里。

Morris 遍历的另一种视角

Morris 并不是“没有栈”，而是把本来压进栈的返回信息暂时编码进树的空指针。中序遍历在第二次遇到节点时访问自己；先序遍历则在第一次建立线索时访问自己。后序遍历更复杂，需要在第二次遇到节点时反转一段右边界并恢复，因此它很适合检验对线索恢复的理解。

它也揭示了一个工程取舍：为了 O(1) 额外空间，算法会短暂修改输入结构。若树可能被并发读取、异常中断后无法保证恢复、或可读性比常数空间更重要，显式栈通常更安全。复杂度从来不是唯一指标；可恢复性和副作用范围同样是算法设计的一部分。

用不变量审查代码

写完之后，可以逐条问自己：循环开始时，哪些区间已经确定？每一个分支结束后，这个条件仍成立吗？退出时，未处理区是否为空？Morris 的前驱指针是否都被清空？三路快排的递归区间是否严格缩小？颜色分类中 cur 是否只越过已检查元素？

这种审查方式比记住模板更可靠。模板换成 Hoare 分区、双指针去重或链表分割后，不变量依旧能带路；只要能说清每个指针守护的区域，就能在边界变化时自己推导出代码。

复杂度之外还要看数据分布

同样标注为平均 O(n log n) 的快排，在不同数据分布下表现差异很大。全相等数组是检验分区策略的试金石：Lomuto 会反复处理几乎完整的区间，三路分区一次就把所有元素放进等值区。近乎有序数组则提醒我们 pivot 选择不能依赖位置。算法题里的随机化不是装饰，它是在输入未知甚至可能带有对抗性时，避免确定策略被轻易击穿。

对于 912，库排序通常更稳妥，因为生产级实现会结合插入排序、堆排序兜底与缓存友好的细节；手写快排的意义在于掌握分区、递归边界与退化原因。面试要求“原地排序”时，再根据重复值比例与最坏情况约束选择双路或三路方案。

一组值得保留的测试

任何排序实现至少跑过：空数组、一个元素、两个逆序元素、全部相同、严格递增、严格递减、含负数、极大重复值与随机长数组。将结果和 Arrays.sort 对拍，是发现边界错误的高效办法。树遍历则可构造只有左链、只有右链、完全树和左右子树交错的树，遍历后再次检查树结构没有被修改。

这些测试不是为了凑覆盖率，而是在验证不变量是否经得住最容易错的边界。能主动构造反例，才算真正掌握了原地算法。