所有学习过排序算法的人都知道， 快速排序（Quick Sort）的时间复杂度为 O(n*lg(n))， n 为需要排序的数的个数； 而计数排序（Counting Sort）的时间复杂度为 O(m+n)，n 为需要排序的数的个数，m 为数据的范围。

看起来计数排序时间复杂度要比快速排序的时间复杂度要低，但是实际上我接下来就会证明计数排序时间复杂度并不比快速排序低，甚至会更高。

问题的复杂度的一般化定义是关于输入字串的长度 w 的函数，也就是说要等价于待排序的数组在内存中的长度， 所以 w = n*lg(m)。 由于无论何种排序算法，都需要完整的读入整个字符串，并输出同等长度的字符串，所以任何排序算法的时间复杂度至少为 O(w)。

故，计数排序的时间复杂度实际为 O(w+m+n+w) = O(w+m)，其至少为 O(w)。当 n 很小，但是 m 很大的时候，会变为 O(m)。

再来看快速排序：

标准的快速排序算法在每次递归处理的时候， 首先调用 Partition 函数，选取一个数，将小于它的数放到它的左边，将大于等于它的数放到它的右边， 这个函数的时间复杂度为 O(n)。 然后递归处理左右两边，整体时间复杂度为 O(n*lg(n))。

考虑一种拥有对相同元素有特殊处理的快速排序算法。 我们需要修改 Partition 函数，在选取一个数后，将小于它的数放到左边，接下来是与它相等的数，之后是大于它的数， 这样，所有相等的数只会处理一遍，函数的时间复杂度仍然为 O(n)。 整体的时间复杂度变为 O(n*lg(p))，其中 p 为待排序的数字中不同的数的个数。

所以我们可以知道 1 <= p <= m，因为我们数据范围只有 m，至多有 m 个不同的数。

于是快速排序的时间复杂度实际为 O(n*lg(m)) = O(w)。

所以计数排序不小于快速排序的时间复杂度 O(w)，当 m 很大的时候，甚至比快速排序复杂度更高。