バケツソート(Bucket Sort)

ソースアドレス: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の対応する位置の連表に挿入する. 最後にすべてのチェーンテーブルを順次接続することがソート結果である.
このプロセスは、次のように簡単にステップできます.
定量的配列を空きバケツとして設定します.シーケンスを探して、プロジェクトを1つずつ対応するバケツに置きます.空でないバケツごとに並べ替えます.空ではないバケツからアイテムを元のシーケンスに戻します. 
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: }