计数排序问题

当输入的元素中的每一个数的大小都是介于0到K之间的整数时，计数排序的时间复杂度可以为O(n)。它的基本思想就是对于每一个输入元素x，确定出小于x的元素的个数，这样我们就可以确定出x元素在最终的输出数组中的位置，这种方法就不需要比较元素的大小了。在排序中我们需要两个辅助数组，一个是用来保存排序结果的B[0...N]，另一个是用来提供临时存储的C[0...K]。下面这段程序是计数排序的一个简单的实现。

在上面的程序中，由于数组A中的数最大为65，所以在这里给C分配了66(0--65)个空间单元。
通过对上面的代码分析我们知道计数排序的时间复杂度为O(N),在实践中，当K=O(N)时，我们常常采用计数排序方法。当然了，由于需要一个临时数组C，所以计数排序的输入元素最好是小范围的整数构成，这样可避免大量的空间浪费。