百搭背心★瘋搶↘120金豪禮★拿現金最實在!這畫面也太叫人垂涎欲滴!睽違25天終開會 立院...
2011-07-22 22:02:31 人氣(555) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

RadixSort (基數排序)

0
收藏
0
推薦

寫完才知道, 原來基數排序寫起來很優美, 比起快速排序或者是合併排序,
"單純"數字排序的話, 只需要短短幾行而已, 如果要附上"次排序", 目前沒有想法
一次做 4 位, 意思是做 4 bits, 從尾部開始做
範例輸入 :
5 2 4 //5 個數字, 排序部分[2]~[4]
5 4 3 2 1 //儲存格[0]~[4],
範例輸出 :
5 4 1 2 3

以下程式碼只有跑 4 次 4 bits, 也就是說, 最大可行排序為 16 bits


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

RadixSort基數排序
台長:Morris
人氣(555) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 各類演算法與示範題目 |
此分類下一篇:分堆插入法 (bin+insert)
此分類上一篇:Suffix Array (SA 倍增演算法) + 高度數組建造

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文