/*
桶子法排序的主要思想：（限正整数）
从个位数起向左一位一位的排过去，最终把所有的数都排列完成，
排的是位数，而不是整个数。
时间复杂度：O(n)
*/
#include<cstdio>
#include<cstdlib>
#define LENGTH 4//mask size
#define MAX 16
#define LOOP sizeof(int)*8/LENGTH//整数的位数

using namespace std;

typedef struct Node
{
	int data;//original data
	int x;//working data
	struct Node *next;
}Node;

Node *head;

struct cell
{
	Node *first;
	Node *last;
}Bucket[MAX];

int mask=0x0F;

Node* ListGenerate(int input[],int n)//根据输入数组生成一个链表 
{
	Node *first,*last,*temp;
	int i;
	first=last=(Node *)malloc(sizeof(Node));
	if(!first)
	{
		printf("No enough memory!\n");
		exit(-1);
	}
	first->data=first->x=input[0];
	first->next=NULL;
	for(i=1;i<n;i++)
	{
		temp=(Node *)malloc(sizeof(Node));
		if(!temp)
		{
			printf("No enough memory!\n");
			exit(-1);
		}
		temp->data=temp->x=input[i];
		temp->next=NULL;
		last->next=temp;
		last=temp;
	}
	return first;
}

void Distribute(void)//根据数据各个位上的数字散列到桶中
{   //如果把输入数据看成是十进制的，则应有10组（0-9），如果最多5位数
	Node *temp;//则要分组，收集5次，一次1位；但有更好地办法，把那个数
	int index;//看成16进制，则一位的值为0-15，所以每次分组时用低4位
	while(head!=NULL)//与mask进行&操作，以取出低位的值
	{
		index=(head->x)&mask;
		(head->x)>>=LENGTH;
		if(Bucket[index].first==NULL)
			Bucket[index].first=Bucket[index].last=head;
		else
		{
			(Bucket[index].last)->next=head;
			Bucket[index].last=head;
		}
		temp=head->next;
		if(head->next!=NULL)
			head->next=NULL;
		head=temp;
	}
}

void Recollect(void)//从桶中合并数据到链表
{
	int i,j;
	for(i=0;i<MAX&&Bucket[i].first==NULL;i++)
		;
	head=Bucket[i].first;
	for(j=i+1;j<MAX;j++)
	{
		if(Bucket[j].first!=NULL)
		{
			(Bucket[i].last)->next=Bucket[j].first;
			i=j;
		}
	}
}

void PutBack(int input[])//存回数组
{
	Node *temp;
	int i;
	for(i=0;head!=NULL;i++)
	{
		input[i]=head->data;
		temp=head->next;
		free(head);
		head=temp;
	}
}

void BucketSort(int input[],int n)//排序
{
	int i,j;
	head=ListGenerate(input,n);
	for(i=1;i<=LOOP;i++)
	{
		for(j=0;j<MAX;j++)
			Bucket[j].first=Bucket[j].last=NULL;
		Distribute();
		Recollect();
	}
	PutBack(input);
}

int main(int argc,char *argv[])
{
	int input[]={122,433,234,786,34,23,536,2346,7424,13};
	BucketSort(input,sizeof(input)/sizeof(int));
	for(int i=0;i<sizeof(input)/sizeof(int);i++)
		printf("%d\n",input[i]);
	return 0;
}