JavaScript 快速排序的迭代写法与非递归优化

一、问题的提出：为什么递归快排会在 JavaScript 中崩溃？

考虑一个典型的开发场景：在前端电子表格处理组件中，用户导入了一份包含 60,000 条交易记录的流水列表；或者在 Node.js 后端数据同步任务中，程序需要对一组已经基本排好序的按时间戳排列的数据进行局部校准。如果开发者直接套用教科书上的标准递归快速排序算法，程序往往不仅无法如期返回结果，反而在执行瞬间直接抛出如下致命异常：

要理解为什么会发生这个问题，需要从 JavaScript 引擎底层的内存模型与执行机制来看：

1. 调用栈（Call Stack）的容量上限：无论是 Google Chrome 浏览器的 V8 引擎还是 Node.js 环境，为单个线程分配的调用栈空间都是极其有限的。每次函数调用都会在调用栈中分配一个“栈帧”（Stack Frame），用于存储局部变量、参数、词法作用域链和返回地址。在主流的 64 位 V8 环境中，调用栈的深度硬上限通常在 10,000 层左右。
2. 递归深度的最坏情况退化：快速排序在基准值（Pivot）选取不当且输入数据高度有序（正序或倒序）时，每次切分划分出的左右子区间极不均衡（例如左区间长度为 0，右区间长度为 n - 1）。此时递归树完全退化为单链表，递归深度达到 O(n)。对于 60,000 个元素，递归层数直奔 6 万层，远远击穿了 1 万层的引擎硬限制。
3. 缺乏尾调用优化支持：尽管 ECMAScript 2015 (ES6) 规范曾定义过尾调用优化（Tail Call Optimization, TCO），但在目前的各大主流 JavaScript 引擎（包括 V8）中，出于调试调用栈完整性、错误堆栈追踪（Stack Trace）及性能微架构考量，默认均未开启通用尾调用消除。

因此，要让快速排序在 JavaScript 中承载大规模生产级数据，最可靠的工程解法就是将递归转为迭代（Iterative Approach）。我们在堆内存（Heap Memory）中手动维护一个区间任务栈，把递归调用的隐式入栈动作，替换为向普通 JavaScript 数组中显式压入区间索引。由于堆内存可支配的空间高达数百兆字节乃至千兆字节，系统调用栈的溢出隐患被彻底拔除。

二、迭代快排的基石：分区逻辑（Partition）与状态解构

快速排序无论采用递归还是迭代结构，其最核心的原地排序机制——分区划分（Partition）——在逻辑上是完全一致的。

分区函数的职责十分清晰：在指定的连续区间 [low, high] 内选取一个基准元素（Pivot），通过双指针或单向扫描，把所有小于基准的元素移动到基准左侧，把所有大于基准的元素移动到基准右侧，最终将基准元素安放在其最终排序的正确位置 pivotIndex，并返回该索引。

在迭代写法中，分区函数依旧保持纯粹的原地交换逻辑。这里我们先采用经典的 Lomuto 分区策略作为基准实现：

/**
 * 原地交换数组中的两个元素
 */
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

/**
 * 基础分区函数 (Lomuto 分区策略)
 * @param {number[]} arr - 待排序目标数组
 * @param {number} low - 当前子区间起始下标
 * @param {number} high - 当前子区间结束下标
 * @returns {number} 基准元素最终就位的索引位置
 */
function partition(arr, low, high) {
  // 选取末尾元素作为基准值
  const pivot = arr[high];
  let i = low;

  // 将所有小于 pivot 的元素置换到左侧区域
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      swap(arr, i, j);
      i++;
    }
  }

  // 将 pivot 安放到最终的分界点位置 i
  swap(arr, i, high);
  return i;
}

在递归写法中，分区完成后会紧接着发起两次自身调用：quickSort(arr, low, pivotIndex - 1) 与 quickSort(arr, pivotIndex + 1, high)。在迭代写法中，我们将这两个调用动作抽象为状态数据：只要一个区间的长度大于 1（即 low < high），它就是一个“待处理任务”，我们只需要将 [low, pivotIndex - 1] 与 [pivotIndex + 1, high] 作为待办区间存入我们自己的辅助栈中。

三、基础迭代写法的完整实现与执行轨迹推导

