Radix sort
AC (68ms, 1.5MB)
/**********************************************************************************/
/* Problem: a233 "排序法~~~ 挑戰極限" from 24TH 成功電研社內考 */
/* Language: CPP (810 Bytes) */
/* Result: AC(69ms, 1.5MB) judge by this@ZeroJudge */
/* Author: saitor362320 at 2012-09-05 01:31:08 */
/**********************************************************************************/
#include<cstdio>
#include<cstdlib>
#define MAX 1000000
void RadixSort(int a[],int n)
{
int* b;
int exp = 1;
b = (int*) malloc(n*sizeof(int));
// find MAX num
int m = a[0];
for(int i=0;i<n;++i){
if(a[i]>m) m =a[i];
}
// LSD
while( (m/exp)>0 ){
int bucket[10] = {0};
for(int i=0; i<n ; ++i)
bucket[a[i]/exp % 10]++; // save radix in the bucket
for(int i=1; i<10 ;++i)
bucket[i] += bucket[i-1]; // cout the total
for(int i=n-1 ; i>=0 ; --i)
b[--bucket[a[i]/exp %10]] = a[i]; // restore the array from behind
for(int i=0; i<n ; ++i)
a[i] = b[i];
exp *= 10;
}
for(int i=0; i<n ; ++i)
printf("%d ", a[i]);
printf("\n");
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
int* a;
a = (int*) malloc(n*sizeof(int));
for(int i=0; i<n ; ++i)
scanf("%d",&a[i]);
RadixSort(a,n);
}
}