排序算法比较

没有哪种排序算法总是最快。有的简单但慢,有的在随机数据上快、在有序数据上却会失手,还有的根本不是比较排序。让八种算法在同一列表上竞赛,差异一目了然。

八条柱子赛道,每种排序算法一条,有的已经排好并变成绿色,其他的仍未排序
八条柱子赛道,每种排序算法一条,有的已经排好并变成绿色,其他的仍未排序

三大类

冒泡、选择和插入排序是简单排序。它们比较并交换相距较近的值,在随机列表上所需时间与 n² 成正比。归并、快速和堆排序巧妙地划分工作,所需时间与 n log n 成正比,这已是只能问“两个值哪个更大”的排序所能做到的最好结果。基数排序和计数排序完全跳过这个问题:它们直接使用数位或数值本身,这只适用于较小整数之类的键。

衡量工作量

排序竞赛把每次比较、每次读取数位或数值、每次交换或移动都算作一次操作。对 40 个随机值,计数排序约 120 次,基数排序 240 次,快速排序 260 次,归并排序 380 次,堆排序 490 次,选择排序和插入排序各约 820 次,冒泡排序超过 1,100 次。真实的计算机还要考虑内存:由于在列表中移动的方式不同,快速排序实际上通常比其计数显示的更快,而堆排序更慢。

输入很重要

在基本有序的列表上,40 个值插入排序只需约 50 次操作,冒泡排序约 90 次,因为每个值都离自己的位置很近。在倒序列表上,这两种都需要 1,560 次,这是它们的最坏情况。选择、堆、归并、基数和计数排序几乎不受顺序影响。用三数取中法的快速排序能很好地处理有序和倒序列表,但如果用朴素的基准,有序列表就是它的最坏情况。不同值很少时快速排序会变慢,因为相等的值都会分到一边。

内存与稳定性

冒泡、选择、插入、快速和堆排序是原地排序,几乎不需要额外内存。归并、基数和计数排序需要一个与列表等长的缓冲区。稳定排序会让相等的值保持原来的顺序:冒泡、插入、归并、基数和计数排序是稳定的,选择、快速和堆排序则不是。按一个字段接一个字段对记录排序时,稳定性很重要。

该用哪种

实际中你会用编程语言内置的排序:通常是 Timsort,一种对短片段使用插入排序、在部分有序数据上很快的归并排序;或者 introsort,一种会退回到堆排序、对小段使用插入排序的快速排序。对大量较小的整数键,计数排序或基数排序可能比两者都快。冒泡排序和选择排序主要用于教学。

动手试试

打开排序竞赛并按“播放”。每条赛道是同一列表上的一种排序;右边的数字统计它的操作次数,完成后赛道变成绿色。试试基本有序、倒序和少量不同值的列表,看完成顺序如何变化。每种排序还有自己的应用,可以逐步详细查看。

常见问题

最快的排序算法是什么?

对一般数据,快速排序和归并排序(以及基于它们的混合算法,如 introsort 和 Timsort)平均最快,为 n log n。对较小的整数键,计数排序和基数排序更快。对短列表或基本有序的列表,插入排序获胜。

为什么比较排序无法超越 n log n?

n 个值的列表有 n! 种排列,每次比较只有两种结果,所以在最坏情况下至少需要 log₂(n!) 次比较才能把它们全部区分开。这大约是 n log₂ n。基数排序和计数排序不做比较,所以不受这个限制。

哪些排序算法是稳定的?

冒泡、插入、归并、基数和计数排序的常见形式是稳定的。选择排序、快速排序和堆排序不稳定,因为它们会把值移动很远。

哪些排序需要额外内存?

归并、基数和计数排序需要一个大约与列表等长的缓冲区。冒泡、选择、插入和堆排序几乎不需要,快速排序只需少量内存用于递归。

准备好尝试了吗?

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

开始排序竞赛