理解了状态转换模型后，我们可以立即写出基础版本的迭代快速排序。它的运行节奏由一个 while 循环主导：

1. 首先将全局初始区间 [0, arr.length - 1] 压入显式栈；
2. 当栈不为空时，弹出栈顶的一个区间元组 [low, high]；
3. 如果当前区间满足 low < high，调用 partition 计算切分点 p；
4. 将切分后生成的左子区间 [low, p - 1] 和右子区间 [p + 1, high] 重新推入栈中；
5. 重复循环，直到栈内所有区间任务都被消化完毕。

/**
 * 基础迭代快速排序 (利用 JavaScript 数组模拟显式栈)
 * @param {number[]} arr - 待排序数组
 * @returns {number[]} 排序后的原数组引用
 */
function quickSortIterativeBasic(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) {
    return arr;
  }

  // 1. 初始化显式任务栈，存入初始排序边界 [low, high]
  const stack = [[0, arr.length - 1]];

  // 2. 主循环：只要栈中仍有待处理区间，持续迭代
  while (stack.length > 0) {
    // 弹出栈顶区间
    const [low, high] = stack.pop();

    // 只有有效区间才需要切分排序
    if (low < high) {
      const p = partition(arr, low, high);

      // 将右子区间与左子区间压入栈中待处理
      if (p + 1 < high) {
        stack.push([p + 1, high]);
      }
      if (low < p - 1) {
        stack.push([low, p - 1]);
      }
    }
  }

  return arr;
}

这段代码已经彻底消除了系统的函数调用栈溢出风险。无论待排数组是 10 万还是 100 万，所有状态推进均在 JavaScript 堆内的 stack 数组中完成，绝对不会产生 RangeError。

四、非递归写法的四大核心优化策略

虽然上述基础迭代写法解决了系统调用栈崩溃的致命缺陷，但在高并发、海量数据或极端分布的生产环境中，它仍然面临三个性能与内存挑战：

• 显式栈深度可能膨胀至 O(n)：如果每次切分极不平衡，随意压栈会导致长区间在显式栈中积压，消耗过多内存；
• GC（垃圾回收）抖动：每次循环执行 stack.push([low, high]) 都会动态创建一个两元素的临时数组对象，在 100 万级排序中会产生数百万个短命对象，引发频繁的 V8 新生代 GC；
• 小区间递归开销冗余：当子区间缩小到 10~20 个元素时，快速排序的基准选取与切分开销反超简单的直接插入排序。

为了解决这些问题，我们需要对非递归快排引入以下四项关键工程优化：

优化 1：长区间先压、短区间后压（将栈空间严格锁定在 O(log n)）

这是快速排序非递归优化中最精妙的理论约束。在切分得到左区间 [low, p - 1] 和右区间 [p + 1, high] 之后，两者的长度通常并不相等：

• 如果盲目固定先压左后压右，在最坏情况下（例如每次切分只分出一个元素），较长的区间将连续被压入栈中却未被立刻处理，导致显式栈的长度直奔 O(n)。
• 正确策略：先对比两个区间的长度，先将较长的区间压入栈底，再将较短的区间压入栈顶。

由于栈是后进先出（LIFO）的，栈顶的短区间会在下一次循环中被立即弹出并切分。从数学上可以严格证明：任何一个待排区间在入栈前，如果强制要求每次优先消解较小的半边，未被消解而在栈中积攒的区间规模至少呈指数级翻倍增长。因此，辅助栈的最大深度被严格限制在 ⌊log&sub2 n⌋ 之内！

优化 2：扁平数值栈消除对象分配与 GC 压力

在基础写法中，我们使用二维数组 stack.push([left, right]) 记录区间。每次压栈都会产生一个形如 [left, right] 的 JavaScript 堆对象。在处理大规模数据时，这种短命小对象不仅拖慢了属性寻址速度，还会频繁触发 V8 的垃圾回收（Minor GC），引发微观停顿（Stop-The-World）。

既然前文已经证明栈的最大深度不超过 2 × ⌊log&sub2 n⌋，我们完全可以使用一个一维扁平定长数组（或 Int32Array）配合一个指针变量 top 来管理任务：

// 针对最多 10 亿级别的数据，栈深度 64 层绝对绰绰有余
const stack = new Int32Array(64);
let top = 0;

