忘记了 17 年学的东西。。。看来线性排序还是实用性不强嘛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int BIT = 16;
const int U = 65536;
int N, cnt[U], A[MAXN][2];
inline int getd( int x, int d ) {
return (x >> (d * BIT)) & (U - 1);
}
inline void radix_sort() {
For(d, 0, 2){
memset(cnt, 0, sizeof(cnt));
For(i, 0, N) cnt[getd(A[i][d], d)]++;
For(i, 1, U) cnt[i] += cnt[i - 1];
for (int i = N - 1;i >= 0;i--) A[--cnt[getd(A[i][d], d)]][d ^ 1] = A[i][d];
}
For(i, 0, N) printf("%d%c", A[i][0], i == N - 1 ? '\n' : ' ');
}
int main() {
scanf("%d", &N);
For(i, 0, N) scanf("%d", &A[i][0]);
radix_sort();
return 0;
}
編集日 閲覧数