|
|
#include<stdio.h>
|
|
|
#include<stdlib.h>
|
|
|
//整体思想大致为用数组单元内存放的为结构体式的链表，每个链表称为一个桶。通里面容纳的都是键值相同的元素。
|
|
|
// 之后便是查看对应元素的键值，然后放进与之对应的桶，还需注意桶为空和不空的时的放入方式
|
|
|
//桶元素的插入就是看桶以什么方式的实现。这里桶以链表的形式表现，所以桶中元素的插入即为链表中数组的插入。
|
|
|
/*只要桶的数量够多，那么之前的放入操作只需花费O（n)的时间，而后面的对每个桶里面的元素进行排序则需要基于比较的排序算法。因此后面算法的选择也是
|
|
|
关乎桶排序速度的重要因素。
|
|
|
*/
|
|
|
//桶排序的特点是要有界限分明的桶，而不能是无限个桶，也就是说桶排序的个数应该是可以确定的，有限个的。
|
|
|
//这里链表实现桶排序的还有要注意的点，就是数组的首地址其实链表的头节点，有这里的值确定该桶的元素个数，并由这里出发寻找其他元素。
|
|
|
typedef struct node *Snode;
|
|
|
typedef struct node{
|
|
|
int key;
|
|
|
Snode next;
|
|
|
}BBc;
|
|
|
|
|
|
void sort(int keys[],int keys_size,int bucket_size)
|
|
|
{
|
|
|
Snode *bucket_table = (Snode *)malloc(bucket_size*sizeof(Snode));//为结构体数组分配空间。
|
|
|
for(int i=0;i<bucket_size;i++)//对每个数组单元赋予内存空间时，初始化每个结构体数组单元。
|
|
|
{
|
|
|
bucket_table[i] = (Snode)malloc(sizeof(Snode));//这一步是必要的，因为之前只是给数组分配了一连串的存储空间，但是每个单元的存储地址都是
|
|
|
//不确定，也不确定该方式是否会自动地分配内存空间给每个数组单元。
|
|
|
//那么这样准确的给数组单眼分配的空间是占用之前的分配给数组的空间，还是重新分拨其他的空间给数组单元。
|
|
|
//其实应该是分配之前给整个数组单元分配的一段存储空间。
|
|
|
bucket_table[i]->key = 0;
|
|
|
bucket_table[i]->next = NULL;
|
|
|
}//其实创建数组这部分应该放在主函数那里，否则某些功能只能在这个函数中使用。
|
|
|
for(int j=0;j<keys_size;j++)
|
|
|
{
|
|
|
Snode node_branch = (Snode)malloc(sizeof(Snode));//定义一个节点，满足条件时链入以链表为表现形式的桶。
|
|
|
node_branch->key = keys[j];
|
|
|
node_branch->next = NULL;
|
|
|
int index = keys[j]/10;
|
|
|
Snode p = bucket_table[index];//p用来充当指向循环的变量。
|
|
|
//桶为空和非空时的两种插入形式
|
|
|
if(p->key == 0){
|
|
|
bucket_table[index]->next = node_branch;
|
|
|
(bucket_table[index]->key)++;
|
|
|
}
|
|
|
//链表的插入形式，按照大小从后到大。
|
|
|
else{
|
|
|
while(p->next!=NULL && p->next->key <= node_branch->key){
|
|
|
p=p->next;
|
|
|
}
|
|
|
node_branch->next = p->next;
|
|
|
p->next = node_branch;
|
|
|
(bucket_table[j]->key)++;
|
|
|
}
|
|
|
}
|
|
|
//以此输出每个桶中的所有元素。
|
|
|
for(int i=0;i<bucket_size;i++){
|
|
|
for(Snode k = bucket_table[i]->next;k!=NULL;k = k->next){
|
|
|
printf(" %d ",k->key);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
int main()
|
|
|
{
|
|
|
int keys[] = {49,26,53,47,89,31,72,11,33};
|
|
|
int keys_size = sizeof(keys)/sizeof(int);
|
|
|
int bucket_size = keys_size+2;
|
|
|
sort(keys,keys_size,bucket_size);
|
|
|
}
|
