桶排序

• 桶排序（Bucket Sort），其核心思想是将要排序的数据，分到几个有序的桶里（每个桶代表一个范围大小），每个桶的数据再进行单独排序，之后再将每个桶的数据按顺序取出组合即可

• 假定对 n 个数据排序，将其均匀分到 m 个桶中，每个桶含有 k=n/m 个数据，对每个桶使用快速排序，时间复杂度为 O(klogk)，则总的时间复杂度为 O(mklogk) = O(nlog(n/m))。因此当 m 接近 n 时，桶排序复杂度接近 O(n) 。但是另一方面，如果数据无法被均匀划分，极端情况下集中在同一个桶中，则此时复杂度退化为 O(nlogn)

• 桶排序适用于外部排序，即指数据存储在磁盘中，数据量较大，但内存有限，无法将数据一次全部加载进内存的情况。此时可以将数据尽可能均匀分为几个桶，每次只加载读取一个桶的数据排序，排序后写入文件。如果一个桶的数据仍然大于内存，则对该桶数据进行进一步划分，然后再进行排序

稳定性：稳定，取决于用于桶内排序的算法（如果使用快速排序，则不稳定）

执行效率：平均 O(n)，最差即 n 个元素快速排序的最差复杂度 O(n^2)

计数排序

• 计数排序（Counting Sort），是桶排序的特殊情况，即当要排序的数据所处范围不大时，如都处于 [0..k] 区间，则直接将数据划分为 k 个桶，每个桶代表一个数值，省去了桶内部的排序时间

• 由于每个桶代表一个数值，因此遍历数组，即可得到每个数值的元素个数，即计数数组 count[]，通过对 count[] 从左至右进行累加求和，即可得到每个数值在数组中的排列顺序，由该顺序数组即可对原数组进行排序

• 计数排序适合数据范围不大的场合，如果 k 远大于 n，则不适合使用计数排序。此外，计算排序只能对非负元素进行排序，因此如果数组中存在负数，需要做转化

稳定性：在对原数组进行排序时，可以使用从后向前遍历原数组，每次查询顺序数组获得该数值所处位置，并更新顺序数组，即可保证前后顺序不变（顺序数组 count[val] 初始存储的是，原数组中值为 val 的最后一次出现的元素，处于的顺序）

内存消耗：O(n+k)，k 是数组中最大值，n 是数组长度，因为会用到临时数组

执行效率：O(n+k))

public static void countingSort(int[] arr) {
    if (arr.length <= 1) return;
    // 1. 寻找最大值
    int max = arr[0];
    for (int num : arr) {
        max = Math.max(max, num);
    }

    // 2. 创建计数数组，初始化为0
    int[] count = new int[max+1];
    for (int i = 0; i < count.length; i++) count[i] = 0;

    // 开始统计（计数）
    for(int num : arr) {
        count[num]++;
    }

    // 3. 累加计数数组，获取顺序数组
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i-1];
    }

    // 4. 根据顺序数组，对原数组进行排序
    int[] res = new int[arr.length];  // 临时数组
    for (int i = arr.length - 1; i >= 0; i--) {
        int val = arr[i];
        int order = count[val];
        res[order-1] = val;
        count[val]--;        // 更新顺序数组
    }

    // 5. 拷贝结果回原数组
    for (int i = 0; i < arr.length; i++) {
        arr[i] = res[i];
    }
}

基数排序

• 基数排序（Radix Sort），其核心思想是对数据按位排序，如先按照个位（最后一位）排序，再按照十位（倒数第二位）排序，依次类推，当按照第一位对数据排序后，数据即达到有序

• 基数排序对数据有所要求：（1）数据可以分割出「位」的概念，且「位」之间存在递进关系；（2）每一位的数据范围不能太大，否则无法借助线性排序算法达到近似 O(n) 的复杂度

稳定性：稳定，按位排序要求用于辅助的排序算法必须是稳定的，否则最后一次排序只能保证第一位是有序的

执行效率：如果要排序的数据有 d 位，则利用线性排序作为辅助排序算法，总的复杂度为 O(d*n)，当 d 不大时，复杂度近似于 O(n)