SilverLining's Blog

桶排序与排序总结

SilverLining

桶排序

桶排序的思想如下：

  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 的变量 stu1 与 stu2：

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）个的时候，不继续递归下去了，直接做插入排序（小样本常数项更优）。
Related posts:

Powered by YARPP.