[图解] 桶排序

桶排序是一种排序的思想，其实现包括计数排序和基数排序两种，冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序都是基于比较的排序，而桶排序提出了一种新的思路，即基于数据状态的排序。

1. 桶排序的思想

(1) 得到无序数组的取值范围

(2) 根据取值范围"创建"对应数量的"桶"

(3) 遍历数组，把每个元素放到对应的"桶"中

(4) 按照顺序遍历桶中的每个元素，依次放到数组中，即可完成数组的排序。

"桶"是一种容器，这个容器可以用多种数据结构实现，包括数组、队列或者栈。

2. 复杂度

• 时间复杂度：遍历数组求最大值最小值为O(n)，遍历数组放入"桶"中复杂度为O(n)，遍历桶取出每个值的复杂度为O(n)，最终的时间复杂度为O(3n)，也就是O(n)
• 空间复杂度：额外的空间取决于元素的取值范围，总的来说为O(n)
• 稳定性：桶排序是否稳定取决于"桶"用什么数据结构实现，如果是队列，那么可以保证相同的元素"取出去"后的相对位置与"放进来"之前是相同的，即排序是稳定的，而如果用栈来实现"桶"，则排序一定是不稳定的，因为桶排序可以做到稳定，所以桶排序是稳定的排序算法

3. 桶排序的实现之计数排序

(1) 计数排序图示过程

1. 找出无序数组的最大值，创建一个长度为最大值+1的空数组

1. 遍历原数组，统计每个元素出现的次数

1. 遍历"桶"，即用于元素个数统计的数组，得到有序的数组

(2) 计数排序Java代码实现

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. 桶排序的实现之基数排序（待更新）

(1) 基数排序图示过程

(2) 基数排序Java代码实现