5

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

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

对不起，这是一个如此初级的问题，但我真的在网上找不到任何东西。

4

4 回答 4

2

并非每组项目都可以调整以有效地用于非比较排序。例如，对任意精度数进行排序将需要在桶排序内多次运行循环，从而降低性能。

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

一般来说，追求最好的渐近复杂度并不总是一个好的策略：使用更复杂的算法得到回报的 N 值通常太高，无法使更复杂的算法变得实用。例如，快速排序的时间复杂度非常差，但由于开销非常低，平均而言它击败了大多数其他算法，使其成为大多数实际情况下的不错选择。

*在实践中，桶排序的实现避免了查看所有子元素（数字、字符等）的需要，只要桶中的项目数低于某个阈值，就切换到基于比较的排序。这种混合方法击败了普通的基于比较的排序和普通的桶排序。

于 2013-01-20T05:04:03.440 回答
1

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

于 2013-01-20T04:51:27.713 回答
1

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

于 2013-01-20T04:58:47.193 回答
1

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

基于比较的排序本质上比较慢；他们需要在输入元素上多次调用比较器，每次调用都为基于比较的排序提供了准确的信息位。正确的基于比较的排序必须平均累积有关其输入的 log_2(n!) ~= n log(n) 位信息。

现在，所有数据在机器中都有一个表示。您可以根据您的特定类型的数据、数据的表示以及您用于排序的机器定制排序算法，而且，如果您知道自己在做什么，您通常会击败任何基于比较的裤子排序算法。

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

编辑：以上内容仅适用于内部排序，您有足够的 RAM 来存储整个输入。外部排序（比如溢出到磁盘）通常应该通过一次读取大约一半 RAM 的数据，使用基于非比较的排序，然后写出排序结果来完成。一直小心将排序与输入和输出重叠。最后，您进行（基于比较的）n 路合并。

于 2013-01-20T18:09:41.307 回答