// 压栈：连续写入 low 与 high，无对象实例化
stack[top++] = low;
stack[top++] = high;

// 出栈：逆序读出 high 与 low
const high = stack[--top];
const low = stack[--top];

这种写法将整个排序生命周期内的辅助内存分配压缩到了唯一的这一个定长类型化数组上，整个排序过程零新对象分配、零 GC 消耗，速度提升非常显著。

优化 3：小区间截断切换原地插入排序（Cutoff to Insertion Sort）

快速排序是典型的分治算法，具有 O(n log n) 的渐近优势，但在区间非常小（例如长度 ≤ 16）时，快速排序为了寻找基准、维护指针和操作栈所付出的常数开销，显著高于简单的插入排序（Insertion Sort）。

插入排序在极短区间内的比较和移动极为紧凑，缓存命中率（Cache Locality）极高。因此，工业级快排（包括 V8 内部的 Array.prototype.sort 及 JDK 的 Dual-Pivot Quicksort）都会设置一个小数组阈值（通常为 10~16）。当出栈的区间长度满足 high - low <= 16 时，直接对该局部区间执行原地插入排序，不再继续拆分入栈。

优化 4：三数取中法与三向切分（Dutch National Flag）

基准的选择直接决定了切分的均衡度。使用三数取中法（Median-of-Three）——即取首部、中部和尾部三个元素的中位数作为 Pivot——可以有效规避面对预排序数组时的 O(n²) 最坏情况退化。

此外，如果数组中存在大量重复键值（例如海量状态枚举字段、布尔标识），标准的二路切分会把相等的元素重复切分。采用三向切分（Three-Way Partitioning，荷兰国旗问题算法），将区间一次性划分为三部分：

• 小于基准的区间 [low, lt - 1]
• 等于基准的区间 [lt, gt] —— 这部分元素已经完全就位，无需再入栈！
• 大于基准的区间 [gt + 1, high]

对于全等数组或含大量重复元素的场景，三向切分能让时间复杂度直接从 O(n²) 骤降到 O(n)。

五、工业级高性能非递归快排的综合实现与验证

下面将上述全部四项优化融为一体，给出一份完整、健壮、可直接应用于生产环境的 JavaScript 优化版迭代快速排序实现。

/**
 * 局部区间原地插入排序 (用于小规模区间截断优化)
 * @param {number[]} arr - 目标数组
 * @param {number} low - 起始下标
 * @param {number} high - 终止下标
 */
