题目描述：

如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)

 

解析：

利用计数排序法，设置一大小为65536的int数组，范围a[0]~a[65535]，并初始为0，然后遍历n个数，假设这n个数在数组array[0...n-1]中，则i取值从0到n-1同时执行a[array[i]]++，最后再依照顺序读数组a，遇到不为0时，将对应的下标读回数组array，计数是几次就读几次，覆盖原有数，这样得出的array即为排序所求

因为空间复杂度大小已知，为65536，执行循环次数约为n+65536 ，所以其空间复杂度为O(n)，空间复杂度O(1),代码略