Morris' Blog

2011-10-29 07:33:45Morris

a233. 排序法~~~ 挑戰極限

留言 1 收藏 0 推薦 0

內容：

排序法~~~ 挑戰極限
 
顧名思義 就是要把東西排列的 很快

輸入說明：

每筆側資輸入一個正整數 N  ( N <= 1000000 ) 代表有N個正整數要排列
接下來有N的以空白隔開整數

輸出說明：

輸出N個由小到大排列的整數 ( 用空白隔開 )

範例輸入：

5
1 3 7 0 4

範例輸出：

0 1 3 4 7

提示：

					背景知識：			排序法

放心! 前幾筆測資都很友善!!!
但是 BUBBLE SORT , INSERT SORT , SELECTION SORT 將受到挑戰?

出處：

       24TH 成功電研社內考      (管理：stanley17112000)

作法 : 基數排序

/**********************************************************************************/
/* Problem: a233 "排序法~~~ 挑戰極限" from 24TH 成功電研社內考     */
/* Language: C (700 Bytes)                                                       */
/* Result: AC(57ms, 1.5MB) judge by this@ZeroJudge                               */
/* Author: morris1028 at 2011-10-28 21:24:51                                     */
/**********************************************************************************/

#include<stdio.h>
#define    MaxN 1000001
void RadixSort(int *A, int *B, int n) {
    int i, x, d, *T, C[16];
    for(x = 0; x < 8; x++) {
        d = x*4;
        for(i = 0; i < 16; i++)        C[i] = 0;
        for(i = 0; i < n; i++)        C[(A[i]>>d)&15]++;
        for(i = 1; i < 16 ; i++)    C[i] += C[i-1];
        for(i = n-1; i >= 0; i--)    B[--C[(A[i]>>d)&15]] = A[i];
        T = A, A = B, B = T;
    }
}
int S0[MaxN], S1[MaxN];
main() {
    int n, a;
    while(scanf("%d", &n) == 1) {
        for(a = 0; a < n; a++)   scanf("%d", &S0[a]);
        RadixSort(S0, S1, n);
        for(a = 0; a < n; a++)   printf("%d ", S0[a]);
        puts("");
    }
    return 0;
}

上一篇：a282. 認真念書

下一篇：a285. 女兒國婚友社