用柱状动画看快速排序以枢轴分区:小的去左、大的去右。平均 O(n log n) 最快,但逆序输入会退化为 O(n²)。
算法
数组
比较
0
交换/写入
0
步数
0/467
读取
0
辅助内存
0
递归深度
1/1
放慢速度,用「单步」对照伪代码高亮和柱条颜色。
伪代码
quickSort(lo, hi)
pivot ← a[hi]
for j ← lo to hi−1
if a[j] ≤ pivot: a[i++] ↔ a[j]
a[i] ↔ a[hi] // 피벗 확정
quickSort(lo,i−1) quickSort(i+1,hi)
时间复杂度
| 最好 | O(n log n) |
|---|---|
| 平均 | O(n log n) |
| 最坏 | O(n²) |
| 空间 | O(log n) |
| 稳定 | 否 |
快速排序选一个枢轴(紫色柱),把小于它的放左边、大于它的放右边,然后对两侧递归。每次分区后枢轴位置即确定。
枢轴每次都接近中点则深度 log n,平均 O(n log n) 且缓存友好,是多数内置排序的基础。但逆序数组选末元素作枢轴会退化 O(n²) — 用「逆序」预设可以亲眼看到。 排序可视化