箱排序

箱排序也稱桶排序(Bucket Sort)，箱排序中，箱子的個數取決於關鍵字的取值範圍。一般情況下每個箱子中存放多少個關鍵字相同的記錄是無法預料的，故箱子的類型應設計成鍊表為宜。

箱排序(Bin Sort)
1、箱排序的基本思想
箱排序也稱桶排序(Bucket Sort)，其基本思想是：設定若干個箱子，依次掃描待排序的記錄R[0]，R[1]，…，R[n-1]，把關鍵字等於k的記錄全都裝入到第k個箱子裡(分配)，然後按序號依次將各非空的箱子首尾連線起來(收集)。
【例】要將一副混洗的52張撲克牌按點數A<2<…<J<Q<K排序，需設定13個"箱子"，排序時依次將每張牌按點數放入相應的箱子裡，然後依次將這些箱子首尾相接，就得到了按點數遞增序排列的一副牌。
2、箱排序中，箱子的個數取決於關鍵字的取值範圍。
若R[0..n-1]中關鍵字的取值範圍是0到m-1的整數，則必須設定m個箱子。因此箱排序要求關鍵字的類型是有限類型，否則可能要無限個箱子。
3、箱子的類型應設計成鏈表為宜
一般情況下每個箱子中存放多少個關鍵字相同的記錄是無法預料的，故箱子的類型應設計成鍊表為宜。
4、為保證排序是穩定的，分配過程中裝箱及收集過程中的連線必須按先進先出原則進行。
（1） 實現方法一
每個箱子設為一個鏈佇列。當一記錄裝入某箱子時，應做人隊操作將其插入該箱子尾部；而收集過程則是對箱子做出隊操作，依次將出隊的記錄放到輸出序列中。
（2） 實現方法二
若輸入的待排序記錄是以鍊表形式給出時，出隊操作可簡化為是將整個箱子鍊表連結到輸出鍊表的尾部。這只需要修改輸出鍊表的尾結點中的指針域，令其指向箱子鍊表的頭，然後修改輸出鍊表的尾指針，令其指向箱子鍊表的尾即可。
5、算法簡析
分配過程的時間是O(n)；收集過程的時間為O(m) （採用鍊表來存儲輸入的待排序記錄）或O(m+n)。因此，箱排序的時間為O(m+n)。若箱子個數m的數量級為O(n)，則箱排序的時間是線性的，即O(n)。
注意：
箱排序實用價值不大，僅適用於作為基數排序(下節介紹)的一個中間步驟。