- 比较中
- 当前最小值
- 已交换
- 已就位
选择排序
选择排序从前往后构建有序列表。每一趟扫描尚未排序的值,记住其中最小的,并把它交换到第一个未排序的位置。可以任意速度播放,也可以逐次比较地单步执行,同时观察比较次数、交换次数和趟数。 按“播放”观看排序过程,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到任意位置。卡片统计比较次数、交换次数和趟数。可选择柱子数量、初始顺序,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。
它是如何运作的
- 选择柱子数量和初始顺序:随机、基本有序、倒序或少量不同值。也可以输入自己的数字。
- 按“播放”,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到排序的任意位置。
- 观察扫描过程中当前最小值的变化,以及每趟结束时把它放到位的那次交换。
选择排序的原理
查看列表中的每个值,记住最小的那个。把它与第一个值交换:第一个位置就此确定。然后从下一个位置开始,对列表的其余部分做同样的事。n − 1 趟之后所有值都已就位,最后一个值自然也在正确位置。
比较多,交换少
扫描不会提前结束,因为只有看完所有剩余的值,才能确定哪个最小。所以对 n 个值,无论列表是有序、倒序还是随机,选择排序都恰好进行 n(n − 1)/2 次比较。作为回报,它最多只交换 n − 1 次,每趟一次。因此,当移动一个值的代价远高于比较两个值时,它是不错的选择。
常见问题
选择排序是如何工作的?
它反复选出尚未排序的最小值,并把它交换到第一个未排序的位置。第 k 趟之后,前 k 个位置按顺序存放着最小的 k 个值。
选择排序要进行多少次比较和交换?
对 n 个值,始终是 n(n − 1)/2 次比较:10 个值 45 次,40 个值 780 次。交换最多 n − 1 次,每趟一次;最小值已就位时会更少。
为什么有序列表和倒序列表耗时一样?
因为每一趟都必须查看所有剩余的值,才能确定找到了最小值。与冒泡排序和插入排序不同,选择排序无法从比较中得知列表已经有序。
选择排序稳定吗?
常见的写法不稳定。一次交换可能让某个值越过与它相等的值:在 2, 2, 1 中,第一个 2 与 1 交换,结果排到了第二个 2 的后面。用移位代替交换的版本是稳定的,但移动次数更多。
我的数字会被发送到别处吗?
不会。排序在你的浏览器中运行,上次的设置保存在本浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器