function insertionSortRange(arr, low, high) {
  for (let i = low + 1; i <= high; i++) {
    const temp = arr[i];
    let j = i - 1;
    while (j >= low && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
}

/**
 * 三数取中基准选择：对 low, mid, high 进行排序并将中位数置于 high
 */
function medianOfThree(arr, low, high) {
  const mid = (low + high) >> 1;
  if (arr[low] > arr[mid]) swap(arr, low, mid);
  if (arr[low] > arr[high]) swap(arr, low, high);
  if (arr[mid] > arr[high]) swap(arr, mid, high);
  // 将作为中位数的中点元素调换到 high 位置作为 pivot
  swap(arr, mid, high);
}

/**
 * 工业级优化版非递归快速排序
 * 特性：扁平TypedArray栈 + 小区间插入排序 + 三数取中 + 三向切分 + 短区间优先压栈
 * @param {number[]} arr - 待排序数组
 * @returns {number[]} 排序后的原数组
 */
function quickSortIterativeOptimized(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) {
    return arr;
  }

  const n = arr.length;
  const INSERTION_SORT_THRESHOLD = 16;

  // 优化 1 & 2: 扁平栈，定长 Int32Array (深度 64 足够支撑 2^32 元素)
  const stack = new Int32Array(64);
  let top = 0;

  // 初始区间压栈
  stack[top++] = 0;
  stack[top++] = n - 1;

  while (top > 0) {
    const high = stack[--top];
    const low = stack[--top];

    // 优化 3: 小区间截断切换插入排序
    if (high - low <= INSERTION_SORT_THRESHOLD) {
      if (low < high) {
        insertionSortRange(arr, low, high);
      }
      continue;
    }

    // 优化 4.1: 三数取中防止有序退化
    medianOfThree(arr, low, high);
    const pivot = arr[high];

    // 优化 4.2: 三向切分 (Dutch National Flag)
    let lt = low;
    let gt = high;
    let i = low;

    while (i <= gt) {
      if (arr[i] < pivot) {
        swap(arr, lt++, i++);
      } else if (arr[i] > pivot) {
        swap(arr, i, gt--);
      } else {
        i++;
      }
    }

    // 切分后产生三个区域：[low, lt - 1], [lt, gt] (全等于 pivot), [gt + 1, high]
    const leftLen = (lt - 1) - low;
    const rightLen = high - (gt + 1);

    // 优化 1: 长区间先压、短区间后压，保证辅助栈深度严格收敛于 O(log n)
    if (leftLen > rightLen) {
      // 左侧较长，先压左侧
      if (low < lt - 1) {
        stack[top++] = low;
        stack[top++] = lt - 1;
      }
      // 后压右侧 (栈顶，下次循环优先处理)
      if (gt + 1 < high) {
        stack[top++] = gt + 1;
        stack[top++] = high;
      }
    } else {
      // 右侧较长，先压右侧
      if (gt + 1 < high) {
        stack[top++] = gt + 1;
        stack[top++] = high;
      }
      // 后压左侧 (栈顶，下次循环优先处理)
      if (low < lt - 1) {
        stack[top++] = low;
        stack[top++] = lt - 1;
      }
    }
  }

  return arr;
}

代码验证与测试用例

你可以使用以下测试脚本在 Node.js 或浏览器 Console 中验证该算法的正确性、边界鲁棒性以及面对极限数据的抗压能力：

// 1. 验证基础边界与常规用例
console.log(quickSortIterativeOptimized([]));            // 示例输出: []
console.log(quickSortIterativeOptimized([42]));          // 示例输出: [42]
console.log(quickSortIterativeOptimized([3, 1, 2]));    // 示例输出: [1, 2, 3]

// 2. 验证大量重复键值 (三向切分测试)
const repeated = [5, 2, 5, 5, 1, 2, 5, 3, 5, 2];
quickSortIterativeOptimized(repeated);
console.log(repeated); // 示例输出: [1, 2, 2, 2, 3, 5, 5, 5, 5, 5]

// 3. 验证 100,000 条预排序数据 (传统递归快排在此场景下必然抛出 Call Stack 异常)
const LARGE_SIZE = 100000;
const sortedArray = Array.from({ length: LARGE_SIZE }, (_, i) => i);

console.time("迭代排序 10 万有序数据");
quickSortIterativeOptimized(sortedArray);
console.timeEnd("迭代排序 10 万有序数据"); // 示例输出: 约 10~15ms，完全平稳完成！

// 4. 验证 100,000 条纯随机高离散数据
const randomArray = Array.from({ length: LARGE_SIZE }, () => Math.floor(Math.random() * 1000000));
console.time("迭代排序 10 万随机数据");
quickSortIterativeOptimized(randomArray);
console.timeEnd("迭代排序 10 万随机数据"); // 示例输出: 约 25~35ms，排序无误

六、算法复杂度对比与工程选型建议

通过以上重构，我们将标准递归快速排序与优化后的非递归快排在关键指标上进行对照：

工程实践与选型指引

1. 优先使用原生方法：在常规前端界面展示或规模在数千条以内的业务场景下，优先直接使用 JavaScript 内建的 Array.prototype.sort()。现代 V8 在原生方法中已经内置了高度优化的 TimSort 混合排序算法。
2. 选用非递归快排的典型场景：
   • 需要确定性的防爆栈保障：排序规模超过数万条、数据分布不可控或来自外部不可信输入时；
   • 需要超低内存碎片与零 GC 停顿：在游戏开发、图形渲染管线或高频服务端微服务中，不能容忍垃圾回收引发的帧率骤降；
   • 需要在 TypedArray（类型化数组）上进行高效原地计算：如 Float32Array、Int32Array 科学计算矩阵排序。
3. 稳定性注意事项：需要明确，快速排序（无论递归或迭代）属于不稳定排序（Unstable Sort）。如果业务需求强依赖相等元素的原始相对次序（如多重表头排序），应优先选用归并排序（MergeSort）或 TimSort 的非递归实现。