Pages

Monday, May 16, 2011

算法总结系列之六: 桶排序(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: }
作者:Jeffrey Sun
出处:http://sun.cnblogs.com/
本文以“现状”提供且没有任何担保,同时也没有授予任何权利。本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

No comments:

Post a Comment