大数据情况下桶排序算法的运用与C++代码实现示例

概述箱排序的变种。为了区别于上述的箱排序，姑且称它为桶排序（实际上箱排序和桶排序是同义词）。

箱排序的变种。为了区别于上述的箱排序，姑且称它为桶排序（实际上箱排序和桶排序是同义词）。
桶排序的思想是把[0，1)划分为n个大小相同的子区间，每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[0，1)上的，所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同，所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序，然后依次将各非空桶中的记录连接(收集)起来即可。
注意：
这种排序思想基于以下假设：假设输入的n个关键字序列是随机分布在区间[0，1)之上。若关键字序列的取值范围不是该区间，只要其取值均非负，我们总能将所有关键字除以某一合适的数，将关键字映射到该区间上。但要保证映射后的关键字是均匀分布在[0，1)上的。
桶排序的平均时间复杂度是线性的，即O(n)。
箱排序只适用于关键字取值范围较小的情况，否则所需箱子的数目m太多导致浪费存储空间和计算时间。
例如n=10，被排序的记录关键字ki取值范围是0到99之间的整数(36，5，16，98，95，47,32，36，48)时，要用100个箱子来做一趟箱排序。（即若m=n2时，箱排序的时间O(m+n)=O(n2)）。

例子
一年的全国高考考生人数为500 万，分数使用标准分，最低100 ，最高900 ，没有小数，你把这500 万元素的数组排个序。
分析：对500W数据排序，如果基于比较的先进排序，平均比较次数为O(5000000*log5000000)≈1.112亿。但是我们发现，这些数据都有特殊的条件：  100=<score<=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
方法：创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有***人，501分有***人。
实际上，桶排序对数据的条件有特殊要求，如果上面的分数不是从100-900，而是从0-2亿，那么分配2亿个桶显然是不可能的。所以桶排序有其局限性，适合元素值集合并不大的情况。
代码：

#include<iostream.h> #include<malloc.h>  typedef struct node{  int key;  struct node * next; }KeyNode;  voID inc_sort(int keys[],int size,int bucket_size){  KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *));  for(int i=0;i<bucket_size;i++){   bucket_table[i]=(KeyNode *)malloc(sizeof(KeyNode));   bucket_table[i]->key=0; //记录当前桶中的数据量   bucket_table[i]->next=NulL;  }  for(int j=0;j<size;j++){   KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode));   node->key=keys[j];   node->next=NulL;   //映射函数计算桶号   int index=keys[j]/10;   //初始化P成为桶中数据链表的头指针   KeyNode *p=bucket_table[index];   //该桶中还没有数据   if(p->key==0){    bucket_table[index]->next=node;    (bucket_table[index]->key)++;   }else{    //链表结构的插入排序    while(p->next!=NulL&&p->next->key<=node->key)     p=p->next;     node->next=p->next;    p->next=node;    (bucket_table[index]->key)++;   }  }  //打印结果  for(int b=0;b<bucket_size;b++)   for(KeyNode *k=bucket_table[b]->next; k!=NulL; k=k->next)    cout<<k->key<<" ";  cout<<endl; }  voID main(){  int raw[]={49,38,65,97,76,13,27,49};   int size=sizeof(raw)/sizeof(int);   inc_sort(raw,size,10); } 

 
上面源代码的桶内数据排序，我们使用了基于单链表的直接插入排序算法。可以使用基于双向链表的快排算法提高效率。

总结

以上是内存溢出为你收集整理的大数据情况下桶排序算法的运用与C++代码实现示例全部内容，希望文章能够帮你解决大数据情况下桶排序算法的运用与C++代码实现示例所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。