❶ 桶排序的演算法
桶排序演算法要求，數據的長度必須完全一樣，程序過程要產生長度相同的數據，使用下面的方法：Data=rand()/10000+10000上面提到的，每次下一次的掃描順序是按照上次掃描的結果來的，所以設計上提供相同的兩個桶數據結構。前一個保存每一次掃描的結果供下次調用，另外一個臨時拷貝前一次掃描的結果提供給前一個調用。
數據結構設計：鏈表可以採用很多種方式實現，通常的方法是動態申請內存建立結點，但是針對這個演算法，桶裡面的鏈表結果每次掃描後都不同，就有很多鏈表的分離和重建。如果使用動態分配內存，則由於指針的使用，安全性低。所以，筆者設計時使用了數組來模擬鏈表（當然犧牲了部分的空間，但是操作卻是簡單了很多，穩定性也大大提高了）。共十個桶，所以建立一個二維數組，行向量的下標0—9代表了10個桶，每個行形成的一維數組則是桶的空間。
平均情況下桶排序以線性時間運行。像基數排序一樣，桶排序也對輸入作了某種假設， 因而運行得很快。具 體來說，基數排序假設輸入是由一個小范圍內的整數構成，而桶排序則 假設輸入由一個隨機過程產生，該過程將元素一致地分布在區間[0，1)上。 桶排序的思想就是把區間[0，1)劃分成n個相同大小的子區間，或稱桶，然後將n個輸入數分布到各個桶中去。因為輸入數均勻分布在[0，1)上，所以一般不會有很多數落在一個桶中的情況。為得到結果，先對各個桶中的數進行排序，然後按次序把各桶中的元素列出來即可。
在桶排序演算法的代碼中，假設輸入是含n個元素的數組A，且每個元素滿足0≤ A[i]<1。另外還需要一個輔助數組B[O..n-1]來存放鏈表實現的桶，並假設可以用某種機制來維護這些表。
桶排序的演算法如下(偽代碼表示)，其中floor(x)是地板函數，表示不超過x的最大整數。
procere 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)。因而，整個桶排序的期望運行時間就是線性的。
❷ 令牌桶演算法的簡介
在網路中傳輸數據時，為了防止網路擁塞，需限制流出網路的流量，使流量以比較均勻的速度向外發送。令牌桶演算法就實現了這個功能，可控制發送到網路上數據的數目，並允許突發數據的發送。
令牌桶演算法是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種演算法。典型情況下，令牌桶演算法用來控制發送到網路上的數據的數目，並允許突發數據的發送。
大小固定的令牌桶可自行以恆定的速率源源不斷地產生令牌。如果令牌不被消耗，或者被消耗的速度小於產生的速度，令牌就會不斷地增多，直到把桶填滿。後面再產生的令牌就會從桶中溢出。最後桶中可以保存的最大令牌數永遠不會超過桶的大小。
傳送到令牌桶的數據包需要消耗令牌。不同大小的數據包，消耗的令牌數量不一樣。
令牌桶這種控制機制基於令牌桶中是否存在令牌來指示什麼時候可以發送流量。令牌桶中的每一個令牌都代表一個位元組。如果令牌桶中存在令牌，則允許發送流量；而如果令牌桶中不存在令牌，則不允許發送流量。因此，如果突發門限被合理地配置並且令牌桶中有足夠的令牌，那麼流量就可以以峰值速率發送。
令牌桶演算法的基本過程如下：
假如用戶配置的平均發送速率為r，則每隔1/r秒一個令牌被加入到桶中；
假設桶最多可以存發b個令牌。如果令牌到達時令牌桶已經滿了，那麼這個令牌會被丟棄；
當一個n個位元組的數據包到達時，就從令牌桶中刪除n個令牌，並且數據包被發送到網路；
如果令牌桶中少於n個令牌，那麼不會刪除令牌，並且認為這個數據包在流量限制之外；
演算法允許最長b個位元組的突發，但從長期運行結果看，數據包的速率被限製成常量r。對於在流量限制外的數據包可以以不同的方式處理：
它們可以被丟棄；
它們可以排放在隊列中以便當令牌桶中累積了足夠多的令牌時再傳輸；
它們可以繼續發送，但需要做特殊標記，網路過載的時候將這些特殊標記的包丟棄。
注意：令牌桶演算法不能與另外一種常見演算法「漏桶演算法（Leaky Bucket）」相混淆。這兩種演算法的主要區別在於「漏桶演算法」能夠強行限制數據的傳輸速率，而「令牌桶演算法」在能夠限制數據的平均傳輸速率外，還允許某種程度的突發傳輸。在「令牌桶演算法」中，只要令牌桶中存在令牌，那麼就允許突發地傳輸數據直到達到用戶配置的門限，因此它適合於具有突發特性的流量。
❸ 桶排序與哈希桶排序
桶排序 (箱排序)的原理是將待排序序列分到有限數量的桶裡面，然後對每個桶再分別排序（可以使用其它的排序演算法或者是遞歸使用桶排序演算法），最後將各個桶中的數據有序的合並起來成為一個整體有序的序列。
排序過程：
1.假設待排序的一組數統一的分布在一個范圍中，並將這一范圍劃分成幾個子范圍，也就是桶
2.將待排序的一組數，分檔規入這些子桶，並將桶中的數據進行排序
3.將各個桶中的數據有序的合並起來
設有數組 array = [29, 25, 3, 49, 9, 37, 21, 43]，那麼數組中最大數為 49，先設置 5 個桶，那麼每個桶可存放數的范圍為：09、1019、2029、3039、40~49，然後分別將這些數放人自己所屬的桶，如下圖：
1.時間復雜度：O(m+n)
2.空間復雜度：O(m+n)
適用於序列比較均勻的情況，否則會很耗空間。
或者特殊的場景，例如需要對一個公司的員工的年齡進行排序，年齡的范圍為1-120，此時就可以開辟120個桶進行統計排序。
另，桶排序的瓶頸主要是桶數量的選擇。
另此演算法為穩定的排序演算法。
排序演算法主要是用分治法，用哈希函數對序列進行劃分，最後使用其它的排序演算法或者遞歸使用哈希排序進行排序從而得到一個整體有序的序列。下面先介紹幾個自定義的概念：
1.哈希桶排序：因為本演算法是使用了哈希函數把序列劃分到對應的桶裡面，所以本排序演算法取名為哈希桶排序。
2.哈希桶因子（hashFactor）：hashFactor = （max - min） / length
計算公式如上式，當結果小於等於0的時候再做特殊處理，據此因子進行桶的劃分。
設有數組 array = [10011, 10001, 16, 14, 12, 10000, 10, 10002, 10003, 1]，那麼數組中最大值max = 10011，最小值min = 1，哈希桶因子hashFactor = （10011 - 1） / 10 = 1001。對數組進行劃分，10011 / 1001 = 10，所以10011放在keywei10的桶裡面；10001 / 1001 = 9， 所以10001放在key為9的桶裡面，以此類推，最後得到的桶的情況為：{0=[1, 10, 12, 14, 16], 9=[10000, 10001, 10002, 10003], 10=[10011]}。再分別對每個桶進行排序即可。
1.時間復雜度：O(m+n)
2.空間復雜度：O(m+n)
此演算法與桶排序對比，主要是通過哈希建桶的方式減少了空間的消耗，對序列進行了一個歸約，時間上跟桶排序相當。
使用與序列的最小最大值相差比較大同時又出現在某一個取值區間的集聚的情況。
另此演算法為穩定的排序演算法。
