[科普中国]-比较计数排序

比较排序是一种排序算法，它只通过单个抽象比较操作（通常是“小于或等于”运算符或三向比较）读取列表元素，该操作确定两个元素中的哪一个应首先出现在 最终排序清单。 唯一的要求是操作员遵守总订单的两个属性：

如果a≤b且b≤c则a≤c（传递性）

对于所有a和b，a≤b或b≤a（总和或三分法）。

a≤b和b≤a都可能; 在这种情况下，要么可以在排序列表中排在第一位。 在稳定排序中，输入顺序确定此情况下的排序顺序。

不同分拣技术的性能限制和优势比较种类的性能存在基本限制。比较排序必须具有Ω（n log n）比较运算的平均值下界，[1]称为线性时间。这是仅通过比较获得的有限信息的结果 - 或者换句话说，是完全有序集合的模糊代数结构。从这个意义上讲，mergesort，heapsort和introsort在它们必须执行的比较次数方面是渐近最优的，尽管这个度量忽略了其他操作。非比较排序（例如下面讨论的示例）可以通过使用除比较之外的操作来实现O（n）性能，允许它们回避该下限（假设元素是恒定大小的）。

请注意，比较排序可能会在某些列表上运行得更快;许多自适应排序，例如插入排序在O（n）时间内在已排序或接近排序的列表上运行。 Ω（n log n）下限仅适用于输入列表可以按任何可能顺序排列的情况。

另请注意，排序速度的实际测量可能需要考虑某些算法最佳地使用相对快速的缓存计算机内存的能力，或者应用程序可能受益于排序数据开始向用户快速显示的排序方法（和那么用户的阅读速度将是限制因素，而不是在整个列表被排序之前没有输出可用于显示的排序方法。

尽管存在这些限制，但比较排序提供了显着的实际优势，即对比较功能的控制允许对许多不同数据类型进行排序并对列表的排序方式进行精细控制。例如，反转比较函数的结果允许列表反向排序;只需创建一个比较函数，按顺序比较每个部分，就可以按字典顺序对元组列表进行排序：

function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc)) if lefta ≠ righta return compare(lefta, righta) else if leftb ≠ rightb return compare(leftb, rightb) else return compare(leftc, rightc)平衡的三元符号允许在一步中进行比较，其结果将是“小于”，“大于”或“等于”之一。

比较排序通常更容易适应复杂的订单，例如浮点数的顺序。另外，一旦编写了比较函数，就可以使用任何比较排序而无需修改;非比较排序通常需要每种数据类型的专用版本。

这种灵活性以及现代计算机上的上述比较分类算法的效率已经导致在大多数实际工作中广泛偏爱比较分类。

备择方案一些排序问题允许比用于比较排序的Ω（n log n）绑定严格更快的解决方案;一个例子是整数排序，其中所有键都是整数1。当键形成一个小的（与n相比）范围时，计数排序是一个在线性时间内运行的示例算法。其他整数排序算法，例如基数排序，并不比比较排序渐近快，但在实践中可以更快。

按数字对数字对进行排序的问题不受Ω（n²logn）约束（由配对产生的正方形）;最着名的算法仍然需要O（n²logn）时间，但只有O（n²）比较。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学