为什么快速排序比基数排序更受欢迎？

Question

为什么快速排序比基数排序更受欢迎？

sortingquicksortradix-sort

65

为什么快速排序（或introsort）或者任何基于比较的排序算法比基数排序更为常见呢？尤其是对于数字的排序。

基数排序不是基于比较的，因此可能比O(nlogn)更快。实际上，它的时间复杂度是O(kn)，其中k是用于表示每个项目的位数。而且内存开销并不重要，因为您可以选择要使用的桶的数量，并且所需的内存可能小于归并排序的要求。

这与缓存有关吗？或者与访问数组中的随机字节有关吗？

- Daniyar

6个回答

16

基数排序在（大多数）实际应用场景下速度较慢。

一个原因是算法的复杂性：

如果项目是唯一的，则k >= log(n)。即使存在重复项，k< log(n)的问题集也很小。

另一个原因是实现：

额外的内存需求（本身就是一个缺点），会对缓存性能产生负面影响。

我认为可以肯定地说，许多库，例如标准库，使用快速排序，因为它在大多数情况下表现更好。我不认为“难以实现”或“不太直观”是主要因素。

- Plow

1

大体上来说，我认为有两个原因需要担心排序的速度：一是因为你要对许多小列表进行排序，二是因为你要对一个巨大的列表进行排序。如果你正在对整数的小列表进行排序，那么也许可以合理地假设不会有太多重复项（取决于它们是如何生成的），但如果你要对1000亿个32位整数进行排序，那么必然会有很多重复项。所以使用情况很重要。但我同意，大多数程序更有可能经常需要对小列表进行排序，而不是对一个庞大的列表进行排序。 - Tim Goodman

如果你要对1000亿个32位整数进行排序，你只需要一个40亿个整数的数组来存储每个数字出现的次数计数器。这个算法不需要比较，是一个线性算法，比基数排序更简单，只需运行1000亿步即可。但缓存将是一个真正的问题。 - Guillaume Gris

14

一个显而易见的答案是，您可以使用快速排序（即任何可比较的内容）对任意类型进行排序，而使用基数排序只能限制在数字上。并且我认为，快速排序更加直观。

- NullUserException

32

在我看来，冒泡排序比快速排序更加直观。 - Justin Ardini

3

@Justin 的确如此，但速度要慢得多。 - NullUserException

4

没错，但我更感兴趣的是默认的数字排序算法是使用快速排序实现的。特别是在库中的实现，因为如果sort()函数的实现在底层，则直观性并不是很重要。 - Daniyar

1

有点跑题和灰坟，但我认为快速排序在概念上比冒泡排序更直观。或者说，我认为冒泡排序看起来过于简单，但很难证明（无论是正式还是非正式地）它的特定实现是正确的（例如，在正确的时间终止）。我会认为选择排序是最简单和最直观的排序方法，但当然，“直观”有些主观。 - Arkku

7

如在维基百科上提到的

基数排序与其他排序算法的效率问题有些棘手，也容易引起很多误解。无论是基数排序是否比最佳比较排序算法同样有效、更有效还是不如它，都取决于所做假设的细节。对于具有 d 位或更少数字的 n 个键，基数排序的效率为 O(d·n)。有时会将 d 视为常量，这会使基数排序（对于足够大的 n）优于所有需要 O(n·log(n)) 次比较的最佳比较排序算法。然而，在一般情况下，d 不能被视为常量。特别是，在普遍（但有时隐含的）假设下，所有键都是不同的，则 d 必须至少是 log(n) 的级别，这在最好情况下（密集排列键）给出了时间复杂度 O(n·log(n))。这似乎使基数排序最多与最佳比较排序一样有效（如果键比 log(n) 长得多，则更劣）。

反驳的观点是，比较排序算法是以比较次数为度量标准，而不是实际时间复杂度。在某些假设下，平均比较时间将是常数时间，在其他假设下则不是。随机生成的键的比较平均需要常数时间，因为键在一半的情况下在第一个位上不同，在剩余一半的情况下在第二个位上不同，以此类推，最终需要比较两个位。在排序算法中，第一次比较满足随机性条件，但随着排序的进行，比较的键显然不再是随机选择的。例如，考虑自底向上的归并排序。第一遍将比较随机键对，但最后一遍将比较排序顺序中非常接近的键。

