中小网站 广告费,中国企业排名100强,sem seo,社交主题 wordpress排序算法是数据结构与算法中最基本的算法之一#xff0c;其作用就是将一些可以比较大小的数据进行有规律的排序#xff0c;而想要实现这种排序就拥有很多种方法~
#x1f4da; 非线性时间比较类#xff1a; 那么我将通过几篇文章#xff0c;将排序算法中各种算法细化的其作用就是将一些可以比较大小的数据进行有规律的排序而想要实现这种排序就拥有很多种方法~ 非线性时间比较类 那么我将通过几篇文章将排序算法中各种算法细化的详尽的为大家呈现出来 插入类排序数据结构与算法之排序算法-插入排序-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;}}}
② 计数排序(优化)
上述代码中我们简单实现了计数排序但是这样是有缺点的 当数组中元素过大如 [500050055010]如果创建一个大小为 5011 的数组那么浪费的空间就会特别大。 当数组中存在负数如 [123-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;ArrayListLinkedListDouble bucketList new ArrayListLinkedListDouble(bucketNum);for(int i 0;i bucketNum;i){bucketList.add(new LinkedListDouble());}//将数组元素放入桶中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(LinkedListDouble 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个桶ArrayListLinkedListInteger bucketList new ArrayList(10);for (int i 0; i 10; i) {bucketList.add(new LinkedListInteger());}// 进行排序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;}
那么这篇关于计数排序桶排序基数排序的文章到这里就结束啦作者能力有限如果有哪里说的不够清楚或者不够准确还请各位在评论区多多指出我也会虚心学习的我们下次再见啦
