代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct list
{
    unsigned data;
    list* next;
};

struct aa
{
    list* head;
    list* tail;
} ans[65536];

unsigned findpos(unsigned num,unsigned jishu,int g)
{
    if(g == 0)
        return num&jishu;
    return num>>16;
}
int do_once(unsigned *a,int n,unsigned jishu,int g)
{
    int size = sizeof(list);

    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);
        node->data = a[i];
        node->next = 0;

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

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

    }
}

void sort(unsigned *a, int n)
{
    unsigned jishu = 65535;
    do_once(a,n,jishu,0);
    do_once(a,n,jishu,1);
}

评测结果