排序 · 单步演示
快速排序
选一个基准（这里取区间最后一个数），把比它小的都挪到左边，基准放到中间，然后对左右两段分别做同样的事。
当前操作已就位
步 001 / 035初始数组。快速排序每次选区间最后一个数当基准，把比它小的挪到左边，再对两边分别递归。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
快速排序(lo, hi)：if lo ≥ hi：returnpivot ← a[hi]；i ← lofor j ← lo … hi−1if a[j] < pivot：交换 a[i]、a[j]；i ← i+1交换 a[i]、a[hi]（基准归位）快速排序(lo, i−1)；快速排序(i+1, hi)
变量
| 比较次数 | 0 |
|---|---|
| 交换/写入次数 | 0 |
复杂度
| 最好情况 | O(n log n) |
|---|---|
| 平均情况 | O(n log n) |
| 最坏情况 | O(n²) |
| 额外空间 | O(log n) 平均，O(n) 最坏 |
| 稳定性 | 不稳定 |
每次划分都把基准和区间里其他数各比一次。基准每次都落在正中时一共约 log₂n 层；每次都落在一端（例如输入已经有序、总取最后一个数当基准）时有 n 层，比较次数变成 n(n−1)/2。
要点
- 平均比较次数约 1.39·n·log₂n，推导见讲义。
- 已经有序或全部相等的输入会触发最坏情况，可以用随机选基准或三数取中来避开。
- 空间开销来自递归调用栈，深度就是层数。
常见错误
输入全是相同的数时，本演示的「严格小于」划分会退化成 O(n²)。把演示输入改成 8 个相同的数，看比较次数。