- 解决思路:
- 1.先定义一个数组Arr 然后初始化大小为固定长度:注意:长度必须超过需要排序的数组的长度,不然就没意义了。
- 2.数组初始化全为0.
- 3.遍历需要排序的数组,然后将数组大小作为下标,进行叠加,次数进行叠加
- 4.输出
代码:
#define SIZE 65536
void SuperSort(int * arr,int n)
{
int array_all[SIZE];
//初始化
for (int i = 0; i < SIZE;i++)
{
array_all[i] = 0;//初始化为0;
}
//进行排序
for (int i = 0; i < n; i++)
{
array_all[arr[i] + 100] = arr[arr[i] + 100]+1; //赋值次数,处理负数情况
}
//输出
for (int j = 0; j < SIZE; j++)
{
if (array_all[j]!=0)
{
for(int k = 0; k <array_all[j]; k++)
{
cout << j-100 << endl;
}
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int array_[] = {6, 4, -3, 5, -2, -1, 0, 1, -9}; //定义一个定长数组
//采用排序,时间复杂度O(n),空间复杂度O(1)
SuperSort(array_,9);
system("pause");
return 0;
}
运行结果: