基本介紹
- 中文名：桶排序
- 要求：數據的長度必須完全一樣
- 公式：Data=rand()/10000+10000
- 數據結構設計：鍊表可以採用很多種方式實現
- 性質：平均情況下桶排序以線性時間運行
- 原理：桶排序利用函式的映射關係
- 領域：計算機算法
定義,算法,代價,源碼,C++,JAVA,PAS,套用,海量數據,典型,
定義
假定：輸入是由一個隨機過程產生的[0, 1)區間上均勻分布的實數。將區間[0, 1)劃分為n個大小相等的子區間（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…將n個輸入元素分配到這些桶中，對桶中元素進行排序，然後依次連線桶輸入0 ≤A[1..n] <1輔助數組B[0..n-1]是一指針數組，指向桶（鍊表）。
算法
桶排序算法要求，數據的長度必須完全一樣，程式過程要產生長度相同的數據，使用下面的方法：Data=rand()/10000+10000上面提到的，每次下一次的掃描順序是按照上次掃描的結果來的，所以設計上提供相同的兩個桶數據結構。前一個保存每一次掃描的結果供下次調用，另外一個臨時拷貝前一次掃描的結果提供給前一個調用。
數據結構設計：鍊表可以採用很多種方式實現，通常的方法是動態申請記憶體建立結點，但是針對這個算法，桶裡面的鍊表結果每次掃描後都不同，就有很多鍊表的分離和重建。如果使用動態分配記憶體，則由於指針的使用，安全性低。所以，筆者設計時使用了數組來模擬鍊表（當然犧牲了部分的空間，但是操作卻是簡單了很多，穩定性也大大提高了）。共十個桶，所以建立一個二維數組，行向量的下標0—9代表了10個桶，每個行形成的一維數組則是桶的空間。
平均情況下桶排序以線性時間運行。像基數排序一樣，桶排序也對輸入作了某種假設， 因而運行得很快。具 體來說，基數排序假設輸入是由一個小範圍內的整數構成，而桶排序則 假設輸入由一個隨機過程產生，該過程將元素一致地分布在區間[0，1)上。 桶排序的思想就是把區間[0，1)劃分成n個相同大小的子區間，或稱桶，然後將n個輸入數分布到各個桶中去。因為輸入數均勻分布在[0，1)上，所以一般不會有很多數落在一個桶中的情況。為得到結果，先對各個桶中的數進行排序，然後按次序把各桶中的元素列出來即可。
桶排序的算法如下(偽代碼表示)，其中floor(x)是地板函式，表示不超過x的最大整數。
procedure Bin_Sort(var A:List);begin
n:=length(A);
for i:=1 to n do
將A[i]插到表B[floor(n*A[i])]中;
for i:=0 to n-1 do
用插入排序對表B[i]進行排序;
將表B[0],B[1],...,B[n-1]按順序合併;
end;
右圖演示了桶排序作用於有10個數的輸入數組上的操作過程。(a)輸入數組A[1..10]。(b)在該算法的第5行後的有序表(桶)數組B[0..9]。桶i中存放了區間[i/10，(i+1)/10]上的值。排序輸出由表B[O]、B[1]、...、B[9]的按序並置構成。
要說明這個算法能正確地工作，看兩個元素A[i]和A[j]。如果它們落在同一個桶中，則它們在輸出序列中有著正確的相對次序，因為它們所在的桶是採用插入排序的。現假設它們落到不同的桶中，設分別為B[i']和B[j']。不失一般性，假設i' i'=floor(n*A[i])≥floor(n*A[j])=j' 得矛盾 (因為i' 來分析算法的運行時間。除第5行外，所有各行在最壞情況的時間都是O(n)。第5行中檢查所有桶的時間是O(n)。分析中唯一有趣的部分就在於第5行中插人排序所花的時間。
為分析插人排序的時間代價，設ni為表示桶B[i]中元素個數的隨機變數。因為插入排序以二次時間運行，故為排序桶B[i]中元素的期望時間為E[O(ni2)]=O(E[ni2])，對各個桶中的所有元素排序的總期望時間為：O(n)。(1) 為了求這個和式，要確定每個隨機變數ni的分布。我們共有n個元素，n個桶。某個元素落到桶B[i]的機率為l/n，因為每個桶對應於區間[0，1)的l/n。這種情況與投球的例子很類似：有n個球 (元素)和n個盒子 (桶)，每次投球都是獨立的，且以機率p=1/n落到任一桶中。這樣，ni=k的機率就服從二項分布B(k;n,p)，其期望值為E[ni]=np=1，方差V[ni]=np(1-p)=1-1/n。對任意隨機變數X，有右圖所示表達式。
(2)將這個界用到(1)式上，得出桶排序中的插人排序的期望運行時間為O(n)。因而，整個桶排序的期望運行時間就是線性的。
代價
桶排序利用函式的映射關係，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當於快排中劃分，已經把大量數據分割成了基本有序的數據塊(桶)。然後只需要對桶中的少量數據做先進的比較排序即可。
(1) 循環計算每個關鍵字的桶映射函式，這個時間複雜度是O(N)。
很顯然，第(2)部分是桶排序性能好壞的決定因素。儘量減少桶內數據的數量是提高效率的唯一辦法(因為基於比較排序的最好平均時間複雜度只能達到O(N*logN)了)。因此，我們需要儘量做到下面兩點：
(1) 映射函式f(k)能夠將N個數據平均的分配到M個桶中，這樣每個桶就有[N/M]個數據量。
(2) 儘量的增大桶的數量。極限情況下每個桶只能得到一個數據，這樣就完全避開了桶內數據的“比較”排序操作。 當然，做到這一點很不容易，數據量巨大的情況下，f(k)函式會使得桶集合的數量巨大，空間浪費嚴重。這就是一個時間代價和空間代價的權衡問題了。
對於N個待排數據，M個桶，平均每個桶[N/M]個數據的桶排序平均時間複雜度為：
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
當N=M時，即極限情況下每個桶只有一個數據時。桶排序的最好效率能夠達到O(N)。
總結：桶排序的平均時間複雜度為線性的O(N+C)，其中C=N*(logN-logM)。如果相對於同樣的N，桶數量M越大，其效率越高，最好的時間複雜度達到O(N)。當然桶排序的空間複雜度為O(N+M)，如果輸入數據非常龐大，而桶的數量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩定的。
源碼
io.open();//打開控制台
/**-------------------------------------------------------* 桶排序**------------------------------------------------------*/
/*
桶排序假設輸入元素均勻而獨立分布在區間[0,1) 即 0 <= x and x < 1;將區間劃分成n個相同大小的子區間(桶)，然後將n個輸入按大小分布到各個桶中去，對每個桶內部進行排序。最後將所有桶的排序結果合併起來.
*/
//插入排序算法
insert_sort = function( array ){
for( right=2;#array ) {
var top = array[right];
//Insert array[right] into the sorted seqquence array[1....right-1]
var left = right -1;
while( left and array[left]>top){
array[left+1] = array[left];
left--;
}
array[left+1] = top;
}
return array;
}
//桶排序算法
bucket_sort = function( array ){
var n = #array;
var bucket ={}
for(i=0;n;1){
bucket[i] = {} //創建一個桶
}
var bucket_index
for(i=1;n;1){
bucket_index = math.floor(n * array[i]);
table.push( bucket [ bucket_index ],array[i] );//放到桶里去
}
for(i=1;n;1){
insert_sort( bucket[i] ); //對每個桶進行插入排序
}
return table.concat( table.unpack(bucket) )
}
io.print("----------------")
io.print("桶排序")
io.print("----------------")
array={};
//桶排序假設輸入是由一個隨機過程產生的小數.
math.randomize()
for(i=1;20;1){
table.push( array,math.random() )
}
//排序
array = bucket_sort( array )
//輸出結果
for(i=1;#array;1){
io.print( array[i] )
}
execute("pause") //按任意鍵繼續
io.close();//關閉控制台
C++
#include<iostream>usingnamespace std;int a[]={1,255,8,6,25,47,14,35,58,75,96,158,657};const int len=sizeof(a)/sizeof(int);int b[10][len+1]={0};//將b全部置0void bucketSort(int a[]);//桶排序函式void distribute Elments(int a[],int b[10][len+1],int digits);void collectElments(int a[],int b[10][len+1]);int numOfDigits(int a[]);void zeroBucket(int b[10][len+1]);//將b數組中的全部元素置0int main(){cout<<"原始數組：";for(int i=0;i<len;i++)cout<<a[i]<<",";cout<<endl;bucketSort(a);cout<<"排序後數組：";for(int i=0;i<len;i++)cout<<a[i]<<",";cout<<endl;return 0;}void bucketSort(int a[]){int digits=numOfDigits(a);for(int i=1;i<=digits;i++){distributeElments(a,b,i);collectElments(a,b);if(i!=digits)zeroBucket(b);}}int numOfDigits(int a[]){int largest=0;for(int i=0;i<len;i++)//獲取最大值if(a[i]>largest)largest=a[i];int digits=0;//digits為最大值的位數while(largest){digits++;largest/=10;}return digits;}void distributeElments(int a[],int b[10][len+1],int digits){int divisor=10;//除數for(int i=1;i<digits;i++)divisor*=10;for(int j=0;j<len;j++){int numOfDigist=(a[j]%divisor-a[j]%(divisor/10))/(divisor/10);//numOfDigits為相應的(divisor/10)位的值,如當divisor=10時,求的是個位數int num=++b[numOfDigist][0];//用b中第一列的元素來儲存每行中元素的個數b[numOfDigist][num]=a[j];}}void collectElments(int a[],int b[10][len+1]){int k=0;for(int i=0;i<10;i++)for(int j=1;j<=b[i][0];j++)a[k++]=b[i][j];}void zeroBucket(int b[][len+1]){for(int i=0;i<10;i++)for(int j=0;j<len+1;j++)b[i][j]=0;}JAVA
public static void basket(int data[])//data為待排序數組{int n=data.length;int bask[][]=new int[10][n];int index[]=new int[10];int max=Integer.MIN_VALUE;for(int i=0;i<n;i++){max=max>(Integer.toString(data[i]).length())?max:(Integer.toString(data[i]).length());}String str;for(int i=max-1;i>=0;i--){for(int j=0;j<n;j++){str="";if(Integer.toString(data[j]).length()<max){for(int k=0;k<max-Integer.toString(data[j]).length();k++)str+="0";}str+=Integer.toString(data[j]);bask[str.charAt(i)-'0'][index[str.charAt(i)-'0']++]=data[j];}int pos=0;for(int j=0;j<10;j++){for(int k=0;k<index[j];k++){data[pos++]=bask[j][k];}}for(intx=0;x<10;x++)index[x]=0;}}PAS
program barrel_sort;vara:array[0..100] of integer;i,k,n:integer;beginfor i:=0 to 100 do a[i]:=0;{初始化}readln(n);for i:=1 to n dobeginread(k);a[k]:=a[k]+1;{將等於k的值全部裝入第k桶中}end;for i:=0 to 100 dowhile a[i]>0 dobeginwrite(i:6);a[i]:=a[i]-1;end;{輸出排序結構}end.//這段應該是鴿巢排序，桶排序應該有段桶內比較排序的函式套用
海量數據
一年的全國高考考生人數為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億個桶顯然是不可能的。所以桶排序有其局限性，適合元素值集合併不大的情況。
典型
在一個檔案中有10G個整數，亂序排列，要求找出中位數。記憶體限制為2G。只寫出思路即可（記憶體限制為2G意思是可以使用2G空間來運行程式，而不考慮本機上其他軟體記憶體占用情況。） 關於中位數：數據排序後，位置在最中間的數值。即將數據分成兩部分，一部分大於該數值，一部分小於該數值。中位數的位置：當樣本數為奇數時，中位數=(N+1)/2 ; 當樣本數為偶數時，中位數為N/2與1+N/2的均值（那么10G個數的中位數，就第5G大的數與第5G+1大的數的均值了）。
分析：既然要找中位數，很簡單就是排序的想法。那么基於位元組的桶排序是一個可行的方法。
思想：將整型的每1byte作為一個關鍵字，也就是說一個整形可以拆成4個keys，而且最高位的keys越大，整數越大。如果高位keys相同，則比較次高位的keys。整個比較過程類似於字元串的字典序。
第一步:把10G整數每2G讀入一次記憶體，然後一次遍歷這536,870,912即（1024*1024*1024）*2 /4個數據。每個數據用位運算">>"取出最高8位(31-24)。這8bits(0-255)最多表示256個桶，那么可以根據8bit的值來確定丟入第幾個桶。最後把每個桶寫入一個磁碟檔案中，同時在記憶體中統計每個桶內數據的數量NUM[256]。
代價：(1) 10G數據依次讀入記憶體的IO代價(這個是無法避免的，CPU不能直接在磁碟上運算)。(2)在記憶體中遍歷536,870,912個數據，這是一個O(n)的線性時間複雜度。(3)把256個桶寫回到256個磁碟檔案空間中，這個代價是額外的，也就是多付出一倍的10G數據轉移的時間。
第二步：根據記憶體中256個桶內的數量NUM[256]，計算中位數在第幾個桶中。很顯然，2,684,354,560個數中位數是第1,342,177,280個。假設前127個桶的數據量相加，發現少於1,342,177,280，把第128個桶數據量加上，大於1,342,177,280。說明，中位數必在磁碟的第128個桶中。而且在這個桶的第1,342,177,280-N(0-127)個數位上。N(0-127)表示前127個桶的數據量之和。然後把第128個檔案中的整數讀入記憶體。(若數據大致是均勻分布的，每個檔案的大小估計在10G/256=40M左右，當然也不一定，但是超過2G的可能性很小)。注意，變態的情況下，這個需要讀入的第128號檔案仍然大於2G，那么整個讀入仍然可以按照第一步分批來進行讀取。
代價：(1)循環計算255個桶中的數據量累加，需要O(M)的代價，其中m<255。(2)讀入一個大概80M左右檔案大小的IO代價。
第三步：繼續以記憶體中的某個桶內整數的次高8bit（他們的最高8bit是一樣的）進行桶排序(23-16)。過程和第一步相同，也是256個桶。
第四步：一直下去，直到最低位元組(7-0bit)的桶排序結束。我相信這個時候完全可以在記憶體中使用一次快排就可以了。
