比较
交换
趟数

  • 插入中
  • 比较中
  • 已交换
  • 已排序部分

更多关于插入排序

插入排序

插入排序的做法,和很多人整理手中扑克牌的方式一样。它在列表前端保持一个已排序部分,取出下一个值,把它向前移过每个更大的值,直到放进合适的位置。可以用任意速度播放,也可以逐次比较地单步查看,同时观察比较、交换和趟数的计数。 按“播放”观看排序过程,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到任意位置。卡片统计比较次数、交换次数和趟数。可选择柱子数量、初始顺序,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

它是如何运作的

  1. 选择柱子数量和初始顺序:随机、基本有序、倒序或少量不同值。也可以输入自己的数字。
  2. 按“播放”,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到排序的任意位置。
  3. 试试基本有序的列表和倒序的列表,比较两者各需要多少次比较。

插入排序的原理

第一个值单独构成已排序部分。取出第二个值,与它前面的值比较;如果前面的值更大,就交换,然后继续比较和交换,直到前面的值不比它大,或它到达最前面。这时前两个值已经有序。对第三个、第四个值依次这样做,直到列表末尾。

基本有序的列表排得很快

每一趟遇到第一个不比它大的值就停下,所以已经接近正确位置的值只需一两次比较。已排序的列表需要 n − 1 次比较、零次交换;倒序的列表是最坏情况,比较和交换各需 n(n − 1)/2 次。交换次数总是等于初始列表中的逆序对数,也就是顺序颠倒的值对数。因此,插入排序常用于短列表或基本有序的列表,也常在更快的排序算法内部用来处理小片段。

常见问题

插入排序是怎样工作的?

它在列表前端构建一个已排序部分。每一趟取出下一个值,把它向前移过前面每个更大的值,直到放进合适的位置。第 k 趟之后,前 k + 1 个值已经有序,但后面的值仍可能插到它们中间。

插入排序要进行多少次比较和交换?

交换次数总是等于初始列表中的逆序对数:已排序的列表为 0,倒序的列表为 n(n − 1)/2。比较次数等于交换次数加上每趟最多一次,所以在 n − 1 到 n(n − 1)/2 之间。

为什么插入排序在基本有序的列表上很快?

因为一趟遇到不比它大的值就会停下。如果每个值都接近最终位置,每一趟都很短,整个排序所需的时间接近 n。

插入排序稳定吗?

稳定。一个值只会越过严格更大的值,所以相等的值不会互相越过,会保持原来的顺序。

我的数字会被发送到别处吗?

不会。排序在你的浏览器中运行,上次的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器