桶排序.cpp

利用桶排序给数组a排序

////////////////////////////////////////////////////////////////
//                                                            //
//题目：桶排序                                                //
//学号：SA04225140                                            //
//作者：朱磊                                                  //
//                                                            //
////////////////////////////////////////////////////////////////


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

#define LEN sizeof(struct bucket)  //定义结构体长度
#define BUC struct bucket  //建立结构体名称
#define NUM 100000    //按要求建立十万数组

//定义结构体，包括小数和指向下个链表的指针
BUC{
	double num;
	BUC *next;
};


double *a;  //等待排序的数组
BUC *b,*e; //保存桶排序的结果
BUC *p1[NUM],*p2[NUM],*p;  //建立动态链表的指针
BUC *c; //空指针，用来标志每一行链表的结束

//产生一个含有12位小数的随机数
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;
}

//插入算法应用在链表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();//产生数组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中,构成桶和链表	
	for(i = 0;i < NUM;i++)
	{
		j = (int)floor(NUM * a[i]);
		p2[i] = (BUC *)malloc(sizeof(BUC));//产生新的结构，用来存储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( "只有一个桶的排序开始时间 %.19s.%hu \n",timeline1, time1.millitm );

	insertion_sort_e();

	struct _timeb time2;
    char *timeline2;
	_ftime( &time2 );
    timeline2 = ctime( & ( time2.time ) );
	printf( "只有一个桶的排序结束时间 %.19s.%hu \n",timeline2, time2.millitm );
	printf( "含有多个桶的排序开始时间 %.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( "含有多个桶的排序结束时间 %.19s.%hu \n",timeline3, time3.millitm );



//以下为输出


//排序前的输出
	printf("是否输出排序前结果？(y/n)\n");

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

		printf("\n\n");
	}	

	getchar();

//排序后的输出
	printf("是否输出桶排序后的全部结果？(y/n)\n");

	if(getchar() == 'y')
	{
		printf("输出排序后结果：\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();
//输出只有单个链表的排序结果
	printf("是否输出只有单个链表排序后的全部结果？(y/n)\n");
	if(getchar() == 'y')
	{
		p = e[0].next;
		while(p->num != NULL)
		{
			printf("%16.12f",p->num);
			p = p->next;
		}
	}
	getchar();
	getchar();

}