////////////////////////////////////////////////////////////////
//                                                            //
//題目：桶排序                                                //
//學(xué)號(hào)：SA04225140                                            //
//作者：朱磊                                                  //
//                                                            //
////////////////////////////////////////////////////////////////


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <sys/timeb.h>

#define LEN sizeof(struct bucket)  //定義結(jié)構(gòu)體長(zhǎng)度
#define BUC struct bucket  //建立結(jié)構(gòu)體名稱
#define NUM 100000    //按要求建立十萬數(shù)組

//定義結(jié)構(gòu)體，包括小數(shù)和指向下個(gè)鏈表的指針
BUC{
	double num;
	BUC *next;
};


double *a;  //等待排序的數(shù)組
BUC *b,*e; //保存桶排序的結(jié)果
BUC *p1[NUM],*p2[NUM],*p;  //建立動(dòng)態(tài)鏈表的指針
BUC *c; //空指針，用來標(biāo)志每一行鏈表的結(jié)束

//產(chǎn)生一個(gè)含有12位小數(shù)的隨機(jī)數(shù)
double random(void)
{
	double a,b,c,random;

	a = (double)(rand() % 10000);
	b = (double)(rand() % 10000);
	c = (double)(1 + rand() % 9999);

	random = a * 10e-5 + b * 10e-9 + c * 10e-13;

	return random;
}

//插入算法應(yīng)用在鏈表b中
void insertion_sort_b(int k)
{
	BUC *n1 = b[k].next;
	BUC *n2 = b[k].next;
	BUC *n3 = b[k].next;
	BUC *n4 = &b[k];

	if(n1->next == NULL)
		return;
	n1 = n1->next;
	if(n1->next == NULL)
		return;
	while(n1->next != NULL)
	{
		if(n1->num >= n2->num)
		{
			n1 = n1->next;
			n2 = n2->next;
		}
		else 
		{
			n2->next = n1->next;
			while(n3->num <= n1->num)
			{
				n3 = n3->next;
				n4 = n4->next;
			}
			n1->next = n4->next;
			n4->next = n1;
			n1 = n2->next;
			n3 = b[k].next;
			n4 = &b[k];
		}
	}
	return;
}
//插入算法排序鏈表e
void insertion_sort_e(void)
{
	BUC *n1 = e[0].next;
	BUC *n2 = e[0].next;
	BUC *n3 = e[0].next;
	BUC *n4 = &e[0];

	if(n1->next == NULL)
		return;
	n1 = n1->next;
	if(n1->next == NULL)
		return;
	while(n1->next != NULL)
	{
		if(n1->num >= n2->num)
		{
			n1 = n1->next;
			n2 = n2->next;
		}
		else 
		{
			n2->next = n1->next;
			while(n3->num <= n1->num)
			{
				n3 = n3->next;
				n4 = n4->next;
			}
			n1->next = n4->next;
			n4->next = n1;
			n1 = n2->next;
			n3 = e[0].next;
			n4 = &e[0];
		}
	}
	return;
}

//主程序
void main()
{
//初始化

	int i,j;
	a = (double *)malloc(sizeof(double) * NUM);
	c = (BUC *)malloc(sizeof(BUC) * NUM);
	b = (BUC *)malloc(sizeof(BUC) * NUM);
	e = (BUC *)malloc(sizeof(BUC));

	srand(time(NULL));

	for(i = 0;i < NUM;i++)
	{
		p1[i] = (BUC *)malloc(sizeof(BUC));
		a[i] = random();//產(chǎn)生數(shù)組a
		c[i].num = NULL; //定義c為空
		c[i].next = NULL;
		b[i].next = &c[i];
		p1[i]->next = &c[i];
	}
//建立單一鏈表e

	p = (BUC *)malloc(sizeof(BUC));
	p->next = NULL;
	p->num = NULL;
	e->next = p;
	for(i = 0;i < NUM;i++)
	{
		p = (BUC *)malloc(sizeof(BUC));
		p->num = a[i];
		p->next = e->next;
		e->next = p;
	}

//a插入b中,構(gòu)成桶和鏈表	
	for(i = 0;i < NUM;i++)
	{
		j = (int)floor(NUM * a[i]);
		p2[i] = (BUC *)malloc(sizeof(BUC));//產(chǎn)生新的結(jié)構(gòu)，用來存儲(chǔ)a
		p2[i]->num = a[i];
		p2[i]->next = b[j].next;
		b[j].next = p2[i];
	}

//插入排序e
	struct _timeb time1;
    char *timeline1;
	_ftime( &time1 );
    timeline1 = ctime( & ( time1.time ) );
	printf( "只有一個(gè)桶的排序開始時(shí)間 %.19s.%hu \n",timeline1, time1.millitm );

	insertion_sort_e();

	struct _timeb time2;
    char *timeline2;
	_ftime( &time2 );
    timeline2 = ctime( & ( time2.time ) );
	printf( "只有一個(gè)桶的排序結(jié)束時(shí)間 %.19s.%hu \n",timeline2, time2.millitm );
	printf( "含有多個(gè)桶的排序開始時(shí)間 %.19s.%hu \n",timeline2, time2.millitm );
	
//插入排序b
	for(i = 0;i < NUM;i++)
		insertion_sort_b(i);
	
	struct _timeb time3;
    char *timeline3;
	_ftime( &time3 );
    timeline3 = ctime( & ( time3.time ) );
	printf( "含有多個(gè)桶的排序結(jié)束時(shí)間 %.19s.%hu \n",timeline3, time3.millitm );



//以下為輸出


//排序前的輸出
	printf("是否輸出排序前結(jié)果？(y/n)\n");

	if(getchar() == 'y')
	{
		printf("輸出排序前結(jié)果：\n\n");
		for(i = 0;i <NUM; i++)
			printf("%16.12f",a[i]);

		printf("\n\n");
	}	

	getchar();

//排序后的輸出
	printf("是否輸出桶排序后的全部結(jié)果？(y/n)\n");

	if(getchar() == 'y')
	{
		printf("輸出排序后結(jié)果：\n");
		for(i = 0;i < NUM;i++)//輸出b
		{
			p = b[i].next;
			while(p->num != NULL)
			{
				printf("%16.12f",p->num);
				p = p->next;
			
			}
	
		}
	}

	getchar();
//輸出只有單個(gè)鏈表的排序結(jié)果
	printf("是否輸出只有單個(gè)鏈表排序后的全部結(jié)果？(y/n)\n");
	if(getchar() == 'y')
	{
		p = e[0].next;
		while(p->num != NULL)
		{
			printf("%16.12f",p->num);
			p = p->next;
		}
	}
	getchar();
	getchar();

}