SilverLining's Blog

桶排序与排序总结

桶排序

桶排序的思想如下:

  1. 桶排序思想下的排序都是不基于比较的排序;
  2. 时间复杂度为 O(N),额外空间复杂度为 O(M)
  3. 应用范围有限,需要样本的数据状况满足桶的划分。

这里的桶可以由数组、队列、栈等等来实现,这是一种基于统计的排序算法。

常见的桶排序算法有计数排序基数排序

计数排序

计数排序的适用场景要求数据范围不大,且有规律。例如对员工按年龄排序。

通常可以假设员工的年龄是正整数,分布在 [0 ... 100],我们就建立 100 个桶(Bucket)来统计这些数据。那么在一次 O(N)的遍历中,我们就可以数出每个年龄的样本数。

然后我们再遍历一遍数组,直接按下标重新填充新数组即可。

public class CountSort {

    // 假设样本为年龄,分布在 [0 - 100] 的整数
    public void countSort(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];

        // calculate data in bucket
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }

        // refill data array with bucket index
        int i = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0) {
                arr[i++] = j;
            }
        }
    }
}

基数排序

以十进制非负整数排序为例,先找到数组中最大的数,如 123,是个三位数,那么一共需要做 3 轮排序操作。

对每一轮排序,准备 10 个 bucket(十进制),然后按当前位置上的数(个位,十位,百位)按顺序入桶,然后再依次倒回原数组。

其原理是,先按个位数排序,但这个顺序会被下一轮十位数的顺序颠覆,然后十位数的顺序又被百位数的顺序颠覆。但是个位数相同情况下的小次序却得以保留到下一轮,不会被改变。

其时间复杂度为 O(N * log_{10}{max}),忽略较小常数项,则可近似认为 O(N)

public class RadixSort {
    public void plainRadixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        final int RADIX = 10;
        // prepare buckets
        List<List<Integer>> buckets = new ArrayList<>(RADIX);
        for (int i = 0; i < RADIX; i++) {
            buckets.add(new ArrayList<>());
        }

        int maxDigit = getMaxDigit(arr);

        // 时间复杂度 O(N * log_{10}{max})
        for (int digit = 1; digit <= maxDigit; digit++) {
            // put into buckets
            for (int i = 0; i < arr.length; i++) {
                int digitNum = getDigit(arr[i], digit);
                buckets.get(digitNum).add(arr[i]);
            }

            // pour back with origin order by current digit number
            int k = 0;
            for (List<Integer> bucket : buckets) {
                for (Integer num : bucket) {
                    arr[k++] = num;
                }
            }
            for (List<Integer> bucket : buckets) {
                bucket.clear();
            }
        }
    }

    private int getMaxDigit(int[] arr) {
        int maxNum = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
            }
        }
        int maxDigit = 0;
        while (maxNum % 10 != 0) {
            maxDigit++;
            maxNum = maxNum / 10;
        }
        return maxDigit;
    }

    private int getDigit(int num, int digit) {
        return (num / ((int) Math.pow(10, digit - 1))) % 10;
    }
}

但基数排序的实现还有一个经典的优化:不需要准备 10 个桶,用 O(N)的一个等长辅助数据,借助计数排序的思想,逆序计算下标倒回,即可实现排序过程。

public class RadixSort {
    public void classicRadixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        final int RADIX = 10;
        int maxDigit = getMaxDigit(arr);

        int[] help = new int[arr.length];

        // 时间复杂度 O(N * log_{10}{max})
        for (int digit = 1; digit <= maxDigit; digit++) {
            // calculate digit buckets
            int[] count = new int[RADIX];
            for (int i = 0; i < arr.length; i++) {
                int digitNum = getDigit(arr[i], digit);
                count[digitNum]++;
            }

            // count[i]: 当前位 (d 位) 是 (0~i) 的数字有多少个
            // count  [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
            //         0   2   1   3   2   4   1   2   0   0
            // count'  0   2   3   6   8   12  13  15  15  15
            for (int i = 1; i < RADIX; i++) {
                count[i] = count[i] + count[i - 1];
            }

            // 从右向左反过来倒出数字
            for (int i = arr.length - 1; i >= 0; i--) {
                int digitNum = getDigit(arr[i], digit);
                int pos = count[digitNum] - 1;
                help[pos] = arr[i];
                count[digitNum]--;
            }

            // copy back
            for (int i = 0; i < arr.length; i++) {
                arr[i] = help[i];
            }
        }
    }

    private int getMaxDigit(int[] arr) {
        int maxNum = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
            }
        }
        int maxDigit = 0;
        while (maxNum % 10 != 0) {
            maxDigit++;
            maxNum = maxNum / 10;
        }
        return maxDigit;
    }

    private int getDigit(int num, int digit) {
        return (num / ((int) Math.pow(10, digit - 1))) % 10;
    }
}

