桶排序是一種排序的思想，其實現(xiàn)包括計數(shù)排序和基數(shù)排序兩種，冒泡排序、選擇排序、插入排序、歸并排序、快速排序和堆排序都是基于比較的排序，而桶排序提出了一種新的思路，即基于數(shù)據(jù)狀態(tài)的排序。

1. 桶排序的思想

(1) 得到無序數(shù)組的取值范圍

(2) 根據(jù)取值范圍"創(chuàng)建"對應(yīng)數(shù)量的"桶"

(3) 遍歷數(shù)組，把每個元素放到對應(yīng)的"桶"中

(4) 按照順序遍歷桶中的每個元素，依次放到數(shù)組中，即可完成數(shù)組的排序。

"桶"是一種容器，這個容器可以用多種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，包括數(shù)組、隊列或者棧。

2. 復(fù)雜度

• 時間復(fù)雜度：遍歷數(shù)組求最大值最小值為O(n)，遍歷數(shù)組放入"桶"中復(fù)雜度為O(n)，遍歷桶取出每個值的復(fù)雜度為O(n)，最終的時間復(fù)雜度為O(3n)，也就是O(n)
• 空間復(fù)雜度：額外的空間取決于元素的取值范圍，總的來說為O(n)
• 穩(wěn)定性：桶排序是否穩(wěn)定取決于"桶"用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，如果是隊列，那么可以保證相同的元素"取出去"后的相對位置與"放進(jìn)來"之前是相同的，即排序是穩(wěn)定的，而如果用棧來實現(xiàn)"桶"，則排序一定是不穩(wěn)定的，因為桶排序可以做到穩(wěn)定，所以桶排序是穩(wěn)定的排序算法

3. 桶排序的實現(xiàn)之計數(shù)排序

(1) 計數(shù)排序圖示過程

1. 找出無序數(shù)組的最大值，創(chuàng)建一個長度為最大值+1的空數(shù)組

2. 遍歷原數(shù)組，統(tǒng)計每個元素出現(xiàn)的次數(shù)

3. 遍歷"桶"，即用于元素個數(shù)統(tǒng)計的數(shù)組，得到有序的數(shù)組

(2) 計數(shù)排序Java代碼實現(xiàn)

public static void bucketSort(int[] arr) {
    
    if (arr == null || arr.length < 2) {
        return;
    }
    
    int max = Integer.MIN_VALUE;
    
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }
    
    int[] bucket = new int[max + 1];
    
    for (int i = 0; i < arr.length; i++) {
        bucket[arr[i]]++;
    }
    
    int i = 0;
    
    for (int j = 0; j < bucket.length; j++) {
        while (bucket[j]-- > 0) {
            arr[i++] = j;
        }
    }
}

4. 桶排序的實現(xiàn)之基數(shù)排序（待更新）

(1) 基數(shù)排序圖示過程

(2) 基數(shù)排序Java代碼實現(xiàn)