我是学习算法的新手——我也不是计算机科学专业的毕业生。
但是，在阅读线性排序非比较算法时，我可以理解基数排序是计数排序的扩展。
我不清楚的是计数排序的限制。
当计数排序似乎可以达到我需要避免 O(n*logn) 比较的目的时，为什么我要进行基数排序？
它似乎确实是一个更简单的实现。
问问题
6403 次
5 回答
3
想象一下有人给了你一个整数列表来排序。除了它包含整数之外，您对此一无所知。
如果幸运的话，该列表可能包含相当严格的范围内的数字。如果您要对所有介于 -100 和 100 之间的整数进行排序，那么创建一个具有该大小的数组来进行计数排序一点也不坏。
但是，即使一个数字非常大或非常小，您现在也必须扩展数组的边界，以便对整个输入进行计数排序。如果你真的想对所有可能的整数进行排序（并且在创建数组之前你不知道值的范围，除非你先找到它），你需要创建一个大小数组2 * max_int（对于负整数和正整数）。
基数排序很好，因为您永远不需要创建大小大于数字范围 (0-9) 的数组。
于 2013-07-14T17:56:04.823 回答
2
计数排序算法（包括 Radix）仅适用于可数元素。不幸的是，实数不可数，因此您无法轻松地对“浮点”或“双精度”值进行排序。想象一下，您需要对测得的温度列表进行排序。
现在关于可数数量（如整数），假设从数组中获取元素是 O(1)，你有一个基本错误。这不是真的。当你有一个大小为 N 的数组时，将指针设置到这个数组中的成本是 O(log(N))。换句话说，要访问元素 Array[i]，您需要定义“i”，而要定义“i”的值，您需要设置 log(i) 位。只要 N 很小（比如 200 用于使用计数排序在 -100..100 之间排序值），我们假设 log(N) 是常数并忽略它。但是如果你想对整数进行排序，那么你的计数数组会很大（大小为：2*MAX_INT）log(2*MAX_INT) 可能是一个很大的数字（比如 32）。所以假设你有一个大小为 100 的数组：A[100] 的整数。使用 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))
通常这比O(N*log(N))任何合理的 N 都多，因此计数排序是不切实际的。唯一可行的情况是值的范围很小（如 -100..100）并且
O(MAX_INT) + O(N*log(MAX_INT))
变成O(200) + O(N*log(200)) ~ O(N)
基数排序使您可以节省一些内存和将庞大的计数数组归零的成本，但您仍然没有真正失去 log() 因子，因为许多范围 -X..X 具有 log(X) 数字，而您是仍然有 log(MAX_INT) 通常大于 log(N) ，其中 N 是您要排序的数组的大小。
于 2013-07-14T18:17:48.967 回答
1
计数排序的复杂度为 O(max - min)，其中 min,max 是要排序的最小和最大整数。如果此范围远大于要排序的数组的大小，则基数排序更好。
于 2013-07-14T18:00:00.763 回答
1
我不同意其中一些答案。First Radix Sort 可以对双精度和浮点数进行排序。我已经做到了，它仍然比比较排序快得多。
对于操作员，您可以通过查看我之前写的这篇文章了解更多信息。它总是最好的线性时间排序。
于 2013-07-15T06:40:57.700 回答
0
当人们谈论算法时，他们通常以时间和内存要求来表达算法的性能。
正如您所观察到的，计数排序很棒。它以线性时间运行。
但它也需要O(N)内存要求。
当我们寻找算法时，我们经常会看到内存和时间复杂度之间的这种权衡。通过使用更多内存，我们可以获得更好的运行时间。
因此，尽管计数排序具有更好的时间复杂度，但它需要与输入大小成比例的空间，这使得在大多数情况下使用它是不切实际的。
作为一个更严重的问题，你需要事先知道输入中数字的范围。当然，它的编码简单而优雅，但实际使用时，它是有限的。
于 2013-07-14T17:49:11.337 回答