2011-07-22 22:02:31Morris
RadixSort (基數排序)
寫完才知道, 原來基數排序寫起來很優美, 比起快速排序或者是合併排序,
"單純"數字排序的話, 只需要短短幾行而已, 如果要附上"次排序", 目前沒有想法
一次做 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;
}
"單純"數字排序的話, 只需要短短幾行而已, 如果要附上"次排序", 目前沒有想法
一次做 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;
}