BucketSort

特征 feature

桶排序最好情况下可以在线性时间O(N),桶排序的时间复杂度取决于对各个桶之间数据进行排序的时间复杂度。

是否稳定

稳定的排序算法， 判断就是 a[i] = a[j], i < j, 在排序完成之后，i和j下标对应的元素顺序没有改变。

排序过程

• 创建一个容量为待排序数组中最大元素值的数组
• 遍历待排序数组，将辅助数组填充， 对应的将待排序元素作为辅助数组的小标，来统计该大小的元素出现的次数
• 遍历辅助数组，来修改待排序数组内容，按顺序将辅助数组中的值大于0的元素下标赋值给待排序数组。

代码实现

public static void bucketSort(int[] a, int max) {
        int[] buckets;

        if (a == null || max < 1) {
            return;
        }

//        创建一个容量为max的数组buckets
        buckets = new int[max];

//        1. 计数
        for (int j : a) {
            buckets[j]++;
        }

//        2. 排序
        for (int i = 0, j = 0; i < max; i++) {
            while ((buckets[i]--) > 0) {
                a[j++] = i;
            }
        }
    }