比较
交换
趟数

  • 比较中
  • 当前最小值
  • 已交换
  • 已就位

更多关于选择排序

选择排序

选择排序从前往后构建有序列表。每一趟扫描尚未排序的值,记住其中最小的,并把它交换到第一个未排序的位置。可以任意速度播放,也可以逐次比较地单步执行,同时观察比较次数、交换次数和趟数。 按“播放”观看排序过程,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到任意位置。卡片统计比较次数、交换次数和趟数。可选择柱子数量、初始顺序,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

它是如何运作的

  1. 选择柱子数量和初始顺序:随机、基本有序、倒序或少量不同值。也可以输入自己的数字。
  2. 按“播放”,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到排序的任意位置。
  3. 观察扫描过程中当前最小值的变化,以及每趟结束时把它放到位的那次交换。

选择排序的原理

查看列表中的每个值,记住最小的那个。把它与第一个值交换:第一个位置就此确定。然后从下一个位置开始,对列表的其余部分做同样的事。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 — 无需安装,无需信用卡即可启动。

前往编辑器