选择排序 (Selection Sort)

用柱状动画看选择排序在未排序区找最小值并换到前面。交换仅 n−1 次,理解它在写入昂贵场景的价值。

算法

数组

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

比较

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 次,是比较类排序中写入最少的。不稳定排序。 排序可视化

常见问题

选择排序的优点?
写入(交换)只有 n−1 次。闪存等写入成本高的环境下有优势。
是稳定排序吗?
不是。交换时相等元素的顺序可能被打乱。

其他算法