桶排序
时间复杂度为：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
