基数排序

基数排序的复杂度可以写成：O(k(n+2^logMax/k)，k是维数，n是数据个数，Max是数的最大值。现在需要对10M个32位正整数排序，则可以令k=2，则复杂度为O(2(n+2¹⁶))=O(n)。具体来说，先按低16位进行第一趟排，然后对结果按高16位排，这种排法与32位同时排是等价的。实现时需要链表，因此辅助开销比较大，而时间比std::sort减少了1半多。

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
    #include "local.h"
#endif
#define X first
#define Y second
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define mset(a, x) memset(a, x, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
typedef long long ll;
template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);}
template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}

const int maxn = 1e7 + 7;

int seq[maxn];
int top;
struct HashList {
public:
    HashList() { clr(); }
    void clr() {
        sz = 1;
        memset(head, 0, sizeof(head));
    }
    void ins(int val, int pos) {
        hlist[sz] = Node(val, head[pos]);
        head[pos] = sz ++;
    }
    void get(int a[]) {
        for (int i = 0; i < 0x10000; i ++) {
            int h = head[i];
            top = 0;
            while (h) {
                seq[top ++] = hlist[h].val;
                h = hlist[h].next;
            }
            while (top) *a ++ = seq[-- top];
        }
    }
private:
    struct Node {
        int val;
        int next;
        Node(int val = 0, int next = 0)  {
            this->val = val;
            this->next = next;
        }
    };
    Node hlist[maxn];
    int sz;
    int head[1 << 16];
};


int a[maxn];
HashList hl;

void sortint(int *p, int *q) {
    int n = q - p;
    for (int i = 0; i < n; i ++) {
        hl.ins(p[i], p[i] & 0xffff);
    }
    hl.get(p);
    hl.clr();
    for (int i = 0; i < n; i ++) {
        hl.ins(p[i], (p[i] >> 16) & 0xffff);
    }
    hl.get(p);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int n = 10000000;
    for (int i = 0; i < n; i ++) {
        a[i] = rand() * rand();
    }
    Timer ok;
    sort(a, a + n);
    ok.get();
    ok.start();
    sortint(a, a + n);
    ok.get();
    return 0;
}