計數(shù)排序是個好東東，有點(diǎn)空間換時間的感覺，不過，還是得要求輸入的數(shù)不能太大，想想感覺好像是有啥離散化的方法來解決這個問題呢。哎，學(xué)的東西少了，也不知道該怎么處理。
#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;
}
這個是線性時間的，時間復(fù)雜度根據(jù)輸入數(shù)據(jù)的大小來確定。挺好的一個思想。