排序算法的稳定性

排序算法的稳定性是指:对同一个样本多次排序,不会改变元素间的相对次序。 有些排序算法可以实现成稳定的,而有些排序算法无论如何都实现不成稳定的。

基础类型的稳定性没有意义

[1, 2, 3, 3, 3, 5],一个 3 是否稳定的排在另一个 3 之前,并不重要。

非基础类型的稳定性有重要意义

如两个自定义类型 Student 的变量 stu1stu2

class Student {
    String name;
    int age;

    Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
Comparator<Student> ageAscendingComparator = (o1, o2) -> o1.age - o2.age;

Student sTom = new Student("Tom", 18);
Student sJane = new Student("Jane", 18);

不稳定的堆排序对其进行排序,在一次排序后,Tom 排在 Jane 之前。那么再次执行排序算法后,Tom 是否还可以一直稳定的排在 Jane 之前,就是排序算法的稳定性。

如果排序算法不稳定,那么再次执行排序(如再次以班级号排序)就会出现有时 Tom 在前,有时 Jane 在前的问题。

各排序算法稳定性

判断一个排序算法是否有稳定性,主要看他如何对待相同的两个元素。

排序算法 时间复杂度 额外空间复杂度 稳定性 解释
选择排序 O(N^2) O(1) 每次选取最大值,不关心相等
冒泡排序 O(N^2) O(1) 严格大于时才冒泡,相等时不交换
插入排序 O(N^2) O(1) 严格大于时才向前交换,不影响
归并排序 O(N * log N) O(N) 相等时先归并左组,不影响稳定性
随机快排 O(N * log N) O(log N) partition 过程无法稳定,交换的数是 “抛” 出去交换的
堆排序 O(N * log N) O(1) 堆结构调整不关心稳定性
计数排序 O(N) O(M) 不基于比较
基数排序 O(N) O(N) 不基于比较,按入桶顺序倒出

排序算法总结

算法特性总结

  1. 不基于比较的排序,对样本数据有严格要求,不易改写;
  2. 基于比较的排序,只要规定好两个样本怎么比大小就可以复用;
  3. 基于比较的排序,时间复杂度的极限是 O(N * log N)
  4. 时间复杂度 O(N * log N)、额外空间复杂度低于 O(N)、且稳定的基于比较的排序是不存在的;
  5. 为了绝对的速度选快排、为了省空间选堆排序、为了稳定性选归并排序

常见的坑

  1. 归并排序的额外空间复杂度可以变成 O(1),“归并排序内部缓存法”,但是将变得不再稳定;
  2. “原地归并排序” 是垃圾贴,会让时间复杂度变成 O(N^2)
  3. 快速排序稳定性改进,“01 stable sort”,但是会对样本数据要求更多。
  4. 下面这个算法不可能实现。

    在整型数组中,请把奇数放在数组左边,偶数放在数组右边,要求所有奇数之间原始的相对次序不变,所有偶数之间原始相对次序不变。 时间复杂度做到 O(N),额外空间复杂度做到 O(1)

这是一个 0-1 标准的 partition 过程,参考快排的 partition 过程,是无法在额外空间复杂度 O(1)的情况下,做到稳定性的。

工程上对排序算法的优化

  1. 对于值传递的数据,直接快排(不在乎稳定性);对于引用传递的数据,归并排序(保持稳定性)。
  2. 当当前分组中的元素小于 X(32)个的时候,不继续递归下去了,直接做插入排序(小样本常数项更优)。