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

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

📚 非线性时间比较类：

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

📕 插入类排序：数据结构与算法之排序算法-插入排序-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;}

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