UVa:11462 Age Sort

물 문 제 는 계수 로 정렬 하면 된다.
 
알고리즘 소개
계수 정렬 은 통 정렬 과 유사 한 것 이다.
정렬 알고리즘
그 장점 은 이미 알 고 있 는 수량 범위 의 배열 을 정렬 하 는 것 이다.이 데이터 범위 의 길 이 를 가 진 배열 C 를 만 듭 니 다. C 의 모든 요소 기록 은 배열 에 해당 하 는 기록 의 개 수 를 정렬 해 야 합 니 다.
계수 정렬 은 비교 에 기반 하지 않 은 선형 시간 이다.
정렬 알고리즘
。입력 한 데이터 에 대한 추가 제한 조건 이 있 습 니 다.
1. 입력 한 선형 표 의 요 소 는 유한 편차 집합 S 에 속한다.
2. 입력 한 선형 표 의 길 이 는 n 이 고 | S | = k (집합 S 에서 요소 의 전체 항목 은 k 임 을 나타 내 는 것) 는 k = O (n) 입 니 다.
이 두 가지 조건 하에 서 계수 정렬 의 복잡성 은 O (n) 이다.
 
 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
   int n;
   while(scanf("%d",&n)&&n)
   {
       int a[105]={0};
       for(int i=0;i<n;++i)
       {
           int x;
           scanf("%d",&x);
           a[x]++;
       }
       bool fir=false;
       for(int i=1;i<=100;++i)
       {
           if(!fir&&a[i])
           {
               printf("%d",i);
               a[i]--;
               fir=true;
           }
           while(a[i]--) printf(" %d",i);
       }
       printf("
");
   }
   return 0;
}

 
 
가속 판:

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cctype>
#include <cstring>
using namespace std;
inline int readint()
{
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    int x=0;
    while(isdigit(c))
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int buf[10];
inline void writeint(int i)
{
    int p=0;
    if(i==0) p++;
    else while(i)
    {
        buf[p++]=i%10;
        i/=10;
    }
    for(int j=p-1;j>=0;--j)
    putchar('0'+buf[j]);
}
int main()
{
    int n,x,c[101];
    while(n=readint())
    {
        memset(c,0,sizeof(c));
        for(int i=0;i<n;++i)
        c[readint()]++;
        int first=1;
        for(int i=1;i<=100;++i)
         for(int j=0;j<c[i];++j)
         {
             if(!first) putchar(' ');
             first=0;
             writeint(i);
         }
         putchar('
');
    }
    return 0;
}