Question

给定一个n个数的数组，其中的每个元素都小于n的平方，请设计一个时间复杂度为O(n)的排序算法

如题，请砖家指点，谢谢！
谢谢一楼的答案，让我知道了计数排序这个非比较排序方法。不过“其时间复杂度可以随数据元素范围减小而降低至线性时间内”这句话我不太理解，感觉由于上界是n的平方，时间复杂度还是无法降至线性？
可是在这题中C的大小正是n的平方啊，遍历一次C的所有元素要n的平方次。。难道还不是O(n2)吗？
还有别的答案吗？

Answer 1

可以考虑用计数排序的思想来实现这点，用空间换时间。

其中用A[n]数组代表原始数组，B[n]代表升序排序后的数组，C[n*n]数组用于计数，C[i]值代表小于等于i的元素个数，那么每一次输出排序后的B[i]时，便有B[--C[i]]=i，只是问题中元素的取值范围是n^2以内的，因此造成了这一方法的时间复杂度无形中升至了n^2，但事实上其时间复杂度可以随数据元素范围减小而降低至线性时间内，思想就是空间换取时间，并且只适用于正整数的排序。

#include<iostream>
#define n 10
using namespace std;

int A[n];
int B[n];
int C[n*n];

int main()
{
int nTest;
int i;
cin>>nTest;
while( nTest-- ){
for( i=0 ; i<n ; i++ )
cin>>A[i];

memset( C,0,sizeof(C) );
for( i=0 ; i<n ; i++ )
C[A[i]]++;

for( i=1 ; i<n*n ; i++ )
C[i]+=C[i-1];

for( i=0 ; i<n ; i++ ){
B[C[A[i]]-1]=A[i];
C[A[i]]--;
}
for( i=0 ; i<n ; i++ )
cout<<B[i]<<" ";
cout<<endl;

}
return 0;
}
/*
1
31 77 37 77 37 77 37 77 37 99
31 37 37 37 37 77 77 77 77 99
*/

--------------------------------------------------------
回答补充：
对，正是你想的那样，正因为待排序的数据范围上界达到了n^2的数量级，导致在这个问题中计数排序的效率下降了。
但是，试想一下，上界若不是一个很大的数，举个例子，待排序的数据量n=10^8，而数据范围上界m=10^5，那么按照正常的排序方法时间效率的最低下界为o(nlog(n))，当n=10^8时也是很大的时间开销。而对计数排序而言，此时的时间开销仅仅是o(n),即用于更新数组C[m+1]上了，可以算是在线性时间内完成排序的。