代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include<stdlib.h>

typedef unsigned int u32;
typedef unsigned long long u64;

struct list
{
    unsigned data;
    //list* next;
    int next;
}*alist;

struct aa
{
    int  head;
    int  tail;
} ans[65536];

unsigned findpos(unsigned num,unsigned jishu,int g)
{
    if(g == 0)
        return num&jishu;
    return num>>16;
}

void do_once(unsigned *a,int n,unsigned jishu,int g)
{

    int point = 0;
    memset(ans,0,sizeof(ans));
    for(int i = 0; i < n; i ++)
    {

        unsigned pos = findpos(a[i],jishu,g);
        //	unsigned pos = jishu&a[i];
        //list *node = (list*)malloc(size);
        point++;
        //list node = alist[point];
        //node.data = a[i];
        //node.next = 0;

        alist[point].data = a[i];
        alist[point].next = 0;

        if(ans[pos].head == 0)
        {
            ans[pos].head = point;
            ans[pos].tail = point;
            continue;
        }

        int p = ans[pos].tail;
        alist[p].next = point;
        ans[pos].tail = point;

        //ans[pos].tail.next = node;
        //ans[pos].tail = node;
    }
    int wp=0;
    for(int i = 0; i < 65536; i ++)
    {
        int p = ans[i].head;
        //list *now;
        while(p)
        {
            // printf("%u ",p->data);
            a[wp++] = alist[p].data;
            //now = p;
            p = alist[p].next;
            //free(now);
        }

    }
}
void sort(unsigned *a, int n)
{
    unsigned jishu = 65535;
    alist = new list[n + 1];
    do_once(a,n,jishu,0);
    do_once(a,n,jishu,1);
}

评测结果