手写快速排序，并说明 JavaScript 的 sort 是否稳定。
先理解原理和示例，再练习完整口述与追问。
回答要点
选择基准，把数组分为小于、等于、大于三部分，递归排序两侧。随机选择基准避免有序数组退化为 O(n²)；三路划分处理大量重复元素；先递归较短的一侧、循环处理较长一侧，把递归深度控制在 O(log n)。快速排序不稳定。ES2019 起 Array.prototype.sort 要求稳定，V8 使用 TimSort。
原理拆解
三路划分维护三个指针：[lo, lt) 小于基准，[lt, i) 等于基准，(gt, hi] 大于基准。当前元素小于基准时与 lt 交换并两者前进；大于时与 gt 交换并让 gt 后退（换来的元素尚未检查，所以 i 不动）；等于时只前进 i。划分后只需对 [lo, lt - 1] 和 [gt + 1, hi] 继续排序。
稳定性指相等元素排序后保持原有相对顺序，例如先按时间、再按状态排序时，稳定排序能保留第一次的顺序。默认 sort() 不传比较函数时按字符串的 UTF-16 码元比较，[10, 9, 1].sort() 得到 [1, 10, 9]。比较函数必须返回数字且满足一致性，返回布尔值在不同引擎下结果不可靠。ES2023 增加了不修改原数组的 toSorted。
| 算法 | 平均时间 | 最坏时间 | 额外空间 | 稳定 |
|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(log n) | 否 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 是 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 否 |
| 插入排序 | O(n²) | O(n²) | O(1) | 是 |
| TimSort | O(n log n) | O(n log n) | O(n) | 是 |
示例与推演
function quickSort(input, compare = (a, b) => a - b) {
const arr = input.slice()
const swap = (i, j) => {
const temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
function sort(lo, hi) {
while (lo < hi) {
const pivot = arr[lo + Math.floor(Math.random() * (hi - lo + 1))]
let lt = lo
let i = lo
let gt = hi
while (i <= gt) {
const order = compare(arr[i], pivot)
if (order < 0) swap(lt++, i++)
else if (order > 0) swap(i, gt--)
else i++
}
if (lt - lo < hi - gt) {
sort(lo, lt - 1)
lo = gt + 1
} else {
sort(gt + 1, hi)
hi = lt - 1
}
}
}
sort(0, arr.length - 1)
return arr
}
推演：[3, 1, 3, 2, 3] 若随机到基准 3，一轮划分后变成 [1, 2 | 3, 3, 3]（小于部分内部顺序可能不同），等于区间不再参与递归，只需排序 [1, 2]。
易错点
大于基准时交换后 i 也前进，会漏检换过来的元素；用 filter 创建新数组的写法简洁，但空间开销 O(n log n)，且固定选第一个元素作基准在有序输入下退化。
参考回答可直接练习口述
快排是选基准、分区、递归。我会随机选基准防止有序数组退化，用三路划分把等于基准的元素一次归位，处理大量重复值；先递归短的一侧、长的一侧用循环，递归深度是 O(log n)。快排本身不稳定。JS 的 sort 从 ES2019 起规范要求稳定，V8 用 TimSort；不传比较函数时按字符串比较，所以数字排序一定要传返回数字的比较函数。