冠军
操作
已完成

  • 比较中
  • 标记(最小值、基准或键)
  • 已交换或移动
  • 已就位
名次 算法 比较或读取 交换或移动 操作

更多关于排序算法

排序竞赛

哪种排序算法最快?这取决于列表。排序竞赛让八种排序算法同时处理同一列表,每种一条赛道,并把每次比较、读取、交换和移动都算作一次操作。各赛道随计数增加而前进,你可以看到高效的排序已经完成,而慢的还在交换;也能看到列表基本有序或倒序时名次如何变化。 按“播放”观看八种排序算法在同一列表上竞赛,或用“单步”和“后退”逐次操作。拖动滑块可跳到任意位置。每次比较、读取、交换或移动都算一次操作,每条赛道随自己的操作数增加而前进,所以操作最少的排序最先完成。可选择柱子数量、初始顺序,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

它是如何运作的

  1. 选择柱子数量和初始顺序:随机、基本有序、倒序或少量不同值。也可以输入自己的数字。
  2. 按“播放”观看八条赛道。“单步”和“后退”每次移动一次操作;滑块可跳到竞赛的任意位置。
  3. 比较结果表,再试试基本有序和倒序的列表,看看名次如何变化。

竞赛如何进行

八种排序拿到同一个列表。每次比较两个值、基数排序和计数排序每读取一个数位或数值、每次交换或移动,都算一次操作。在竞赛的每一时刻,每条赛道显示其排序用这么多次操作进行到了哪一步。所需操作越少的排序越早到达终点。结果表列出每种排序的比较次数、交换或移动次数以及总数。

结果说明什么

对 40 个随机值,计数排序约需 120 次操作,基数排序约 240 次,快速排序约 260 次,归并排序约 380 次。堆排序随后,约 490 次,选择排序和插入排序约需 820 次,冒泡排序超过 1,100 次。在基本有序的列表上,插入排序以约 50 次获胜,冒泡排序第二。在倒序列表上,冒泡排序和插入排序都需要 1,560 次。计数排序和基数排序常胜,是因为这些值都是较小的整数;对其他数据,它们根本无法使用。

常见问题

哪种排序算法最快?

取决于数据。对较小的整数,计数排序和基数排序所需操作最少。对一般数据,快速排序和归并排序在随机列表上最快,插入排序在基本有序的列表上最快。冒泡排序和选择排序除了在很小的列表上,都很慢。

什么算一次操作?

每次比较两个值、基数排序和计数排序每读取一个数位或数值、每次交换或移动一个值。这是个简单模型:实际运行时间还取决于内存访问和每次操作的开销。

为什么计数排序和基数排序经常获胜?

因为它们从不比较值。它们利用这些值是较小整数这一点,所以工作量随 n 加上值的范围增长,而不是随 n log n 增长。对不是小整数的数据,它们不适用。

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

因为它的工作量等于值的个数加上逆序对的个数。基本有序的列表逆序对很少,所以每个值只需移动一两位。

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

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

准备好尝试了吗?

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

前往编辑器