线性排序算法

Question

我是学习算法的新手--我也不是计算机科学专业的毕业生。

然而，在阅读线性排序非比较算法时，我可以理解基数排序是计数排序的扩展。

我不清楚的是计数排序的限制。

当计数排序似乎可以避免O(n*logn)比较时，我为什么要使用基数排序呢？

当然，它看起来确实是一个更简单的实现。

Answer 1

假设有人给了你一个要排序的整数列表。除了它包含整数之外，您对它一无所知。

如果幸运的话，这个列表可能会包含相当严格的范围内的数字。如果要对-100到100之间的整数进行排序，那么创建一个具有该大小的数组来进行计数排序并不是一件坏事。

但是，如果有一个数字非常大或非常小，您现在必须扩展数组的界限，以便对整个输入进行计数排序。如果您真的想对所有可能的整数进行排序(并且您在创建数组之前不知道值的范围，除非您先找到它)，则需要创建一个大小为2 * max_int的数组(用于负整数和正整数)。

基数排序很好，因为您永远不需要创建一个大小大于数字范围(0-9)的数组。

Answer 2

计数排序算法(包括基数)仅适用于可数元素。不幸的是，实数是不可计数的，所以你不能很容易地对“浮点数”或“双精度”值进行排序。想象一下，您需要对测量的温度列表进行排序。

现在关于可计数的数量(像整数)，你有一个基本的错误，假设从数组中获取一个元素是O(1)。这不是真的。当您有大小为N的数组时，将指针设置到此数组中的成本为O(log(N))。换句话说，要访问元素Arrayi，您需要定义'i‘，为了定义'i’的值，您需要设置log(i)位。只要N很小(例如，使用计数排序对-100..100之间的值进行排序时为200 )，我们就假设than log(N)是常量，并忽略它。但是如果你想对整数进行排序，那么你的计数数组将会很大(大小为: 2*MAX_INT)，日志(2*MAX_INT)可能是一个很大的数字(比如32)。因此，假设您有一个大小为100的数组:整数的A100。使用O(N*log(N))排序需要O(100*log(100))个比较。但是在使用计数排序时，您创建了一个非常大的计数数组(例如，对于64位整数，您需要2^64 )，您的总时间是O(N*log(2^64))，这实际上大于O(100*log(100))。这听起来很疯狂，但这是真的。想想看，在开始计数之前，您需要将整个计数数组设置为零-即2^64次操作，这比整个O(100*log(100))多得多……还有一个巨大的内存浪费..。

总而言之:即使你有无限的内存可用，运行时间也不是真正的O(N)。它实际上是将计数数组置零并执行计数的开销：

O(MAX_INT) + O(N*log(MAX_INT))

通常，对于任何合理的N，这都比O(N*log(N))多得多，所以计算排序是不切实际的。实用的唯一情况是当值的范围很小时(如-100..100)

O(MAX_INT) + O(N*log(MAX_INT))

成为O(200) + O(N*log(200)) ~ O(N)

基数排序使您可以节省一些内存和将巨大的计数数组置零的成本，但您仍然不会真正失去log()因子，因为许多范围日志具有log(X)位，并且您仍然具有通常大于-X..X (N)的MAX_INT(Log)，其中N是要排序的数组的大小。

Answer 3

计数排序的复杂度为O(max - min)，其中min，max是要排序的最小和最大整数。如果此范围比要排序的数组大小大得多，则基数排序更好。