【算法导论】桶排序

桶排序

时间复杂度为：O(n)

基本思想：将要排列的序列分成n组，每组分别进行排序，然后在合并到一起，这里面有分而治之的思想。实例说明：大家学c语言肯定学过switch-case结构，最常见的题型就是对成绩进行分类，但是这里我们是对其进行排名。假设有十个学生的成绩如下：78,17,39,26,72,94,21,12,23,68。我们可以把成绩先进行分段（称为桶），每十分分为一段，共分为10段。然后在每段内进行排序，每一段的排序可以采用插入排序，最后再进行合并即可。各段的内容为：

 桶编号：桶中元素

           0： 

           1：12 、17

           2：21 、23 、26

           3：39

           4：

           5：

           6：68

           7：72 、 78

           8：

           9：94

具体的程序实现如下：

#include<stdio.h>
#include<malloc.h>  

void inc_sort(int arrayA[],int size,int bucket_size);

typedef struct node
{
    int key;
    struct node * next;
}KeyNode;  

void main()
{
    int raw[]={78,17,39,26,72,94,21,12,23,68};
    int size=sizeof(raw)/sizeof(int);
    inc_sort(raw,size,10);
}

/****************************************************\
函数功能：对输入数组进行桶排序
输入：数组及其大小、桶的大小
输出：无
\****************************************************/
void inc_sort(int arrayA[],int size,int bucket_size)
{
    KeyNode **bucket=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *)); //指向指针的指针，bucket相当于二维数组
    for(int i=0;i<bucket_size;i++)
	{
        bucket[i]=(KeyNode *)malloc(sizeof(KeyNode));//动态开辟空间
        bucket[i]->key=0; //初始化桶中的数据
        bucket[i]->next=NULL;
    }  

    for(int j=0;j<size;j++)
	{
        KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode));//创立节点
        node->key=arrayA[j];
        node->next=NULL;  

        int index=arrayA[j]/10; //映射函数计算桶号和散列函数相似    

        KeyNode *p=bucket[index];//初始化p成为桶中数据链表的头指针  

        if(p->key==0)//当桶中还没有数据
            bucket[index]->next=node;
   		else
		{
            //链表结构的插入排序
            while((p->next!=NULL)&&(p->next->key<=node->key))//插入的数据大于当前数据时，从头结点开始
                p=p->next;                                   //直到找到大于它的节点为止
            node->next=p->next;
            p->next=node;
        }
		(bucket[index]->key)++;
    }  

    for(int i=0;i<bucket_size;i++)
	{
        for(KeyNode *k=bucket[i]->next; k!=NULL; k=k->next)
			printf("%d ",k->key);
	//	printf("\n");
	}
    printf("\n"); 

	free(bucket);//记得释放申请的内存空间

}  

注意：我是在vs2008上运行的，与vc 6.0有点区别，主要是循环体中的循环变量的作用域，出错体现在循环变量的重复定义上。例如：在vs2008或vs2010上，程序为：

#include<stdio.h>
void main()
{
int i=0;
for(int i=0;i<5;i++)
printf("%d ",i);
}

则在VC 6.0上需改为：

#include<stdio.h>
void main()
{
int i=0;
for(i=0;i<5;i++)
printf("%d ",i);
}　

原文：http://blog.csdn.net/tengweitw/article/details/9713333

作者：nineheadedbird