比较排序 | 张拓的博客

比较排序（英语：Comparison sort）是排序算法的一种，通过一个抽象的内容比较操作（通常是“小于或等于”操作）来确定两个元素中哪个应该放在序列前面。该算法的唯一要求就是操作数满足全序关系：

如果 $a\leq b$ 并且 $b\leq c$ 那么 $a\leq c$ （传递性）。
对于 $a$ 或 $b$ ，要不 $a\leq b$ ，要不 $b\leq a$ （完全性）。
对于 $a\leq b$ 并且 $b\leq a$ 这种情况， $a$ 和 $b$ 都有可能被排在前面。这时输入的顺序就会决定最后的顺序。

比较排序类似于将未贴标签的砝码用天平将按质量大小进行排序，并且除了用天平测量两个砝码的质量之外不能用其他方法。

算法特例

比较排序包括：

快速排序
堆排序
归并排序
插入排序
选择排序
冒泡排序

非比较排序包括：

基数排序
计数排序
桶排序

性能限制和优势

比较排序有很多性能上的根本限制。在最差情况下，任何一种比较排序至少需要 Ω(n log n) 次比较操作。这是比较操作所获的信息有限所导致的，或者说是全序集的模糊代数结构所导致的。从这个意义上讲，归并排序，堆排序在他们必须比较的次数上是渐进最优的，虽然这忽略了其他的操作。前面提到的三种非比较排序算法能在 O(n) 时间内完成，通过非比较操作使他们能够回避 Ω(n log n) 这个下界（假设元素为常量大小）。

不过，比较排序在控制比较函数方面有显著优势，因此比较排序能对各种数据类型进行排序，并且可以很好地控制一个序列如何被排序。例如，如果倒置比较函数的输出结果可以让排序结果倒置。或者可以构建一个按字典顺序排序的比较函数，这样排序的结果就是按字典顺序的。

比较排序可以更好地适应复杂顺序，例如浮点数。并且，一旦比较函数完成，任何比较算法都可以不经修改地使用；而非比较排序对数据类型的要求更严格。

这种灵活性和上述比较排序在现代计算机的执行效率一起导致了比较排序被更多地应用在了大多数实际工作中。