代码

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

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);
	list *p = head.next;
	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);
}

评测结果