桶排序

维基百科，自由的百科全书

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

桶排序以下列程序進行：

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

目录 1 虛擬碼 2 Postman's sort 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]

"array" 是要被排序的陣列，而 "n" 則表示桶子的數量。 Here array is the array to be sorted and n is the number of buckets to use. The function msbits(x,k) returns the k most significant bits of x (floor(x/2^(size(x)-k))); different functions can be used to translate the range of elements in array to n buckets, such as translating the letters A-Z to 0-25 or returning the first character (0-255) for sorting strings. The function next-sort is a sorting function; using bucket-sort itself as next-sort produces a relative of radix sort; in particular, the case n = 2 corresponds to quicksort (although potentially with poor pivot choices).

[编辑] Postman's sort

The Postman's sort is a sorting algorithm, a variant of a bucket sort where attributes of the key are described so the algorithm can allocate buckets efficiently. This is the algorithm used by letter-sorting machines in the post office: first states, then post offices, then routes, etc. Since keys are not compared against each other, sorting time is O(cn), where c depends on the size of the key and number of buckets. This is similar to radix sort, but works "top down" or "most significant digit first" while radix sort works "bottom up" or "least significant digit first."

[编辑] 額外連結

• 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