Timsort、Quicksort 和 Mergesort 等算法主导着“现实世界”的排序方法。这些比较排序的案例非常实用——它们已被证明是各种环境中性能最高、最稳定、多用途的排序算法。
然而，我们在计算机上排序的几乎所有东西似乎都是可数/部分有序的。数字、字符、字符串，甚至函数都适用于一些有意义的非比较排序方法。这里的一个候选者是基数排序。一般来说，它会比 O(n*log(n)) 表现得更快，在许多复杂度为 O(K*n) -- K 的情况下，大大超过了 n * log(n) 的理论比较排序限制是表示特定项目所需的位数。
是什么赋予了？
比较排序基于一个非常好的抽象：您所需要的只是一种比较两个元素的方法。然后，根据您的语言，使用模板 (c++)、接口 (java)、类型类 (haskell)、函数对象 (javascript) 等。您可以对可以容纳任意类型的容器进行排序，您唯一需要的是实现比较.
您将如何为任意类型实现基数排序？:)
基数排序的速度取决于键的长度。如果你有像字符串这样的长键，基数排序可能会很慢。
此外，对于仅对少数项目进行排序，初始化成本可能会比实际排序高出一个数量级。
例如，如果您使用 8 位基数对 32 位整数进行排序，则需要初始化 256 个存储桶列表的至少 4 倍 - 如果您只有 20 个左右的项目来排序，那么 80 次交换将远慢于约快速排序需要约 200 次比较/交换。
如果您对任何更长的内容进行排序，例如字符串，则最长字符串的每个字符都有一个存储桶初始化 - 这可能会更糟。
基数排序仅适用于使用整数键对对象进行排序，从实际性能的角度来看，它在很大程度上取决于键的长度。对于对任意对象进行排序的一般情况，这还不够——因此需要基于比较的排序。