排序算法之计数排序和基数排序以及桶排序

这三种排序都不是基于比较的排序，典型的空间换时间算法。

0. 修改父类

因为父类中针对稳定性判断时泛型的其它类，但是下方的排序只支持整数(浮点型等非自定义类型)。

     /**
     * 判断稳定性
     * @return
     */
    private boolean isStable(){
        if (this instanceof CountingSortPro) return true;
        if (this instanceof CountingSort) return true;
        if (this instanceof ShellSort) return false;
        if (this instanceof RadixSort) return true;
        // 根据student类型测试，如果年龄相同的分数呈递增状态则是稳定性排序。
        Student[] students = new Student[20];
        for (int i = 0; i < students.length; i++) {
            students[i] = new Student(i * 10, 10);
        }
        sort((T[]) students);
        for (int i = 1; i < students.length; i++) {
            int score = students[i].score;
            int prevScore = students[i - 1].score;
            if (score != prevScore + 10) return false;
        }
        return true;
    }

1. 计数排序（Counting Sort）

1954年提出，适合对一定范围内的整数进行排序。

1.1 简单版本实现

核心思想：统计每个整数在序列中出现的次数，进而推导每个整数在有序序列中的索引。

• 原数组
  
• 新建一个数组存储整数出现的次数：
• 推导结果：

/**
 * @Description 计数排序实现
 * @date 2022/5/8 15:05
 */
public class CountingSort extends Sort<Integer> {

    @Override
    protected void sort() {
        // 获取数组最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }

        // 开辟内存空间
        int[] counts = new int[max + 1];

        // 统计次数
        for (int i = 0; i < arr.length; i++) {
            counts[arr[i]]++;
        }

        // 根据出现的次数对整数进行排序
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            while (counts[i] > 0) {
                arr[index] = i;
                index++;
                counts[i]--;
            }
        }
    }

}

1.2 优化思路

• 缺点：在上方1.1版本中存在以下问题：

  1. 不是稳定性排序；
  2. 消耗内存过大；
  3. 不能对负整数进行排序。

• 优化内存空间和负整数排序：获取最小值，将内存空间的大小从[0,max]减少到[min,max]；这种实现也达到了可以对负整数优化的目的，不再以元素值对应索引值，而是以顺序对应索引。得出结论：元素k在counts中的索引值为：k - min
  

• 稳定性排序：每个次数加上前面所有元素出现的次数，可以得到当前元素在有序序列种的位置。
  

• 完成排序：得出结论：元素k在有序序列中的索引为：counts[ k - min ] - p。p为倒数第几个k。
  例如：索引为 6 的 7 是倒数第一个 7 ，在counts中的索引为： 7 - 3 = 4；在有序序列中的索引为：7 - 1 = 6 。
  

1.3 优化实现

• 从后往前遍历：
  
• 使用相应的值计算出索引之后，下方counts序列中也执行减一，这样可以做到稳定性。
  
• 然后将值放入到有序序列中：
  

/**
 * @Description 优化版计数排序
 * @date 2022/5/8 15:58
 */
public class CountingSortPro extends Sort<Integer> {
    @Override
    protected void sort() {
        // 获取数组最大值
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
            if (arr[i] < min){
                min = arr[i];
            }
        }

        // 开辟内存空间
        int[] counts = new int[max - min + 1];

        // 统计次数
        for (Integer integer : arr) {
            counts[integer - min]++;
        }

        // 统计累加的次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        // 倒序遍历然后将值放到合适位置
        int[] newArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            // 将当前值根据在counts中的索引计算出新的位置。
            // 先将值减一，在计算出当前值对应的索引
            int index = --counts[arr[i] - min];
            // 放到新序列中。
            newArr[index] = arr[i];
        }

        // 覆盖序列
        for (int i = 0; i < newArr.length; i++) {
            arr[i] = newArr[i];
        }
    }
}

1.4 总结分析

1. 时间复杂度：最好、最坏、平均：O(n + k)。
2. 空间复杂度：O(n + k)。
3. 属于稳定排序。

1.5 自定义对象实现计数排序

如果自定义的对象包含可共排序的整数类型，也可以使用计数排序。

• 自定义类：

/**
 * @Description 自定义对象测试
 * @date 2022/5/8 20:20
 */
@Data
@AllArgsConstructor
@ToString
public class Person {
    private Integer id;
    private String name;
}

• 计数排序：

/**
 * @Description 自定义对象计数排序
 * @date 2022/5/8 15:58
 */
public class CountingSortObj{

    public static void main(String[] args) {
        Person[] arr = {new Person(1,"aa")
                ,new Person(-1,"bb"),
                new Person(99,"cc"),
                new Person(5,"dd"),
                new Person(0,"ee"),};
        sort(arr);
        for (Person person : arr) {
            System.out.println(person);
        }
    }

