分类
Algorithm C++

松式基数排序

遥想当年WC2017时候被吓到的场景…

#include <bits/stdc++.h>
inline void sort(unsigned *a, int len)
{
    unsigned b = malloc(sizeof(unsigned ) * len);
    int sum[256] = {0}, sum1[256] = {0}, sum2[256] = {0}, sum3[256] = {0};
    for (int i = 0; i < len; i++)
    {
        ++sum[a[i] & 255];
        ++sum1[(a[i] >> 8) & 255];
        ++sum2[(a[i] >> 16) & 255];
        ++sum3[a[i] >> 24];
    }
    for (int q = 1; q <= 255; ++q)
    {
        sum[q] += sum[q - 1];
        sum1[q] += sum1[q - 1];
        sum2[q] += sum2[q - 1];
        sum3[q] += sum3[q - 1];
    }
    for (int q = len - 1; q >= 0; --q)
        b[--sum[a[q] & 255]] = a[q];
    for (int q = len - 1; q >= 0; --q)
        a[--sum1[(b[q] >> 8) & 255]] = b[q];
    for (int q = len - 1; q >= 0; --q)
        b[--sum2[(a[q] >> 16) & 255]] = a[q];
    for (int q = len - 1; q >= 0; --q)
        a[--sum3[b[q] >> 24]] = b[q];
    free(b);
    return;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注