在计算机科学中，排序算法是基础中的基础，而快速排序凭借其平均 O(n log n) 的时间复杂度和优秀的实际性能，长期占据“最实用排序算法”的宝座。对于 JavaScript 开发者而言，理解并实现快速排序不仅是面试的常客，更是体会分治思想、提升代码设计能力的绝佳途径。本文将以 JavaScript 为语言载体，拆解快速排序的三大核心：pivot 选择、双指针操作与分治递归。

一、核心思想：分而治之

快速排序由 C. A. R. Hoare 于 1960 年提出，其核心是分治策略。基本思路是：从数组中选出一个“基准元素”（pivot），通过一趟扫描将数组分成两部分——左部分所有元素小于等于 pivot，右部分所有元素大于等于 pivot；然后递归地对左右两部分重复该过程，直到每个子数组只剩一个元素（天然有序）。这种“分-治-合”的模式将大问题分解为独立子问题，最终合并为有序结果。

二、关键步骤：pivot 与双指针

实现快速排序有两个关键设计点：如何选 pivot 与 如何分区。

2.1 pivot 的选择

pivot 直接决定算法的平衡性。最简单的做法是固定取第一个或最后一个元素，但在已排序数组上会退化到 O(n²)。更常见的优化方式包括：

  • 随机 pivot：在数组中随机选一个位置，期望避免最坏情况。
  • 三数取中法：取数组首、中、末三个元素的中位数作为 pivot，平衡性更稳定。

在 JavaScript 中，随机 pivot 实现简单且效果良好，是多数教程采用的方式。

2.2 双指针分区

分区是快速排序的“重头戏”。经典的 Hoare 分区 使用两个指针：左指针从左侧向右移动，寻找大于等于 pivot 的元素；右指针从右侧向左移动，寻找小于等于 pivot 的元素；当两者都找到时进行交换，直到指针相遇。Lomuto 分区则更为直观，但交换次数较多。现代实现中，双指针法 以代码简洁、数据移动少而受欢迎。以下是典型实现：

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return; // 递归终止

  // 随机选择 pivot 并交换到末尾
  const pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
  [arr[pivotIndex], arr[right]] = [arr[right], arr[pivotIndex]];

  const pivot = arr[right];
  let i = left; // 慢指针，标记小于 pivot 的边界

  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]]; // 将 pivot 归位

  // 递归处理左右两半
  quickSort(arr, left, i - 1);
  quickSort(arr, i + 1, right);
  return arr;
}

上述代码采用了“单向遍历”的变体：用指针 i 划分小于 pivot 的区域，指针 j 遍历整个区间。当遇到小于 pivot 的元素时，将其与 i 位置的元素交换，i 向前挪动。结束时将 pivot 换到 i 位置，保证左小右大。尽管这种写法只用了单个“边界指针”，但核心仍是双指针思维的体现——一个负责扫描，一个负责定位。

三、性能与优化

快速排序的平均时间复杂度为 O(n log n)，最坏情况（每次选的 pivot 都是极值）会退化到 O(n²)。通过随机 pivot 或三数取中，最坏概率可被大幅降低。空间复杂度方面，递归调用栈深度平均为 O(log n)，但最坏可能达到 O(n)。现代 JavaScript 引擎（如 V8）对内置的 Array.prototype.sort 已做了大量优化（如 TimSort 或混合排序），但理解快速排序的原理对面试和特殊场景下的定制排序仍至关重要。

四、实际应用与思考

在 JavaScript 日常开发中，排序需求往往直接用 sort() 解决，但快速排序的思想无处不在：从数据库索引、外部排序到数据分析的分治策略，都是同一内核的延伸。掌握快速排序，相当于掌握了一把理解算法复杂度和系统设计的钥匙。

值得一提的是，针对大数据量或特殊数据结构（如链表），快速排序可能需要调整 pivot 选取策略或改用迭代实现以避免栈溢出。但无论如何，选择 pivot 保证平衡，双指针高效分区的底层逻辑始终不变。

五、结语

从 pivot 的巧妙选择，到双指针的精准移动，再到递归分治的化繁为简，JavaScript 快速排序以不足二十行代码展现了计算机科学的优雅与力量。它不仅是一项编程技能，更是一种思维方式——面对复杂问题，先寻找一个“支点”，再分而治之，最终通过迭代逼近全局有序。下次当你处理数据排序时，不妨重温这段代码，感受分治思想的魅力。