桶排序（Bucket sort）或所謂的箱排序，是一個排序算法，工作的原理是將數組分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ(n)）。但桶排序并不是比較排序，他不受到O(n log n)下限的影響。
桶排序以下列程序進行：
1.設置一個定量的數組當作空桶子。
2.尋訪序列，并且把項目一個一個放到對應的桶子去。
3.對每個不是空的桶子進行排序。
4.從不是空的桶子里把項目再放回原來的序列中。
桶排序圖文示例
桶排序代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
/* * 桶排序 * * 參數說明： * a -- 待排序數組 * n -- 數組a的長度 * max -- 數組a中最大值的范圍 */void bucket_sort(int a[], int n, int max){ int i, j; int *buckets; if (a==NULL || n<1 || max<1) return ; // 創建一個容量為max的數組buckets，并且將buckets中的所有數據都初始化為0。 if ((buckets=(int *)malloc(max*sizeof(int)))==NULL) return ; memset(buckets, 0, max*sizeof(int)); // 1. 計數 for(i = 0; i < n; i++) buckets[a[i]]++; // 2. 排序 for (i = 0, j = 0; i < max; i++) while( (buckets[i]--) >0 ) a[j++] = i; free(buckets);} |
說明：
bucketSort(a, n, max)是作用是對數組a進行桶排序，n是數組a的長度，max是數組中最大元素所屬的范圍[0,max)。
假設a={8,2,3,4,3,6,6,3,9}, max=10。此時，將數組a的所有數據都放到需要為0-9的桶中。如下圖：
在將數據放到桶中之后，再通過一定的算法，將桶中的數據提出出來并轉換成有序數組。就得到我們想要的結果了。
