Dan*_*yar 38 sorting quicksort radix-sort
为什么quicksort(或introsort)或任何基于比较的排序算法比radix-sort更常见？特别是对于数字排序.
基数排序不是基于比较的,因此可能比O(n logn)更快.实际上,它是O(k n),其中k是用于表示每个项目的位数.并且内存开销并不重要,因为您可以选择要使用的桶数,并且所需的内存可能小于mergesort的要求.
它与缓存有关吗？或者可能访问数组中的随机字节整数？
Nil*_*nck 23
我想到了两个论点:
Quicksort/Introsort更灵活:
Quicksort和Introsort可以很好地处理各种数据.排序所需要的只是比较项目的可能性.这对于数字来说是微不足道的,但您也可以对其他数据进行排序.
另一方面,基数排序只是通过二进制表示来排序.它永远不会将项目相互比较.
基数排序需要更多内存.
我见过的所有基数排序实现都使用辅助缓冲区来存储部分排序结果.这增加了排序算法的内存需求.如果你只排序几千字节,这可能不是问题,但如果你进入千兆字节范围,它会产生巨大的差异.
如果我记得正确的,那么纸上存在基数排序算法.
Nul*_*ion 11
一个明显的答案是,您可以使用快速排序(即任何可比较的东西)对任意类型进行排序,而您仅限于使用基数的数字.IMO快速排序更加直观.
对于(大多数)现实世界的用例,基数排序较慢.
一个原因是算法的复杂性:
如果项是唯一的,则k> = log(n).即使有重复的项目,k <log(n)的问题也很小.
另一个是实施:
额外的内存要求(其本身就是一个缺点)会对缓存性能产生负面影响.
我认为可以说很多库,比如标准库,使用Quicksort,因为它在大多数情况下表现更好.我不认为"难以实施"或"不太直观"是主要因素.
与其他排序算法相比，基数排序的效率这个话题有些棘手，并且存在很多误解。与基于比较的最佳算法相比，基数排序是否具有同等效率、更低效率或更高效率取决于所做假设的细节。对于具有 d 个或更少数字的 n 个键，基数排序效率为 O(d·n)。有时 d 表示为常数，这将使基数排序（对于足够大的 n）比最佳的基于比较的排序算法更好，这些算法都需要 O(n·log(n)) 次比较。然而，通常 d 不能被认为是一个常数。特别是，在所有键都不同的常见（但有时是隐含的）假设下，d 必须至少是 log(n) 的数量级，这最多给出（使用密集的键）时间复杂度 O(n·日志（n））。这似乎使基数排序最多与最佳的基于比较的排序一样有效（如果键比 log(n) 长得多，则更糟）。
相反的论点是，基于比较的算法是以比较次数而非实际时间复杂度来衡量的。在某些假设下，比较的平均时间是恒定的，而在其他假设下则不会。随机生成的密钥的比较平均需要恒定的时间，因为在一半的情况下，密钥在第一个位上不同，在剩余一半的第二个位上不同，依此类推，导致平均两个位需要比较。在排序算法中，第一次比较满足随机性条件，但随着排序的进行，比较的键显然不再是随机选择的。例如，考虑自底向上归并排序。第一遍将比较随机键对，但最后一遍将比较排序顺序非常接近的键。
决定性因素是密钥的分布方式。基数排序的最佳情况是它们被视为连续的位模式。这将使密钥尽可能短，仍然假设它们是不同的。这使得基数排序为 O(n·log(n))，但基于比较的排序不会那么有效，因为在此假设下比较不会是恒定时间。如果我们假设键是常数 k > 1 和基数为 2 的对数的长度为 k·log(n) 的位模式，并且它们是均匀随机的，那么基数排序仍然是 O(n·log(n) )，但基于比较的排序也是如此，因为“额外”长度使得即使在排序结果中连续的键也足够不同，以至于比较平均是恒定时间。如果键比 O(log(n)) 长，但是是随机的，那么基数排序会较差。 还可以做出许多其他假设，并且大多数都需要仔细研究才能做出正确的比较。