为什么要使用比较排序？

Question

Timsort、Quicksort 和 Mergesort 这样的算法在“现实世界”中占据主导地位。这些比较排序方法非常实用，已被证明是最高效、稳定、多功能的排序算法，在各种环境下都能发挥作用。

然而，似乎几乎所有需要在计算机上排序的内容都是可数的/部分有序的。数字、字符、字符串，甚至函数都可以使用某种有意义的非比较排序方法进行排序。其中一种选择是基数排序。通常情况下，它的表现速度比 O(n*log(n)) 更快，在许多情况下，其复杂度为O(K*n) -- K 是表示特定项所需的位数，远远超过理论上的比较排序极限 n * log(n)。

这是为什么呢？

- zetavolt

---

+1 我也一直在想为什么似乎没有（标准或有效的标准）库提供类似于聪明的基数排序变体的东西。请注意：（1）“表示特定项目所需的位数”对于n个不同项目的顺序为log n - 这并不是基数排序能够击败基于比较的排序的真正原因。（2）Introsort不是唯一广泛使用的排序算法，至少有两个流行的标准库使用Timsort。 - user395760

顺便说一下，快速排序不是稳定的。 - Daniel Fischer

快速排序不一定是稳定的，但这只是实现细节。快速排序可以表现出稳定的行为。 - zetavolt

“can behave in a stable fashion”是什么意思？您将如何编写一个稳定的快速排序算法？ - Daniel Fischer

@DanielFischer：你可以添加作为决胜者的最终比较，基于指针值。（在C中是有效的，因为两个指针应该指向同一个数组对象的元素。但这当然需要一个比较函数或等效物）。更新：我混淆了quicksort和qsort()。 - wildplasser

Answer 1

比较排序基于一个非常好的抽象概念：你只需要一种比较两个元素的方法。然后，根据你所使用的语言，可以使用模板（C ++），接口（Java），类型类（Haskell），函数对象（JavaScript）等等来对容器进行排序，这些容器可以包含任意类型，唯一需要做的是实现比较。

你会如何为任意类型实现基数排序？ :)

- Karoly Horvath

---

@ZephyrPellerin 我不想为我使用的每个对象编写类似基数排序的算法。基于比较的算法很好，因为实现不依赖于要排序的对象；所以您可以编写一个通用的快速排序函数（或使用语言库中的函数），并提供一个比较器来进行排序。这就是 抽象 的目的。 - Haile

@Haile 如果我错了，请纠正我，我从未实现过基数排序。但据我所知，我们只需要一个将要排序的项转换为键（整数）的函数，然后可以通过在键上运行基数排序来重复使用它。 - user395760

@Haile 我并不是说这很琐碎（虽然比较器也不简单），我只是在充当魔鬼的代言人。而且我相信，通过提供帮助函数（例如递归地转换序列项并连接它们的键以及内置类型的预定义映射），它可以变得更容易。 - user395760

请问您能否提供一个示例，其中您实现了一个比较函数，而不使用可以轻松提供给基数排序算法的属性或函数？例如 object.age、object.size，甚至是 object.name 等。 - zetavolt

首先需要注意的是：在某些静态类型语言中，将通用类型传递给排序函数可能会产生问题，您可能希望返回一个整数（比特片段），然后使用这些片段进行排序。这就是您的基本接口。 - Karoly Horvath

Answer 2

基数排序的速度取决于关键字的长度。如果您的关键字很长，例如字符串，那么基数排序可能会非常慢。

此外，如果仅需要对少量元素进行排序，则初始化成本可能会超过实际排序的数量级。

例如，如果使用8位基数对32位整数进行排序，则需要初始化至少4次256个桶的列表 - 如果您只有大约20个左右的项目要排序，那么这些初始化和80个交换的时间将远远慢于快速排序需要的大约~ 200个比较/交换。

如果您要对类似字符串的更长内容进行排序，则对于最长字符串的每个字符都需要一个桶初始化 - 这可能会更糟。

- Gunther Piez

---

这些是基数排序的基本问题，还是只是朴素实现的问题？我倾向于后者（这会使你的观点无关紧要），但我不是专家。 - user395760

大多数关于初始化的点可以通过合理的实现（通过对相对较小的大小进行其他种类的排序）轻松解决。但是对于基数排序来说，长键的问题是一个非常根本的问题（想象一下所有的字符串键都具有相同的长前缀）。 - Keith Randall

长前缀对比较同样是一个问题。 - user395760

基数排序的速度取决于关键字的长度，而比较排序的速度则不会受到影响吗？ - user541686

Answer 3

基数排序仅适用于对具有整数键的对象进行排序，并且从实际性能角度来看，它严重依赖于键的长度。对于任意对象的一般情况，这是不够的 - 因此需要比较排序。

- Óscar López

---

你能举个例子吗？在字符串的字典序排序中，美国国旗排序算法通常比快速排序更快。 - zetavolt