算法总结系列之六: 桶排序(Bucket Sort)

桶排序是另外一种以O(n)或者接近O(n)的复杂度排序的算法. 它假设输入的待排序元素是等可能的落在等间隔的值区间内.一个长度为N的数组使用桶排序, 需要长度为N的辅助数组. 等间隔的区间称为桶, 每个桶内落在该区间的元素. 桶排序是基数排序的一种归纳结果

算法的主要思想: 待排序数组A[1...n]内的元素是随机分布在[0,1)区间内的的浮点数.辅助排序数组B[0....n-1]的每一个元素都连接一个链表.将A内每个元素乘以N(数组规模)取底,并以此为索引插入(插入排序)数组B的对应位置的连表中. 最后将所有的链表依次连接起来就是排序结果.

这个过程可以简单的分步如下:

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。

note: 待排序元素越均匀, 桶排序的效率越高. 均匀意味着每个桶在中间过程中容纳的元素个数都差不多,不会出现特别少或者特别多的情况, 这样在排序子程序进行桶内排序的过程中会达到最优效率.

note: 将元素通过恰当的映射关系将元素尽量等数量的分到各个桶(值区间)里面, 这个映射关系就是桶排序算法的关键.桶的标记(数组索引Index)的大小也要和值区间有对应关系

下面是一段来自互联网的算法引用, 桶排序算法的C++实现, 非作者原创!

   1: #

   2: #include <iostream>

   3: #

   4: #include <ctime>

   5: #

   6: #include <cmath>

   7: #

   8: using namespace std;

   9: #

  10: void main()

  11: #

  12:  

  13: #

  14: {

  15: #

  16:  

  17: #

  18: long choice;

  19: #

  20: long start,end;

  21: #

  22: MUNE: cout<<"桶排序：1.正常情况 2.最坏情况 3.退出"<<endl;

  23: #

  24: cin>>choice;

  25: #

  26:  

  27: #

  28:  

  29: #

  30: struct node //定义链表

  31: #

  32: {

  33: #

  34: double item;

  35: #

  36: node *next;

  37: #

  38: node(double x,node *n)

  39: #

  40: {

  41: #

  42: item=x;

  43: #

  44: next=n;

  45: #

  46: }

  47: #

  48: };

  49: #

  50: typedef node *link; //构造链表

  51: #

  52: const long ARRAYNUM=10000; //定义要求要求排序数组大小

  53: #

  54: const long BUCKETNUM=10000; //定义桶的数量

  55: #

  56: double *SortArray;

  57: #

  58: SortArray=new double[ARRAYNUM];//定义排序数组

  59: #

  60: link *Bucket;

  61: #

  62: Bucket=new link[BUCKETNUM]; //定义桶

  63: #

  64: link t=new node(0,NULL);

  65: #

  66: link newlink;

  67: #

  68: link templink=new node(0,NULL);

  69: #

  70: for (long x=0;x<BUCKETNUM;x++) //初始化桶

  71: #

  72: {

  73: #

  74: Bucket[x]=new node(0,NULL);

  75: #

  76: }

  77: #

  78:  

  79: #

  80:  

  81: #

  82: srand((unsigned) time(NULL)); //产生随机数组

  83: #

  84: for (long i=0;i<ARRAYNUM;i++)

  85: #

  86: {

  87: #

  88: SortArray[i]=(double)rand()/RAND_MAX;

  89: #

  90:  

  91: #

  92: }

  93: #

  94:  

  95: #

  96: start=clock(); //设置时钟起点

  97: #

  98: for(long j=0;j<ARRAYNUM;j++)

  99: #

 100: {

 101: #

 102: newlink=new node(SortArray[j],NULL);

 103: #

 104: switch(choice) //输入选择

 105: #

 106: {

 107: #

 108: case 1: t=Bucket[(long)(BUCKETNUM*SortArray[j])];break;

 109: #

 110: case 2: t=Bucket[0];break; //最坏情况，数据都在一个桶里

 111: #

 112: case 3: goto EXIT;break;

 113: #

 114: }

 115: #

 116: if(t->item==0) //如果桶为空，则把数据直接放入桶内

 117: #

 118: {

 119: #

 120: t->item=SortArray[j];

 121: #

 122: }

 123: #

 124: else

 125: #

 126:  

 127: #

 128: {

 129: #

 130: if(t->item>SortArray[j]) //桶不为空，待插入数据比原桶内第一个数据小情况

 131: #

 132: //即数据要插在第一个数据前面

 133: #

 134: {

 135: #

 136: templink=t; //前向指针，随着t的编译，templing->next=t

 137: #

 138: Bucket[(long)(BUCKETNUM*(newlink->item))]=newlink;

 139: #

 140: newlink->next=templink;

 141: #

 142: templink=NULL;

 143: #

 144: }

 145: #

 146: else

 147: #

 148: {

 149: #

 150: while(t!=NULL) //桶不为空，待插入数据比原桶内数据小情况

 151: #

 152: {

 153: #

 154: if(t->item<=SortArray[j]) //桶不为空，待插入数据比原桶内第二个及以后数据大情况，

 155: #

 156: {

 157: #

 158: templink=t;

 159: #

 160: t=t->next; //待插入数比桶内数大，链表后向遍历

 161: #

 162:  

 163: #

 164: if(t==NULL) //链表编译到原桶内最后一个数

 165: #

 166: {

 167: #

 168: templink->next=newlink;//将待插数据接在原链表最后

 169: #

 170: }

 171: #

 172: }

 173: #

 174: else //链表比当前数据小,插入数据

 175: #

 176: {

 177: #

 178:  

 179: #

 180: newlink->next=t;

 181: #

 182: templink->next=newlink;

 183: #

 184: t=NULL;

 185: #

 186: }

 187: #

 188:  

 189: #

 190:  

 191: #

 192: }

 193: #

 194: }

 195: #

 196: }

 197: #

 198:  

 199: #

 200:  

 201: #

 202: }

 203: #

 204: end=clock(); //设置时钟终点

 205: #

 206: cout<<"所用时间为："<<end-start<<endl;

 207: #

 208:  

 209: #

 210: goto MUNE;

 211: #

 212:  

 213: #

 214: EXIT:;

 215: #

 216: }