bucketsort.cpp
Bài toán
Sắp xếp một dãy số nguyên với các phần tử nằm trong khoảng 1..1000000 bằng bucket sort và counting sort.
Độ phức tạp
O(n+B*B) trong đó B là số bucket
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define long long long
#define N 1000006
#define B 1024
void count_sort(int a[], int n) {
static int a1[N], First[B], Last[B], Count[B];
for (int i = 0; i < B; ++i)
First[i] = Last[i] = Count[i] = 0;
for (int i = 1; i <= n; ++i)
Count[a[i] % B]++;
for (int i = 1; i <= B - 1; ++i)
Last[i] = First[i] = First[i - 1] + Count[i - 1];
for (int i = 1; i <= n; ++i)
a1[++Last[a[i] % B]] = a[i];
for (int i = 1; i <= n; ++i)
a[i] = a1[i];
}
void bucket_sort(int a[], int n) { // 1-based
static int a1[N], First[B], Last[B], Count[B];
for (int i = 0; i < B; ++i)
First[i] = Last[i] = Count[i] = 0;
for (int i = 1; i <= n; ++i)
Count[a[i] >> 10]++;
for (int i = 1; i <= B - 1; ++i)
Last[i] = First[i] = First[i - 1] + Count[i - 1];
for (int i = 1; i <= n; ++i)
a1[++Last[a[i] >> 10]] = a[i];
for (int i = 0; i < B; ++i)
count_sort(a1 + First[i], Count[i]);
for (int i = 1; i <= n; ++i)
a[i] = a1[i];
}
int n, a[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
bucket_sort(a, n);
for (int i = 1; i <= n; ++i)
printf("%d\n", a[i]);
}
Nhận xét