决定因素是键的分布方式。基数排序的最佳情况是将它们作为连续的位模式。这将使键尽可能短，前提是它们是不同的。这使得基数排序为 O(n·log(n))，但基于比较的排序将不如此有效，因为在此假设下，比较不会是常数时间。如果我们假设键是长度为 k·log(n) 的位模式，其中 k > 1 且基数为 2 的对数，并且它们是均匀随机的，则基数排序仍将为 O(n·log(n))，但是基于比较的排序也将是如此，因为“额外”的长度使得即使在排序结果中连续的键也有足够的差异，使得比较在平均情况下是常数时间。 如果键比 O(log(n)) 长但是随机的，则基数排序将劣于其他排序算法。 还有许多其他假设，大多需要仔细研究才能进行正确比较。

- Abhinav Chauhan

该部分已被维基百科删除，讨论中认为其中的部分内容是不正确的。 - timgo

1

其他回答中提到的观点是正确的，但就你在几条评论中提到的问题而言，需要关注的是默认排序算法使用快速排序来实现数字排序的事实。特别是在库中的实现。

快速排序是“安全”的选择。基于计数排序的基数排序的潜在运行时间非常有吸引力，但是基数排序易受恶意/不幸数据集的影响。如果被排序键的位数接近被排序键的数量，基数排序的性能将达到n^2，而且空间复杂度也相当高，除了被排序键的位数之外，它往往具有相当高的内置运行时常量。
归并排序之所以有吸引力，是因为它的行为在某些方面类似于每次都选择最佳枢轴（中位数）的快速排序。然而，它具有可观的空间复杂度。它不像基数排序那样容易受到恶意/不幸的数据影响，但也没有提供有吸引力的可能运行时间。
基本快速排序在大多数数据集上表现非常好，除了几乎（或完全）排序的数据集之外，并且具有微小的空间复杂度。
快速排序的漏洞可以通过将其转换为随机化快速排序来轻松处理。基数排序的漏洞可以通过对被排序键施加限制来解决，这将从根本上限制库的用户。在小型数据集上，快速排序比归并排序更具性能，并且在归并排序可能更快的情况下表现合理。
在实现库时，您希望使其具有通用性。以这些示例为例，一个Web应用程序和一个具有极限制微控制器的小型设备。
Web应用程序需要定期处理恶意数据，并且具有各种需求。具有预条件限制的库不太可能有用。在微控制器的情况下，它可能会在空间上受到限制，并且无法放弃可以节省的最小位。快速排序节省空间，如果出现较慢的情况，则只会通过常数乘数完成。
总之 -
1.) 库通常编码为尽可能通用的可用性
2.) 在所有方面都具有良好的性能是可以接受的，特别是如果在许多情况下，它是最佳性能
3.) 空间并不总是主要问题，但当它是时，通常明确地限制

- Culex

-4

基数排序的效率 = O(c.n) 其中c = 输入关键字集中最高位数。 n = 输入关键字集中的关键字数量。

快速排序的最佳情况 = O(n. log n) 其中n = 输入关键字集中的关键字数量。

假设要对16个数字进行排序，每个数字有6位：

基数排序 = 16 * 6 = 96 时间单位。快速排序 = 16 * 4 = 64 时间单位。

教训：当'c'较小时，基数排序胜出。当它很高时，它就会输掉。快速排序不受关键字位数的影响，这使它更好、更实用。

- Aksahy N Shelke

快速排序需要O(n log n)的比较（同样重要的是这是平均情况，而不是最坏情况）。这很重要，因为它意味着快速排序不是“与密钥中数字的数量无关”。这意味着你在比较苹果和橙子。如果你想进行类似的比较，那么就必须考虑执行比较函数的成本。对于字长整数来说，它是恒定的，但这不是一般情况。 - Tim Seguine

建议将基数排序的获胜条件更改为“当'c'较小时或'n'较大时”；在c < log n的情况下，基数排序应该获胜。因此，例如，在百万像素相机图像上对像素值进行排序应该使用基数排序会更快。 - Michael

上限时间复杂度的主要目的是确保程序在 n 相当大的情况下能够在合理的时间内完成。我们并不真正关心 96/64 时间单位的情况。 - francox9

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nils Pipenbrinck · Accepted Answer

我想到了两个观点：

快速排序/内省排序更灵活：

快速排序和内省排序可用于所有类型的数据。对于排序，您只需要比较项的可能性。这在数字方面很简单，但您也可以对其他数据进行排序。

另一方面，基数排序仅通过其二进制表示对事物进行排序。它从不将项目相互比较。
基数排序需要更多内存。

我见过的所有基数排序实现都使用辅助缓冲区来存储部分排序结果。这增加了排序算法的内存需求。如果您只排序几千字节，那可能不是问题，但如果您进入吉巴字节范围，则会产生巨大差异。

如果我没记错的话，有一种原地基数排序算法存在于论文中。