计数排序是个好东东,有点空间换时间的感觉,不过,还是得要求输入的数不能太大,想想感觉好像是有啥离散化的方法来解决这个问题呢。哎,学的东西少了,也不知道该怎么处理。
#include<stdio.h>
#include<string.h>
#include<math.h>
int a[105],b[105],c[100005];
int main()
{
int n,i,k;
scanf("%d",&n);
k=0;
for (i=1; i<=n ; i++ )
{
scanf("%d",&a[i]);
k=a[i]>k?a[i]:k;
}
memset(c,0,sizeof(c));
for (i=1; i<=n ; i++ )
c[a[i]]++;
for (i=1; i<=k ; i++ )
c[i]+=c[i-1];
for (i=1; i<=n ; i++ )
{
b[c[a[i]]]=a[i];
c[a[i]]--;
}
for (i=1; i<=n ; i++ )
printf("%d ",b[i]);
return 0;
}
这个是线性时间的,时间复杂度根据输入数据的大小来确定。挺好的一个思想。