快速排序 Quick Sort
交换排序 · 实践中最快的通用排序
什么是快速排序
快速排序是「分而治之」的代表：挑一个基准 pivot，把数组重排成「比它小的都在左、比它大的都在右」——这一步叫分区（partition），做完后 pivot 就落到了它最终该在的位置。然后对左右两段各自递归重复。它平均只要 O(n log n)、而且原地不吃额外内存、常数因子小，是大多数语言标准库通用排序的底子。
它怎么做
本页用 Lomuto 分区（取区间末位当 pivot）+ 一个显式区间栈代替递归：栈里存「待处理的区间」，每次弹出一段做分区、把 pivot（品红柱）换到正确位置钉死，再把左右两个子区间压回栈。点「下一步」看 [7, 6, 5, 10, 9, 8, 4, 3, 2, 1]：右侧区间栈显示还有哪些段待排，主轨上 pivot 一次次归位、绿色就位块逐渐铺满。
区间栈 · 每格 = 一段待排序子数组 a[lo..hi]（栈顶先弹出分区）
栈空 → 全部就位
弹出区间 [0,9]
1function quickSort(a: number[]): number[] {
2 const n = a.length;
3 const stack: [number, number][] = [[0, n - 1]];
4 while (stack.length > 0) {
5 const [lo, hi] = stack.pop()!;
6 if (lo >= hi) continue;
7 const pivot = a[hi];
8 let i = lo;
9 for (let j = lo; j < hi; j++) {
10 if (a[j] < pivot) {
11 [a[i], a[j]] = [a[j], a[i]];
12 i++;
13 }
14 }
15 [a[i], a[hi]] = [a[hi], a[i]];
16 stack.push([i + 1, hi]);
17 stack.push([lo, i - 1]);
18 }
19 return a;
20}
n10
栈深0
lo0
hi9
pivot-
i-
j-
a[j]-
swapCount0
1 / 93
复杂度与适用
平均 O(n log n)、原地、不稳定。软肋是最坏 O(n²)——当 pivot 每次都取到极值（如对已有序数组取末位），分区会退化成一头沉。实战用「随机 / 三数取中」选 pivot 来规避。另外大量重复元素也会拖慢它——这正是三路快排要解决的。
快排的两个变体（本站都有）：
三路快排：分成 < / == / > 三段，等值元素一次归位——治大量重复。
双轴快排：用两个基准分三段——Java 基本类型
三路快排：分成 < / == / > 三段，等值元素一次归位——治大量重复。
双轴快排：用两个基准分三段——Java 基本类型
Arrays.sort 实际采用。 看懂本页的单轴分区后，去三路快排和双轴快排页看它在真实世界怎么被打磨——同样的 lt/i/gt 指针，玩法各不相同。