    private static void sort(Person[] arr) {
        // 获取数组最大值
        int max = arr[0].getId();
        int min = arr[0].getId();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i].getId() > max){
                max = arr[i].getId();
            }
            if (arr[i].getId() < min){
                min = arr[i].getId();
            }
        }

        // 开辟内存空间
        int[] counts = new int[max - min + 1];

        // 统计次数
        for (Person person : arr) {
            counts[person.getId() - min]++;
        }

        // 统计累加的次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        // 倒序遍历然后将值放到合适位置
        Person[] newArr = new Person[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            // 将当前值根据在counts中的索引计算出新的位置。
            // 先将值减一，在计算出当前值对应的索引
            int index = --counts[arr[i].getId() - min];
            // 放到新序列中。
            newArr[index] = arr[i];
        }

        // 覆盖序列
        System.arraycopy(newArr, 0, arr, 0, newArr.length);
    }
}

2. 基数排序（Radix Sort）

非常适合用于整数排序，特别是非负整数。

2.1 执行流程

依次对个位数、十位数、百位数…进行排序（从低位到高位）。

• 原始数组
  
• 对个位数进行排序后
  
• 再对十位数进行排序，没有就为0
  
• 最后对百位数再进行排序：
  

2.2 实现

因为每次针对位数进行排序时，只有 0~9 ，非常符合使用计数排序。
所以这里整合计数排序进行实现。

/**
 * @Description 基数排序
 * @date 2022/5/8 20:37
 */
public class RadixSort extends Sort<Integer>  {

    @Override
    protected void sort() {
        // 获取数组最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }

        // 计算基数
            // 个位数 ： x / 1 % 10
            // 十位数 ： x / 10 % 10
            // 百位数 ： x / 100 % 10

        // 针对最大值的位数判断需要执行多少次计数排序
        for (int divider = 1; divider <= max; divider *= 10) {
            countingSort(divider);
        }
    }


    /**
     * 针对基数进行计数排序
     * @param divider 被除数
     */
    private void countingSort(int divider){
        int[] counts = new int[10];

        for (Integer integer : arr) {
            counts[integer / divider % 10]++;
        }

        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        int[] newArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int index = --counts[arr[i] / divider % 10];
            newArr[index] = arr[i];
        }

        for (int i = 0; i < newArr.length; i++) {
            arr[i] = newArr[i];
        }
    }

}

2.3 复杂度分析

1. 最好、最坏、平均复杂度：O(d * (n + k))，d是最大值的位数，k是进制数；
2. 空间复杂度：O( n + k )，k是进制数；
3. 属于稳定排序。

3. 桶排序（Bucket Sort） 3.1 执行流程

1. 创建一定数量的桶（数组、或者链表）；
2. 按照一定规则将序列中的元素均匀的分配到对应的桶；
3. 分别对桶单独排序；
4. 将所有的非空桶元素合并成有序序列。

• 对小数排序：因为小数全部的是小于一的，如果直接按照值放入到桶中都会放到索引为0 的桶中，这里乘以数组长度：
  

• 根据乘以 数组长度 之后的索引放到对应的桶中：
  

• 分别进行排序：

• 将所有元素统一进行排序：

3.2 实现

/**
 * @Description 桶排序
 * @date 2022/5/8 20:58
 */
public class BucketSort {

    public static void main(String[] args) {
        Double[] arr = {0.34, 0.47, 0.29, 0.84, 0.45, 0.38, 0.35, 0.76};
        bucketSort(arr);
        for (Double aDouble : arr) {
            System.out.print(aDouble + "_");
        }
    }

    public static void bucketSort(Double[] arr){
        // 创建一个存放 double类型的list 的数组
        List<Double>[] buckets = new List[arr.length];
        // 遍历数组
        for (Double info : arr) {
            // 根据长度计算索引
            int bucketIndex = (int) (info * arr.length);
            // 将当前索引位置的数组赋值给list
            List<Double> bucket = buckets[bucketIndex];
            // 如果list为空，新建一个
            if (bucket == null){
                bucket = new LinkedList<>();
                buckets[bucketIndex] = bucket;
            }
            // 将当前值存放到索引位置的链表中
            bucket.add(info);
        }

        // 对每个桶进行排序
        int index = 0;
        // 遍历桶数组
        for (List<Double> bucket : buckets) {
            // 如果桶数组为空，不进行 *** 作
            if (bucket == null) continue;
            // 调用JDK方法对当前桶进行排序
            bucket.sort(null);
            // 遍历当前桶，赋值给原先的序列
            for (Double aDouble : bucket) {
                arr[index++] = aDouble;
            }
        }
    }
}

3.3 复杂度分析

1. 空间复杂度：O(n + m)，m是桶的数量；
2. 时间复杂度：O( n + k)；
3. 属于稳定排序