JavaScript 快速排序递归实现原理与代码示例

一、快速排序的核心分治思想

在各类经典的内部排序算法中，快速排序以其优秀的平均时间复杂度 O(N log N) 与极低的原地常数空间消耗成为工程领域最广泛应用的排序算法之一。理解快速排序的关键在于把握其“分治”（Divide and Conquer）的三个标准阶段：

1. 选取基准（Pivot Selection）：从待排序数组的当前区间中选出一个元素作为参考基准。
2. 分区操作（Partitioning）：通过双指针从区间两端向内探测，把所有小于基准值的元素重排至基准左侧，所有大于基准值的元素重排至基准右侧。分区完成后，该基准元素已处于其在整个数组排序后的最终位置，无需再次移动。
3. 递归求解（Recursive Sorting）：以基准元素的落脚点为界，将原区间拆分为左右两个独立的子区间，分别对子区间递归调用快速排序函数。

递归必须设定明确的基线条件（Base Case）：当待排序区间的起始索引 left >= right 时，说明当前子区间仅剩 1 个元素或为空区间，本层函数直接返回。此时，随着调用栈的层层回溯，原数组已经在原地完成了完整的升序排列。

二、原地分区原理与双指针移动步骤

初学者在初次接触快速排序时，常会尝试使用 Array.prototype.filter() 搭配展开运算符创建新数组来切分左右子集。这种写法虽然形式直观，但在每次递归调用中都会开辟新的堆内存空间，导致空间复杂度飙升至 O(N log N)，并伴随频繁的垃圾回收（GC）损耗，彻底丧失了快速排序“原地修改（In-Place）”的精髓。

标准的工业级实现通常采用双向扫描双指针原地分区法。以下以具体数组 [5, 2, 8, 3, 9, 1]、区间索引从 0 到 5、选取首元素 5 作为基准值为例，详细演示分区的五个关键步骤：

双指针探测的执行细节：

• 第一步（初始化）：设定基准值 pivot = arr[left] = 5。左指针 i = left = 0，右指针 j = right = 5。
• 第二步（从右向左探测）：右指针 j 率先从右端向左移动，跳过大于或等于基准的元素，停在第一个严格小于基准的元素 1（下标 5）。
• 第三步（从左向右探测）：左指针 i 从左端向右移动，跳过小于或等于基准的元素，停在第一个严格大于基准的元素 8（下标 2）。
• 第四步（元素原地对调）：此时 i < j，交换 arr[2] 与 arr[5]，数组变为 [5, 2, 1, 3, 9, 8]。随后两指针继续向内逼近。
• 第五步（指针相遇与基准归位）：j 继续左移停在元素 3（下标 3），i 右移亦到达下标 3，两指针相遇。最后将首位的基准值 5 与相遇点 arr[3] 对调，数组变为 [3, 2, 1, 5, 9, 8]。基准值 5 稳固就位，函数返回分割点索引 3。

三、完整 JavaScript 递归代码实现

根据上述原地分区逻辑，下面给出结构清晰、可直接在 Node.js 或浏览器控制台中运行的 JavaScript 完整实现代码：

/**
 * 交换数组中指定两个下标的元素（原地对调）
 * @param {number[]} arr 
 * @param {number} i 
 * @param {number} j 
 */
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

/**
 * 原地双指针分区函数
 * 将选定基准归位，并保证左侧 <= 基准，右侧 >= 基准
 * @param {number[]} arr 待处理数组
 * @param {number} left 当前分区起始索引
 * @param {number} right 当前分区结束索引
 * @returns {number} 基准最终归位后的索引
 */
function partition(arr, left, right) {
  // 选取最左侧元素为基准值
  const pivot = arr[left];
  let i = left;
  let j = right;

  while (i < j) {
    // 1. 右指针向左探测，寻找第一个严格小于 pivot 的元素
    while (i < j && arr[j] >= pivot) {
      j--;
    }
    // 2. 左指针向右探测，寻找第一个严格大于 pivot 的元素
    while (i < j && arr[i] <= pivot) {
      i++;
    }
    // 3. 在相遇前，交换两侧逆序元素
    if (i < j) {
      swap(arr, i, j);
    }
  }

  // 4. 将基准值交换至两指针相遇的最终落脚点
  swap(arr, left, i);
  return i;
}

