源地址:http://www.cnblogs.com/sun/archive/2008/07/07/1237331.html
桶排序是另外一种以O(n)或者接近O(n)的复杂度排序的算法. 它假设输入的待排序元素是等可能的落在等间隔的值区间内.一个长度为N的数组使用桶排序, 需要长度为N的辅助数组. 等间隔的区间称为桶, 每个桶内落在该区间的元素. 桶排序是基数排序的一种归纳结果
算法的主要思想: 待排序数组A[1...n]内的元素是随机分布在[0,1)区间内的的浮点数.辅助排序数组B[0....n-1]的每一个元素都连接一个链表.将A内每个元素乘以N(数组规模)取底,并以此为索引插入(插入排序)数组B的对应位置的连表中. 最后将所有的链表依次连接起来就是排序结果.
这个过程可以简单的分步如下:
- 设置一个定量的数组当作空桶子。
- 寻访序列,并且把项目一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项目再放回原来的序列中。
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: }