【算法导论】桶排序

时间复杂度为：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);//记得释放申请的内存空间
	
}