快速排序 (Quick Sort)

用柱状动画看快速排序以枢轴分区:小的去左、大的去右。平均 O(n log n) 最快,但逆序输入会退化为 O(n²)。

算法

数组

大小48
比较中交换/写入枢轴/基准读取已排序
速度50×

比较

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²) — 用「逆序」预设可以亲眼看到。 排序可视化

常见问题

最坏 O(n²) 为什么还是标准排序?
随机或三数取中枢轴让最坏情况几乎不可能出现,且平均速度和缓存表现优于其他 O(n log n) 排序。
是稳定排序吗?
不是。远距离交换会打乱相等元素的顺序。

其他算法