桶排序是什麼

桶排序是一個排序演算法，工作的原理是將數組分到有限數量的桶子裡；桶排序也是鴿巢排序的一種歸納結果，當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間，但桶排序並不是比較排序，他不受到「 O(n log n)」下限的影響。

桶排序

#如果已知N 個關鍵字的取值範圍是在0 到M-1 之間，而M 比N 小的多，則桶排序演算法將關鍵字的每個取值建立一個"桶"，即建立M 個桶，在掃描N 個關鍵字時，將每個關鍵字放入對應的桶中，然後按桶的順序收集一遍就自然有序了

簡介：

桶排序(Bucket sort)或所謂的箱排序，是一個排序演算法，工作的原理是將數組分到有限數量的桶子裡。每個桶子再個別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序並不是 比較排序，他不受到 O(n log n) 下限的影響。

定義

假定：輸入是由一個隨機過程產生的[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]是一指標數組，指向桶（鍊錶）。

以上是桶排序是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！