题目描述
对n个数进行排序，要求时间复杂度为O(n)，空间复杂度为O(1)。
题目解答
我们知道，通常使用到的排序方法在时间复杂度上最好为O(nlogn)，所以这道题目看起来是不可能实现的。
既然有这么一种算法的存在，那她肯定有一种使用限制在里面。这里的限制条件为： ` 要排序的数组元素不能过大。`
假设数字范围在0~65535范围内，定义一个数组count[65536]，这里因为空间元素是常量，并且不是很大，所以空间复杂度满足条件。
假设有以下一组数字：
100
200
300
0
45
...
对于每个数字，计算count，即出现的次数：
count[100]++;
count[200]++;
count[300]++;
count[0]++;
count[45]++;
...
最后得出来的count数组，只需要遍历一遍就可以输出排序结果了，并且时空复杂度都满足题目要求。