1

大多数时候，我们使用内置库进行排序，它们是通用的。但大多数时候，我们也是根据数字索引或其他可以在索引中转换的值进行排序的。如果我没记错的话，排序数字是 O(n)。那么为什么我们根本不使用数字排序算法呢？

4

2 回答 2

3

真的有必要吗？

我不太确定（单个）整数（或浮点数，尽管大多数数字排序需要/对整数有效）是“大部分时间”排序的内容，因此有一些算法只适用于整数似乎不是特别有用。我说“单个”整数，而不是包含多个整数、数字、字符串或其他任何东西的（字符串或）对象（或等价物）。

更不用说（我相信）任何现实世界程序的瓶颈（主要目的不仅仅是对数据进行排序）（嗯，其中大多数）不应该是使用排序对“单个”数字进行O(n log n)排序。更改数据的表示方式以消除对排序的需求而不是减少log n因素可能会更好。

数字排序

这是一种常见的误解，但实际上没有排序算法（数字或其他）是最坏的情况O(n)。总会有一些额外的参数在起作用。对于基数排序，数字的长度是决定因素。对于短数组中的长数字，这个长度很容易超过log n，导致性能比O(n log n)排序差（见下面的测试）。

现在数字排序比任何基于比较的排序算法都有用并且更好，因为您的数据在大多数（但不是全部）时间都符合特定约束 （通过查看任何体面的参考给出的复杂性，您应该很容易看到是什么决定了是否会好 - 例如O(kN)意味着长数字可能会导致它花费更长的时间，像处理重复这样的事情会更加微妙）。

那么，为什么不使用它们呢？

如果没有广泛的实际经验/理论知识，您不太可能选择最有效的算法，您完全有可能会发现自己遇到的问题是，理论上应该很棒的算法严重低于标准算法对于您的数据，由于一些微妙的因素。

因此，标准库不会让您选择不正确的排序，并且可能会因为您的数据不符合某些约束而导致性能很差。图书馆的分类往往是全面的，但并不专门针对特定的数据集。虽然我确信也有一些库专注于排序算法，允许您从广泛的算法中进行选择，但您的普通程序员 Joe 可能不想/不应该接触到这种选择。

另请注意，虽然它们通常不包含在库中，但应该很容易找到/编写您希望使用的任何（流行）排序的实现......然后您应该在足够的样本上对库排序进行基准测试在提交之前您的数据。

有点随机的测试

这绝不是为了成为一个结论性的、100% 正确的测试，它具有基数排序和快速排序的最佳实现，以使之成为现实。更多的是表明数据的样子在任何给定算法的性能中都起着重要作用。

这是我在几分钟的搜索中找到的唯一一个不错的基准，包括基数排序。

我运行了代码，发现了这个：（数字范围0-2147483646）

（时间单位与纳秒有关，并不真正转换为秒）

ArraySize Radix     Quick
10        1889      126       
100       2871      2702      
1000      18227     38075     
10000     360623    484128    
100000    2306284   6029230

对于大小小于 100 的大量数字和数组（正是我上面所说的），快速排序更快。有趣但没什么了不起的。我的意思是谁在乎排序少于 100 个数字的性能？

但是，看看当我将数字范围更改为0-99时发生了什么：

ArraySize Radix     Quick
10        1937      121       
100       8932      2022      
1000      29513     14824     
10000     236669    125926    
100000    2393641   1225715

对于合理大小的数组（1000-100000 个元素），快速排序始终比基数排序快 2 倍左右。

你一定在想——“到底是什么？我认为基数排序应该擅长这些。我的意思是......只有 2 位数字。为什么快速排序比上述情况快得多？” 确切地。这就是“广泛的现实世界经验/理论知识”的用武之地。我怀疑它与每个算法/实现处理重复的程度有关。但其中一半可能是因为我可能没有针对较小范围优化基数排序实现（不知道我们这样做了吗？嗯，这是反对尝试在库中使用通用基数排序的另一个原因）

现在 0-99 可能也不是您的典型数据集，总体而言，基数排序可能仍然更好，但是您需要从所有这些中删除：

大约有无数种排序算法。他们擅长的领域差别很大。不要指望标准库为您提供每个功能。基于比较的排序可以对任何可比较的数据类型进行排序（并且对于大多数实际应用来说足够快），而不是只能对数字进行排序的数字排序。因此，在您的（如您，编写它的人）库中拥有一个（或 2 个，如 Java 所具有的）基于比较的排序是首选。

于 2013-05-26T13:14:18.387 回答
1

基本上，我们使用基于比较的排序算法，因为它更容易。从工程的角度来看，能够提供比较功能并对数据进行分类是一个巨大的胜利，即使您为此付出了速度。

请记住，基于 O(n log n) 比较的排序界限计算比较，而不是总运行时间。例如，如果您正在对字符串进行排序，则比较所花费的时间可能与被比较的字符串的长度呈线性关系。

一个常见的误解（我在另一个答案中看到了回应）是，当您对中等数量的长数字进行排序时，基于比较的排序最终会具有更快的渐近复杂性。说它们每个都是 k 字节。这根本不是真的。您进行 n log(n) 次比较，每次比较都需要 O(k) 时间，总体复杂度为 O(kn log n)。这比 O(kn)更糟。

设计一个快速基数排序比理论说的要难一些。虽然理论要求您应该选择尽可能大的基数，但在您选择的基数和在对输入流进行分区时实现的局部性之间存在权衡。更大的基数意味着更少的通过次数，但也意味着更少的本地内存使用。

于 2013-05-26T13:23:55.967 回答