0%

【算法导论】桶排序

时间复杂度为: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

具体的程序实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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);//记得释放申请的内存空间

}
坚持原创技术分享,您的支持将鼓励我继续创作!