桶排序、计数排序、基数排序

桶排序、计数排序、基数排序（不是基于比较的排序）

1. 非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以实际中并不经常使用
2. 时间复杂度O(N)，额外空间复杂度O(N)
3. 稳定的排序

桶排序算法如下：

public class BucketSort {
    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 j = 0; j<arr.length; j++) {
            bucket[arr[j]]++;
        }
        int i = 0;
        for (int k=0; k<bucket.length; k++) {
            while (bucket[k]-- >0) {
                arr[i++] = k;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3,9,12,5,8,13,1};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}