数据结构与算法之排序算法-(计数,桶,基数排序)

排序算法是数据结构与算法中最基本的算法之一，其作用就是将一些可以比较大小的数据进行有规律的排序，而想要实现这种排序就拥有很多种方法~

📚 非线性时间比较类：

那么我将通过几篇文章，将排序算法中各种算法细化的，详尽的为大家呈现出来：

📕 插入类排序：数据结构与算法之排序算法-插入排序-CSDN博客

📖 直接插入排序

📖 希尔排序

📕 交换类排序：数据结构与算法之排序算法-快速排序(分治)-CSDN博客

📖 冒泡排序

📖 冒泡排序-优化

📖 快速排序(Hoare，挖坑法，前后指针法)

📖 快速排序-优化

📕 选择类排序：数据结构与算法之排序算法-选择排序-CSDN博客

📖 简单选择排序

📖 堆排序

📕 归并类排序：数据结构与算法之排序算法-归并排序-CSDN博客

📖 归并排序

📚 线性时间非比较类：

📕 非比较类排序：[本篇]

📖 计数排序

📖 桶排序

📖 基数排序

一、计数排序

稳定性：稳定

时间复杂度：O(n + m)

额外空间复杂度：O(n + m)

大家应该也注意到了，这次学习到的排序算法，不仅具有稳定性，时间复杂度竟然还趋近O(n)！这是相当快的一种排序算法了。

那么为什么它能达到这么优秀的时间复杂度呢？主要就是因为它并不需要对元素之间进行比较~那么有人可能就要发出疑问，不进行比较又如何知道元素与元素间的大小关系呢？

① 计数排序

📚 算法思想：

计数排序的基本思想：把原数组元素作为数组的下标，创建一个临时数组 arr，使得 arr 至少能将原数组中所有数据都存入数组中。

然后遍历原数组，将遍历到的元素与 arr 下标进行匹配，并使 arr[index]++，代表该数字出现的次数 +1，而将数组遍历结束后，arr 从 start 下标到 end 下标存储的数据正好由下标默认排序好了，并且数据也准确的存到了正确位置~

了解了计数排序的基本思想后，大家或许也知道了为什么它的速度如此之快，相应的，大家应该也能理解为什么它没有"快速排序"，"归并排序"那么实用了，那就是"额外空间复杂度太高"

⭐ 图示：

📖 代码示例：

    public static void countingSort(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        int[] arr = new int[max + 1];
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            arr[index]++;
        }
        int k = 0;
        for (int i = 0; i < arr.length; i++) {
            while (arr[i] != 0) {
                array[k] = i;
                arr[i]--;
                k++;
            }
        }
    }

② 计数排序(优化)

上述代码中，我们简单实现了计数排序，但是这样是有缺点的：

📕 当数组中元素过大：如 [5000，5005，5010]，如果创建一个大小为 5011 的数组，那么浪费的空间就会特别大。

📕 当数组中存在负数：如 [1，2，3，-1]，创建数组后，是搜索不到 ' -1 ' 下标的。

📚 算法思想：

在原来的基础上，同时算出数组中的最小值，创建一个大小为[max - min + 1]的数组，这样就能有效的降低额外空间的损耗。

并且放入和取出元素时，寻找的下标也相应变成 arr[index] - min ，这样就能够彻底避免访问下标小于0的非法访问。

📖 代码示例：

    public static void countingSort(int[] array) {
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        int[] arr = new int[max - min + 1];
        for (int i = 0; i < array.length; i++) {
            int index = array[i] - min;
            arr[index]++;
        }
        int k = 0;
        for (int i = 0; i < arr.length; i++) {
            while (arr[i] != 0) {
                array[k] = i + min;
                arr[i]--;
                k++;
            }
        }
    }

③ 效率测试

顺便一提，快速排序达到的速度为40ms左右，归并排序达到的速度为30ms左右~

二、桶排序

稳定性：稳定

时间复杂度：O(n)

额外空间复杂度：O(m)

上面的计数排数，很快倒是很快，但是它也有相应的缺点

📕 无法对浮点型数据进行排序，因为无法通过浮点型数据查找对应下标

这个算法属于计数排序的一种升级版，它的思想和计数排序类似，也是通过数据的值进行分类。

但它和计数排序也有些不同：

📕 它并没有通过数据的值来直接对应下标，而是通过创建一些"桶"，并且为它们设定"区间"，从而通过数据查找对应区间，这样就能够避免"浮点数非法查找下标"的问题了。

① 桶排序

📚 算法思想：

桶排序的基本思想：根据原数组的最大值 max 和最小值 min 来划分区间，由这些区间来创造一些"桶"。而每一个桶代表一个区间范围，里面可以承载一个或多个元素。

创建好"桶"后，遍历原数组，将数组中的数据放到对应区间的桶中，然后再分别将桶中的元素排序，这样排好序后，就能够得到我们最终想要的有序数组了。

⭐ 图示：

📖 代码示例：

    public static double[] bucketSort(double[] array) {
        //取最大值和最小值，并求出差值
        int len = array.length;
        double max = array[0];
        double min = array[0];
        for (int i = 1; i < len; i++) {
            max = Math.max(array[i], max);
            min = Math.min(array[i], min);
        }
        double d = max - min;
        //创建桶
        int bucketNum = len;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);
        for(int i = 0;i < bucketNum;i++){
            bucketList.add(new LinkedList<Double>());
        }
        //将数组元素放入桶中
        for(int i = 0;i < len;i++){
            int num = (int)((array[i] - min) * (bucketNum - 1) / d);
            bucketList.get(num).add(array[i]);
        }
        //对每个桶进行排序
        for(int i = 0;i < bucketList.size();i++){
            Collections.sort(bucketList.get(i));
        }
        double[] sortArr = new double[len];
        int index = 0;
        for(LinkedList<Double> list:bucketList){
            for(double element: list){
                sortArr[index++] = element;
            }
        }
        return sortArr;
    }

三、基数排序

稳定性：稳定

时间复杂度：O(n * k)

额外空间复杂度：O(n * k)

① 基数排序

📚 算法思想：

基数排序的基本思想：基数排序的算法思想是，将整数按照位数分别切割成不同的数字。

当每次将数组中的数据按位数分割结束后，分别放入以位数为单位的"桶"中。

然后遍历桶，按照顺序将元素取出，再重新进行分割，入桶等操作，直到分割位数的次数达到了数组中位数最高的元素的限制，排序结束。

📖 代码示例：

        public static int[] radioSort(int[] arr) {
        if(arr == null || arr.length < 2) return arr;
        int n = arr.length;
        int max = arr[0];
        // 找出最大值,计算最大值是几位数
        for (int i = 1; i < n; i++) {
            if(max < arr[i]) max = arr[i];
        }
        int num = 1;
        while (max / 10 > 0) {
            num++;
            max = max / 10;
        }
        // 创建10个桶
        ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            bucketList.add(new LinkedList<Integer>());
        }
        // 进行排序
        for (int i = 1; i <= num; i++) {
            for (int j = 0; j < n; j++) {
                int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10;
                bucketList.get(radio).add(arr[j]);
            }
            int k = 0;
            for (int j = 0; j < 10; j++) {
                for (Integer t : bucketList.get(j)) {
                    arr[k++] = t;
                }
            }
        }
        return arr;
    }

那么这篇关于计数排序，桶排序，基数排序的文章到这里就结束啦，作者能力有限，如果有哪里说的不够清楚或者不够准确，还请各位在评论区多多指出，我也会虚心学习的，我们下次再见啦