桶排序

桶排序

分類	排序算法
數據結構	数组
最差時間復雜度	$O(n^2)$
平均時間復雜度	$O(n+k)$
最差空間復雜度	$O(n*k)$
最佳算法	$O(n)$

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

桶排序以下列程序進行：

1. 設置一個定量的陣列當作空桶子。
2. 尋訪序列，並且把項目一個一個放到對應的桶子去。
3. 對每個不是空的桶子進行排序。
4. 從不是空的桶子裡把項目再放回原來的序列中。

虛擬碼

function bucket-sort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

外部链接

• Bucket Sort in C++

參考

• Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，and Clifford Stein。Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.4: Bucket sort, pp.174–177.
• Paul E. Black "Postman's Sort" from Dictionary of Algorithms and Data Structures at NIST。
• Robert Ramey The Postman's Sort C Users Journal Aug. 1992