解题思路 - 912 排序数组

考点归类

分治法（Divide and Conquer）· 原地双指针划分（Hoare Partition）。大厂高频面试手撕题，用于考察基础算法功底、边界控制以及防退化工程意识。

思路推导

1. 为什么“朴素快排”在 LeetCode 912 会遭遇惨败？

很多同学初学快排时，常写出如下开辟新数组的写法：

const quickSort = (arr) => {
    if (arr.length <= 1) return arr;
    const pivot = arr[0];
    const left = [], right = [];
    for (let i = 1; i < arr.length; i++) {
        arr[i] > pivot ? right.push(arr[i]) : left.push(arr[i]);
    }
    return [...quickSort(left), pivot, ...quickSort(right)];
}

该写法在 LeetCode 912 会死在两处：

MLE（超内存）：每层递归都 slice 或 push 新数组，额外空间开销达到 $O (n)$ 甚至 $O (n^{2})$ 。
TLE / 爆栈：
- 固定取 arr[0]：遇到已排序数组，每次只能削减 1 个元素，递归深度退化到 $O (n)$ ，耗时 $O (n^{2})$ ；
- 面对全同数组（如 50000 个 2）：arr[i] > pivot 全为 false，所有元素滚入 left，切分彻底失衡。

2. 优化关键：Hoare 原地对撞双指针

要在 $O (1)$ 额外辅助空间内完成重排，必须使用东尼·霍尔（Tony Hoare）提出的两头对撞双指针分区：

随机选取基准值：pivot = nums[randomIndex]，打破特定输入构造的针对性，将期望复杂度稳定在 $O (n lo g n)$ 。
两头夹逼：
- 左指针 $i$ 自左向右，遇到 >= pivot 的元素停下；
- 右指针 $j$ 自右向左，遇到 <= pivot 的元素停下；
- 若 $i \leq j$ ，原地交换两个违规元素 [nums[i], nums[j]] = [nums[j], nums[i]]，并各推进一步 i++, j--。
全同元素不退化的秘密：注意内层循环是严格小于/大于 nums[i] < pivot 和 nums[j] > pivot。当遇到大量相同元素时，两边指针都会停下来并互相交换，这看似做了“多余的交换”，实际上迫使左右指针以均匀步频向中央汇聚，将全同数组对半平分！

3. 分割边界判定

当 while (i <= j) 终止时，指针必然满足 $j < i$ （即两指针相互穿过）。此时数组被完美切分成两部分：

$[l, j]$ ：所有元素均 $\leq p i v o t$ ；
$[i, r]$ ：所有元素均 $\geq p i v o t$ 。因此下一步只需递归 quickSort(l, j) 和 quickSort(i, r)，无需关注 pivot 原始索引所在的位置。

算法快速记忆法（速记口诀）

快排避坑四句诀

基准随机偏移 l：Math.random() * (r - l + 1) + l，必须加区间起点 + l（防偷区间外的数），随机化防退化；

双针对撞 i 到 j：外层 while (i <= j)，内层移动的是双指针，切莫手抖写成固定区间 while (l <= r)；

内层严格无等号：nums[i] < pivot 与 nums[j] > pivot 严格比较，遇全同数两边停下互换，强制平分区间；

错开两截定边界：循环结束必然指针交叉错开（ $j < i$ ）—— 左段配小 $j$ （quickSort(l, j)），右段配大 $i$ （quickSort(i, r)），切忌碰 randomIndex，更不可写反 (l, i) 导致原地打转爆栈！

完整代码

/**
 * 原地快速排序（Hoare 分区 + 随机化基准）
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    function quickSort(l, r) {
        // 递归基：区间单元素或空区间已然有序
        if (l >= r) return;
 
        // 1. 随机基准：防升序/降序极端用例退化 O(n^2)
        const randomIndex = Math.floor(Math.random() * (r - l + 1)) + l;
        const pivot = nums[randomIndex];
 
        let i = l, j = r;
 
        // 2. 双指针两头对撞扫描
        while (i <= j) {
            // 严格小于/大于：相等元素停下做交换，防止全同数据倾斜
            while (nums[i] < pivot) i++;
            while (nums[j] > pivot) j--;
 
            if (i <= j) {
                // 原地交换，两指针推进
                [nums[i], nums[j]] = [nums[j], nums[i]];
                i++;
                j--;
            }
        }
 
        // 3. 递归解决子问题：循环退出后必然 j < i，切分为 [l, j] 与 [i, r]
        quickSort(l, j);
        quickSort(i, r);
    }
 
    quickSort(0, nums.length - 1);
    return nums;
};

复杂度分析

时间复杂度：平均 $Θ (n lo g n)$ 。在引入随机基准后，最坏情况退化为 $O (n^{2})$ 的概率降至数学上可忽略的极低概率。
空间复杂度： $O (lo g n)$ 。严格原地（In-place）交换，除了系统递归调用栈消耗外，辅助数组空间为 $O (1)$ 。

易错点剖析

递归边界传参：切忌写成 quickSort(l, randomIndex - 1) 或 (randomIndex + 1, r)！因为在 while 循环交换中，randomIndex 原位置上的数字早已被移走，真正的分割边界是交错后的 j 和 i。
内层 while 比较运算符不要带等号：如果写成 nums[i] <= pivot，当遇到整个数组全相等的用例（例如 [2, 2, 2, ...]）时， $i$ 会一路越界狂飙，且划分完全失效直接退化。
外层循环为 i <= j：必须保证指针错开（即 $j < i$ ）才能安全结束，避免当 $i === j$ 退出后左右区间产生重叠或无限递归。

变体与举一反三

215. 数组中的第K个最大元素：快速选择（QuickSelect）——基于快排分区思想，每次只递归包含目标排名的单边子区间，将平均时间优化至 $O (n)$ 。
75. 颜色分类：三路划分（三向切分 / 荷兰国旗问题）——把数组划分为 < pivot、=== pivot、> pivot 三段，是重复元素较多场景下的另一经典利器。
148. 排序链表：链表形态下的排序，归并排序相比快排更自然，因为链表合并仅需调整指针无需开辟数组。

← 速查卡片见经典 150 分治

description	912 排序数组（手撕快速排序）：原地 Hoare 双指针分区、随机化基准防退化、重复元素处理与调用栈分析
tags	leetcode, 经典150, 分治, 快速排序, 双指针
aliases	排序数组详解, 手撕快速排序详解

unbrain · 算法学习 Wiki & 个人档案

探索