快速排序是一种基于分治思想的经典排序算法，平均时间复杂度为O(n log n)，在大多数场景下比冒泡排序、插入排序要快得多。在JavaScript中实现快速排序有多种思路，有的写法简单易懂，有的则更贴近算法本质、性能更优。本文分享三种常见的实现方案，并逐一分析它们的优缺点和适用场景。
方案一：基于额外空间的简易实现
这是最常见、也最容易理解的写法，尤其适合初学者和面试白板题。核心思路是：选取数组中间或任意一个元素作为基准值，然后遍历数组，把小于基准的元素放进左数组，大于等于基准的元素放进右数组，最后对左右两个子数组递归执行同样的操作，再把结果拼接起来。
这种写法的优点是逻辑清晰，不会出现下标越界的错误，代码可读性非常高。缺点也显而易见：每一层递归都会创建新的数组，空间开销较大，在数据量很大时内存占用明显增加，并不适合生产环境中的大数据排序。
function quickSort(arr) {
// 递归终止条件：数组长度小于等于1时直接返回
if (arr.length <= 1) return arr;
const left = [];
const right = [];
// 取中间元素作为基准值
const pivot = arr[Math.floor(arr.length / 2)];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else if (arr[i] > pivot) {
right.push(arr[i]);
}
}
// 递归排序左右子数组并合并
return quickSort(left).concat([pivot], quickSort(right));
}
console.log(quickSort([5, 3, 8, 1, 9, 2]));需要注意的是，上面代码里对等于基准值的元素既不放进左数组也不放进右数组，相当于自动跳过了重复元素，这在有大量重复数据时反而能减少递归次数，算是一个小的优化点。如果想保留重复元素，也可以把等于基准的元素单独归入其中一边。
方案二：原地分区经典实现
真正意义上的快速排序应该做到原地排序，也就是不借助额外数组，直接在原数组上通过交换元素完成分区。经典的做法是使用Lomuto分区方案：选取数组最后一个元素作为基准，维护一个分区指针，遍历过程中把小于基准的元素交换到分区左侧，遍历结束后把基准放到正确位置，返回基准的下标，然后对左右两部分递归处理。
这种实现的空间复杂度只有递归调用栈的O(log n)，性能明显优于方案一。理解的关键在于分区指针的含义：它始终指向小于基准区域的后一个位置，每当遇到比基准小的元素，就把它交换进来并让指针右移。
function partition(arr, low, high) {
const pivot = arr[high]; // 以最后一个元素为基准
let i = low - 1; // 小于基准区域的边界
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// 把小于基准的元素交换到左侧区域
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
// 把基准放到正确位置
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const p = partition(arr, low, high);
quickSortInPlace(arr, low, p - 1);
quickSortInPlace(arr, p + 1, high);
}
return arr;
}
const data = [6, 2, 7, 1, 3, 8, 4];
quickSortInPlace(data);
console.log(data); // [1, 2, 3, 4, 6, 7, 8]经典实现也有它的隐患：如果每次选中的基准恰好是最大值或最小值，分区会极度不平衡，递归深度退化为n层，时间复杂度退化为O(n²)。比如对一个已经有序的数组排序时，固定取最后元素作基准就会触发最坏情况。实际使用中可以通过随机选取基准，或者采用三数取中法（取首、中、尾三个元素的中位数作基准）来规避这个问题。
方案三：三路快排应对重复元素
当数组中存在大量重复元素时，前两种方案的分区效果都会打折扣，因为等于基准的值会被集中到某一边继续参与递归。三路快排的思路是把数组划分成三个区域：小于基准、等于基准、大于基准。等于基准的区域在一次分区后就已经就位，不再参与后续递归，因此在重复数据多的场景下效率大幅提升。
三路分区的实现需要三个指针：lt指向小于区域的右边界，gt指向大于区域的左边界，i是当前遍历位置。遍历中根据当前元素与基准的大小关系，分别执行不同的交换操作，直到i与gt相遇为止。
function quickSort3Way(arr, low = 0, high = arr.length - 1) {
if (low >= high) return arr;
const pivot = arr[low];
let lt = low; // 小于基准区域的右边界
let gt = high; // 大于基准区域的左边界
let i = low + 1; // 当前遍历位置
while (i <= gt) {
if (arr[i] < pivot) {
[arr[lt], arr[i]] = [arr[i], arr[lt]];
lt++;
i++;
} else if (arr[i] > pivot) {
[arr[i], arr[gt]] = [arr[gt], arr[i]];
gt--;
// i不动，交换过来的元素下一轮再判断
} else {
i++;
}
}
quickSort3Way(arr, low, lt - 1);
quickSort3Way(arr, gt + 1, high);
return arr;
}
console.log(quickSort3Way([4, 2, 4, 3, 4, 1, 4, 5]));三路快排在全部元素都相同的情况下，一次分区就能完成排序，时间复杂度接近O(n)，这是前两种方案无法做到的。它的代价是普通场景下交换次数略多、代码复杂度稍高，属于典型的以场景换性能的优化手段。
三种方案的对比与选择建议
把三种方案放在一起对比，可以从时间复杂度、空间复杂度和适用场景三个维度来衡量。方案一空间开销最大，但代码最简单，适合学习算法思想和应对简单面试题；方案二是标准实现，空间和时间表现均衡，适合一般规模的排序需求；方案三则专门针对重复元素多的数据做了优化，在特定场景下有明显优势。
| 方案 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 简易实现 | O(n log n) | O(n) | 学习理解、小数据量 |
| 原地分区 | O(n log n) | O(log n) | 通用场景、生产环境 |
| 三路快排 | O(n log n) | O(log n) | 大量重复元素 |
还有一点值得提醒：JavaScript引擎内置的Array.prototype.sort方法在V8中已经采用了TimSort混合排序算法，对短数组使用插入排序、长数组使用归并思想，稳定性和性能都经过充分优化。在实际项目中，除非有特殊需求或明确知道数据特征，一般直接使用sort方法就够了，自己实现快速排序更多是为了面试准备和理解算法原理。如果想深入性能调优，可以自行写个基准测试，用不同规模和分布的数据对比这几种实现的耗时，会收获更直观的体会。