When people say "sorting algorithm" they often are referring to "comparison sorting algorithm", which is any algorithm that only depends on being able to ask "is this thing bigger or smaller than that". So if you are limited to asking this one question about the data then you will never get more than n*log(n) (this is the result of doing a log(n) search of the n factorial possible orderings of a data set).
If you can escape the constraints of "comparison sort" and ask a more sophisticated question about a piece of data, for instance "what is the base 10 radix of this data" then you can come up with any number of linear time sorting algorithms, they just take more memory.
This is a time space trade off. Comparason sort takes little or no ram and runs in N*log(n) time. radix sort (for example) runs in O(n) time AND O(log(radix)) memory.
Think the numbers as three digit numbers where each digit ranges from 0 to n-1. Sort these numbers with radix sort. For each digit there is a call to counting sort which is taking Theta(n+n) time, so that the total running time corresponds to Theta(n).
一组有限范围的数字可以由 RANGE 位的位图表示。 在本例中，位图大小为 500mb，因此对于除大型列表之外的任何内容，最好使用基数排序。 当遇到数字 k 时，设置 bitmap[k] = 1。单次遍历列表，O(N)。
A Set of a limited range of numbers can be represented by a bitmap of RANGE bits. In this case, a 500mb bitmap, so for anything but huge lists, you'd be better off with Radix Sort. As you encounter the number k, set bitmap[k] = 1. Single traversal through list, O(N).
发布评论
评论（8）
还要看看相关的排序：pigeonhole sort 或 计数排序，以及基数排序 正如 Pukku 提到的。
Also take a look at related sorts too: pigeonhole sort or counting sort, as well as radix sort as mentioned by Pukku.
查看基数排序。
Have a look at radix sort.
当人们说“排序算法”时，他们通常指的是“比较排序算法”，这是任何仅依赖于能够询问“这个东西比那个更大还是更小”的算法。 因此，如果您仅限于询问有关数据的这一问题，那么您将永远不会得到超过 n*log(n) （这是对数据集的 n 阶乘可能排序进行 log(n) 搜索的结果） 。
如果您可以摆脱“比较排序”的限制并询问有关一段数据的更复杂的问题，例如“该数据的以 10 为底的基数是多少”，那么您可以想出任意数量的线性时间排序算法，它们只是占用更多内存。
这是一个时间空间的权衡。 比较排序需要很少的内存或不需要内存，并且运行时间为 N*log(n) 。 基数排序（例如）在 O(n) 时间和 O(log(radix)) 内存中运行。
When people say "sorting algorithm" they often are referring to "comparison sorting algorithm", which is any algorithm that only depends on being able to ask "is this thing bigger or smaller than that". So if you are limited to asking this one question about the data then you will never get more than n*log(n) (this is the result of doing a log(n) search of the n factorial possible orderings of a data set).
If you can escape the constraints of "comparison sort" and ask a more sophisticated question about a piece of data, for instance "what is the base 10 radix of this data" then you can come up with any number of linear time sorting algorithms, they just take more memory.
This is a time space trade off. Comparason sort takes little or no ram and runs in N*log(n) time. radix sort (for example) runs in O(n) time AND O(log(radix)) memory.
维基百科展示了许多不同的排序算法及其复杂性。 你可能想看看
wikipedia shows quite many different sorting algorithms and their complexities. you might want to check them out
这非常简单，如果 n=2 并且数字是唯一的：
复杂性=> O(2n)
否则，使用基数排序：
复杂度 => O(kn)（希望如此）
It's really simple, if n=2 and numbers are unique:
Complexity => O(2n)
Otherwise, use Radix Sort:
Complexity => O(kn) (hopefully)
将这些数字视为三位数字，其中每个数字的范围从 0 到 n-1。 使用基数排序对这些数字进行排序。 对于每个数字，都会调用计数排序，该排序需要花费 Theta(n+n) 时间，因此总运行时间对应于 Theta(n)。
Think the numbers as three digit numbers where each digit ranges from 0 to n-1. Sort these numbers with radix sort. For each digit there is a call to counting sort which is taking Theta(n+n) time, so that the total running time corresponds to Theta(n).
一组有限范围的数字可以由 RANGE 位的位图表示。
在本例中，位图大小为 500mb，因此对于除大型列表之外的任何内容，最好使用基数排序。 当遇到数字 k 时，设置 bitmap[k] = 1。单次遍历列表，O(N)。
A Set of a limited range of numbers can be represented by a bitmap of RANGE bits.
In this case, a 500mb bitmap, so for anything but huge lists, you'd be better off with Radix Sort. As you encounter the number k, set bitmap[k] = 1. Single traversal through list, O(N).
类似的算法是可能的：
它是线性复杂度的唯一可能的算法，但它的复杂度为 O(k*N) by ram（N - 数组元素数，k - 元素的 len）
alike algo is possible:
It's alone possible algo for linear complexity, but it has complexity O(k*N) by ram (N - number array elements, k -- element's len)