bucketsort.cpp (2)

Bai toan

Sap xep mot day so nguyen khong am su dung bucket sort ket hop voi ham sort.

Do phuc tap

Code nay cua Nguyen Tien Trung Kien

#include <assert.h>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define long long long

#define B 1024

#define N 10000007

int n, a[N], b[N];

void bucket_sort(int a[], int n, int Shift) {

    if (n + B >= n * 20) {

        sort(a + 1, a + n + 1);

        return;

    }

    int *a1 = new int[n + 1];

    int First[B], Last[B], Count[B];

    memset(Count, 0, sizeof Count);

    for (int i = 1; i <= n; ++i)

        Count[(a[i] >> Shift) & (B - 1)]++;

    First[0] = Last[0] = 0;

    for (int i = 1; i <= B - 1; ++i)

        First[i] = Last[i] = First[i - 1] + Count[i - 1];

    for (int i = 1; i <= n; ++i)

        a1[++Last[(a[i] >> Shift) & (B - 1)]] = a[i];

    if (Shift)

        for (int i = 0; i < B; ++i)

            bucket_sort(a1 + First[i], Count[i], Shift - 10);

    for (int i = 1; i <= n; ++i)

        a[i] = a1[i];

    delete[] a1;

}

main() {

    scanf("%d", &n);

    //  f1(i,n) a[i]=rand();

    for (int i = 1; i <= n; ++i)

        scanf("%d", &a[i]);

    bucket_sort(a, n, 30);

    for (int i = 1; i <= n; ++i)

        printf("%d\n", a[i]);

}

Nhan xet

Code nay da dung de nop cho mot bai tren SPOJ.