用柱状动画看选择排序在未排序区找最小值并换到前面。交换仅 n−1 次,理解它在写入昂贵场景的价值。
算法
数组
比较
0
交换/写入
0
步数
0/1,577
读取
0
辅助内存
0
递归深度
1/1
放慢速度,用「单步」对照伪代码高亮和柱条颜色。
伪代码
for i ← 0 to n−1
min ← i
for j ← i+1 to n−1
if a[j] < a[min]
min ← j
swap a[i] ↔ a[min]
时间复杂度
| 最好 | O(n²) |
|---|---|
| 平均 | O(n²) |
| 最坏 | O(n²) |
| 空间 | O(1) |
| 稳定 | 否 |
选择排序每轮在未排序区间找出最小值(紫色柱),与该区间的第一个元素交换,从前到后逐个确定。
比较固定 n(n−1)/2 次,所有情况 O(n²);但交换只有 n−1 次,是比较类排序中写入最少的。不稳定排序。 排序可视化