何时使用非比较排序而不是比较排序

Question

在课堂上，我们学习了一大堆新的非比较排序算法，以避免所有基于比较的排序的下限为omega(nlogn)。但对我来说有点不清楚的是，何时使用哪个排序算法族的利弊。

任何数据集都可以被调整，以便使用非比较排序算法（基数排序、桶排序、键索引排序）吗？如果是这样，那么比较排序存在的意义是什么？

对不起，这是一个很基础的问题，但我真的找不到任何在线资源。

- Lucas Ou-Yang

---

通过选择特定的排序算法，您可以在内存和速度之间进行权衡。而且，您的问题约束使得某些算法不切实际。 - Alexey Frunze

Answer 1

并非所有的项目集都能以高效的方式进行非比较排序的调整。例如，对任意精度数字进行排序需要在桶排序内部运行循环多次，这会降低性能。

基数排序的问题在于它必须检查要排序的每个项目的每个元素。相反，基于比较的排序可以跳过相当数量的子元素（数字、字符等）。例如，当比较函数检查两个字符串时，它会在第一个不同之处停止，跳过两个字符串的尾部。另一方面，桶排序必须检查每个字符串中的所有字符。

总的来说，追求最优渐进复杂度并不总是一个好策略：使用显著更复杂的算法的N值通常太高，使得更复杂的算法实际上并不实用。例如，快速排序的最坏时间复杂度非常糟糕，然而平均而言，由于其非常低的开销，它在大多数实际情况下都能击败其他大多数算法，因此在大多数实际情况下是一个不错的选择。

*在实践中，桶排序的实现避免了查看所有子元素（数字、字符等）的需要，方法是在桶中的项目数少于某个阈值时立即切换到基于比较的排序。这种混合方法既能击败纯基于比较的排序，又能击败纯桶排序。

- Sergey Kalinichenko

---

肯定的是，桶排序从最高位到最低位工作，并在桶变得足够小的时候使用其他排序算法（比如插入排序）。因此，如果你用它来对字符串进行排序，它可能只会读取每个字符串的前几个字节。大多数快速排序实现，除非专门用于排序字符串，否则不会执行此优化，在快速排序的更深层递归中，比较的字符串的第一个差异逐渐加深。因此，尽管我同意你的总体结论，但我并不被这个例子所说服。 - rici

@rici 非常感谢您的精彩评论！我同意，我的快速排序示例有点误导人，因为我引入它是为了阐述一个与原始问题不直接相关的普遍观点 - 具体而言，低开销算法具有更高渐进复杂度可以击败渐进复杂度更好但开销更高的算法。我编辑了答案以反映您关于在桶变小时切换到归并排序的注意事项。 - Sergey Kalinichenko

(1) 当桶的大小为1时停止桶排序通常比切换到基于比较的排序要好得多。如果您这样做，如果您正在对字符串进行排序，则不会进行更多的字符比较，而不是更少的字符比较。 (2) 快速排序并不是最坏情况时间复杂度不重要的很好例子；一个好的归并排序实现即使在平均情况下也会进行更少的比较，并且与缓存一样好。不幸的是，快速排序具有快速声誉，但其性能并不快速。 - tmyklebu

Answer 2

非比较排序的问题在于它们的复杂度通常取决于除输入大小之外的其他参数。例如，基数排序的复杂度为O(kn)，其中k是元素中最高位数字的数量 - 问题是，k与n有何关系。如果k与n大致相同，则算法变为O(n^2)。

- Maciej Stachowski

---

练习：如果您的数字有n个位数，最坏情况下逐位比较需要多长时间？如果您进行n log(n)次这样的比较，最坏情况下排序需要多长时间？ - tmyklebu

比较两个不超过ALU总线/寄存器大小的数字应该是O(1)。假设CMP需要1个时钟周期，并且我们的ALU总线/寄存器大小至少与最大数字一样长（在算法分析中通常如此），您提到的排序需要O(nlogn)。另一方面，基数排序明确地逐位进行比较，因此必须调用CMP n次，并且由于处理器由时钟同步，所以问题中的数字最多为4位并没有帮助。 - Maciej Stachowski

排序单词是一个非常特殊的情况。 基数排序需要O（n * k），其中k是单词大小除以最高可容忍基数。 这将比n log（n）增长得慢得多; 我应该总是愿意选择k大约为单词大小的对数，并在每次传递中有wordsize / log wordsize个桶。（除非相对于单词大小非常小的排序，此时我可能希望改用插入或冒泡排序。） - tmyklebu

Answer 3

非比较排序算法对输入做出了一些假设。为了确保线性时间复杂度，输入的所有元素都必须落在一个恒定长度的范围内。另一方面，基于比较的排序算法不对输入做任何假设，能够处理任何情况。非比较排序算法通常以额外的内存成本和输入的局限性为代价。

- Terry Li

---

你能举一个键值对数据集的例子，其中非比较排序无法工作吗？难道不能调整任何数据集，使得键适合非比较排序吗？ - Lucas Ou-Yang

假设我们想要对N个整数进行排序，其范围未知。在这种情况下，我们只能使用基于比较的算法。换句话说，一般的排序问题可能只能在O(NlgN)时间内解决，无论你如何调整输入。 - Terry Li

为了确保比较排序的时间复杂度为O(n log(n))，您需要将输入的所有元素限制在一个小范围内，因为您会调用比较器Theta(n log(n))次。 - tmyklebu

Answer 4

当你懒得编写非比较排序时，你使用基于比较的排序。

基于比较的排序本质上较慢；它们需要对输入元素调用比较器很多次，并且每次调用只给基于比较的排序提供一位信息。一个正确的基于比较的排序平均必须累积 log_2(n!) ~= n log(n) 位关于其输入的信息。

现在，所有数据都有机器表示。您可以根据您特定类型的数据、它所具有的表示和您用于排序的机器来定制排序算法，如果您知道该怎么做，通常会击败任何基于比较的排序算法。

然而，性能并不是一切，有些情况下（实际上我见过的大多数情况），最高效的解决方案并不是正确的解决方案。好的基于比较的排序可以采用黑盒比较器，并且它们将在小常数乘以 n log(n) 次比较中对输入进行排序。这对于几乎所有应用程序来说已经足够了。

编辑：上述内容仅适用于内部排序，即您拥有足够的RAM来存储整个输入的情况。对于外部排序（例如溢出到磁盘），通常应该一次读取大约半个RAM的数据，使用非比较排序，并将排序结果写出。同时要注意将排序与输入和输出重叠。最后，进行（基于比较的）n路合并。

- tmyklebu

---

嘿，你不是TopCoder上的tmuklebu，对吧？ - Sergey Kalinichenko

我确实是TopCoder上的tmyklebu。 - tmyklebu

我知道我在某个地方看到过这个句柄 :) - Sergey Kalinichenko