/**
 * 快速排序主递归函数
 * @param {number[]} arr 待排序数组
 * @param {number} left 排序区间左边界（默认 0）
 * @param {number} right 排序区间右边界（默认 arr.length - 1）
 * @returns {number[]} 排序完成的原数组引用
 */
function quickSort(arr, left = 0, right = arr.length - 1) {
  // 基线条件：区间内元素个数 <= 1 时终止递归
  if (left >= right) {
    return arr;
  }

  // 执行原地分区，获取基准最终索引
  const pivotIndex = partition(arr, left, right);

  // 递归对左半子区间排序（排除已就位的 pivotIndex）
  quickSort(arr, left, pivotIndex - 1);

  // 递归对右半子区间排序（排除已就位的 pivotIndex）
  quickSort(arr, pivotIndex + 1, right);

  return arr;
}

// 示例验证
const sample = [5, 2, 8, 3, 9, 1];
quickSort(sample);
console.log("排序输出:", sample); 
// 示例输出: [1, 2, 3, 5, 8, 9]

递归调用栈与分治时序解析：

在 JavaScript 引擎中，函数递归依赖于执行上下文调用栈（Call Stack）。理解递归不能仅停留在代码表面，还需要清晰观察压栈与弹栈的时序。

当主调用 quickSort(arr, 0, 5) 完成分区后，它并不会同时处理左右子树，而是严格按照代码顺序执行：

1. 深度优先压栈：首先进入左侧 quickSort(arr, 0, 2)，在该分支完全处理完毕、触底回溯弹栈之前，右侧分支 quickSort(arr, 4, 5) 处于等待状态。
2. 基线条件触发与弹栈：当左递归深潜至 quickSort(arr, 0, 0) 时，触发 left >= right 条件，当前帧立即返回并从调用栈弹出。
3. 状态隔离：因为每次分区都把基准值锁定在其最终索引上，所以后续子递归的区间均严格收敛，不会发生越界或循环嵌套。

四、关键细节、边界场景与工程优化

标准快速排序在理论上表现优异，但在实际工程环境中，如果不注意基准选取与边界处理，很容易遭遇严重的性能退化甚至调用栈溢出（Stack Overflow）。

1. 规避最坏时间复杂度：三数取中法（Median of Three）

如果总是固定选取数组首项或尾项作为基准，当遇到已完全有序或逆序的极端输入时，每次分区只能将数组规模缩减 1，递归树退化成单链表。此时时间复杂度恶化为 O(N²)，调用栈深度暴涨至 O(N)。

解决此问题的经典策略是三数取中法：在分区前比较 left、mid = (left + right) >> 1 和 right 三个位置的值，选取中间大小的数作为基准，并将其提前与 left 交换。代码片段如下：

function medianOfThree(arr, left, right) {
  const mid = Math.floor((left + right) / 2);
  // 对 left、mid、right 三处进行简易排序
  if (arr[left] > arr[mid]) swap(arr, left, mid);
  if (arr[left] > arr[right]) swap(arr, left, right);
  if (arr[mid] > arr[right]) swap(arr, mid, right);
  // 将中位数藏到 left 索引，作为后续分区的 pivot
  swap(arr, left, mid);
}

2. 重复元素与指针停止条件

在双指针移动的循环条件中（例如 arr[j] >= pivot 与 arr[i] <= pivot），必须注意等于号的使用。若在存在大量重复元素的数组中完全漏掉等于判断，指针容易发生无限停顿或越界。严格保证 i < j 的前提下合理比较是防范死循环的关键。

3. V8 引擎内部与 JavaScript 原生 sort 的差异

现代 JavaScript 引擎（如 Chrome V8）在早期的 Array.prototype.sort() 中曾对小型数组使用插入排序、大型数组使用快速排序。但在 ECMAScript 规范要求排序保持“稳定性（Stable）”后，V8 全面切换到了 TimSort（一种结合归并排序与插入排序的高性能混合算法）。

快速排序本质上是不稳定排序，因为远距离元素在交换过程中可能会颠覆相同键值元素的初始先后相对次序。若业务逻辑对稳定性有强依赖，需谨慎评估或附加索引标记。

五、核心要点总结与快速决策清单

快速排序的精髓在于“分而治之”与“原地交换”。将整个算法流程归纳为以下决策流程图与特性对照表，以便随时回顾查阅：