Question

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

Answer 1

题目：如何对n个不重复出现的整数序列进行排序,已知这些数的范围为(0-65535),要求时间复杂度O(n),空间复杂度O(1)分析：可以申请一个大小为65536的数组A,数组的x下标代表数字x,A[x]代表x 在整数序列中出现的次数.扫描一遍整数序列就可以完成对该整数序列的排序,时间复杂度为O(n)应为已知范围,申请大小为65536的数组,大小为常量,所以空间复杂度为O(1)代码：1:#include 2:#define SIZE 65536 3:void rangeSort(int *array,int len) 4:{ 5:int data[SIZE] ; 6:int i = 0 ; 7:int j = 0 ; 8:memset(data,0,SIZE*sizeof(int)) ; 9:for(i=0;i