sort_bucket.cpp

自己编写的排序算法的代码

#include <fstream.h>
#include "data.h"

//确定数据应该插入哪个桶
int Bucket_number(int a[],int k)
{
	int i,d,s,j=1;
	float n;
	d=digit();
	for(i=0;i<d;i++)
		j=j*10;
	n=(float)Bucket/(float)j;
	s=int(a[k]*n);
	return s;
}

//桶内为单链表结构，顺序插入
void Bucket_insert(int*a,node*b,int k)
{
	node *p1,*p2,*head;
	head=(node*) a[k];
    if(head->next==NULL)
	{
		head->next=b;
		b->next=NULL;
	}
	else
	{
		p1=head;
		p2=head->next;
		while(p2->next&&p2->data<b->data)
		{
			p1=p2;
			p2=p2->next;
		}
		if(p2->data>=b->data)
		{
			b->next=p1->next;
			p1->next=b;
		}
		else
		{
			p2->next=b;
			b->next=NULL;
		}
	}
}


//桶排序
void Bucket_sort(int a[])
{
	node *temp,*p;
	int i,j,k,*ha;
	//申请桶的空间并初始化
	ha=new int[Bucket];
	if(!ha)
	{
		cout<<"内存空间申请失败"<<endl;
		return;
	}
    for(j=0;j<Bucket;j++)
	{
		temp=new node;
		if(!temp)
		{
		cout<<"内存空间申请失败"<<endl;
		return;
		}
		temp->next=NULL;
		ha[j]=(int) temp;
	}
	//把数据插入桶中
	for(i=0;i<number;i++)
	{
		temp=new node;
		if(!temp)
		{
		cout<<"内存空间申请失败"<<endl;
		return;
		}
		temp->data=a[i];
		k=Bucket_number(a,i);
		Bucket_insert(ha,temp,k);
	}
	//把排好序的数据拷回原数组，并且把不用的空间还给内存
	i=0;
	for(j=0;j<Bucket;j++)
	{
		temp=(node*) ha[j];
		temp=temp->next;
		while(temp)
		{
			p=temp;
			a[i]=temp->data;
			temp=temp->next;
			i++;
			delete p;
		}
        temp=(node*) ha[j];
		delete temp;
	}
	delete ha;
}