计数排序 素颜马尾好姑娘i 2022-05-28 00:20 326阅读 0赞 ### 计数排序 ### ##### 算法描述:是一种通过计数来达到排序的方法。 ##### ![20180326152550965][] 1.选出数组的最大值k,创建一个k+1长度的数组countArray,countArray的数组下标代表array数组中的元素值,而countArray中的元素值代表的是array中每一个元素的出现次数。 ![20180326152600451][] 2.遍历array数组,统计每个元素的出现次数。例如array\[0\]是7,那么countArray\[7\]++,因为countArray的下标代表array中的数。统计完如下图。 ![20180326152608660][] 3.对countArray进行循环,对每一个元素countArray\[i\] = countArray\[i\] + countArray\[i-1\],目的是统计每一个元素前面有多少个小于它的元素。 ![20180326152617314][] 4.复制array数组存到temp中,循环temp,将temp中i位置的的元素放到array中的--countArray\[temp\[i\]\]位置。也就是array\[--countArray\[temp\[i\]\]\] = temp\[i\]。 ##### 注意: ##### 1.数组只能是整形数组。 2.数组元素必须都大于0。 3.计数排序是一种拿空间换时间的排序算法。 ##### 时间复杂度:O(n) ##### ##### 空间复杂度:O(n) ##### java实现: public static void countSort(int[] array) { int max = getMax(array); // 获取数组的最大值,数组所有值都在0 - max之间 int[] countArray = new int[max + 1]; // 创建一个max+1大小的数组用于表示从0 - max所有数字的重复次数 int[] resultArray = new int[array.length]; resultArray = Arrays.copyOf(array, array.length);// 用于存储排好序的数组 for (int i = 0; i < array.length; i++) { // 循环array数组 countArray[array[i]] += 1; // 因为countArray的下标代表array中的数字,而值代表array中元素的出现次数,所以countArray[array[i]]++ } for (int i = 1; i < countArray.length; i++) { countArray[i] += countArray[i - 1]; // 将countArray中的每一个元素变成与前一个元素相加的和 } for (int i = 0; i < resultArray.length; i++) { int position = countArray[resultArray[i]]; //找出要排序的位置 array[position-1] = resultArray[i]; //位置减一 countArray[resultArray[i]] -= 1; // 统计数要减一 } } private static int getMax(int[] array) { int max = array[0]; for (int i = 0; i < array.length; i++) { if (array[i] < 0) { throw new RuntimeException("数组中有数小于0"); } if (max < array[i]) { max = array[i]; } } return max; } GitHub地址: [https://github.com/xckNull/Algorithms-introduction.git][https_github.com_xckNull_Algorithms-introduction.git] [20180326152550965]: /images/20220528/c290737dee734c41aa3e1fc48812c4a0.png [20180326152600451]: /images/20220528/8fae5d442ba84ce8ba5988b5ab4bf814.png [20180326152608660]: /images/20220528/8361991a1a274e77a5f12f124ab62f66.png [20180326152617314]: /images/20220528/553bf6e2ff6441c09033b256e0352537.png [https_github.com_xckNull_Algorithms-introduction.git]: https://github.com/xckNull/Algorithms-introduction.git
相关 计数排序 数排序是非比较排序,桶排序的一种 时间复杂度:O(n),空间复杂度O(n) ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_1... 一时失言乱红尘/ 2024年04月18日 08:20/ 0 赞/ 150 阅读
相关 计数排序 计数排序 冒泡、选择、插入、归并、快速、希尔、堆排序,都是基于比较的排序,平均时间复杂度最低是O(nlogn)。 计数排序、桶排序、基数排序,都不是基于比较的排序,它们 痛定思痛。/ 2023年02月20日 10:43/ 0 赞/ 57 阅读
相关 排序算法——计数排序 排序算法——计数排序 > 计数排序是一个非基于比较的排序算法。它的优势在于在对一定范围内的整数排序时,快于任何比较排序算法。 这是一种牺牲空间换取时间的做法,当O(k)> 绝地灬酷狼/ 2022年12月23日 06:57/ 0 赞/ 371 阅读
相关 【排序】计数排序 为什么记录这个 在做 [leetcode 561 题][leetcode 561]的时候,第三种解法,看了很久才明白,后来理解实际上是做了一次计数排序。 这个题,直接看 缺乏、安全感/ 2022年11月20日 02:00/ 0 赞/ 298 阅读
相关 计数排序 转载自:[http://www.cnblogs.com/eaglet/archive/2010/09/16/1828016.html][http_www.cnblogs.com Bertha 。/ 2022年08月11日 08:00/ 0 赞/ 283 阅读
相关 计数排序 计数排序,他的主要目的是对整数排序并且会比普通的排序算法性能更好。 1. 初始化一个计数数组,大小是输入数组中的最大的数。 2. 遍历输入数组,遇到一个数 布满荆棘的人生/ 2022年07月14日 01:26/ 0 赞/ 315 阅读
相关 计数排序 对于一个int数组,请编写一个计数排序算法,对数组元素排序。 给定一个int数组A及数组的大小n,请返回排序后的数组。 测试样例: [1,2,3,5,2, 系统管理员/ 2022年06月09日 01:36/ 0 赞/ 308 阅读
相关 计数排序 计数排序 算法描述:是一种通过计数来达到排序的方法。 ![20180326152550965][] 1.选出数组的最大值k,创建一个k+1长度的数组coun 素颜马尾好姑娘i/ 2022年05月28日 00:20/ 0 赞/ 327 阅读
相关 计数排序 / 计数排序:统计小于等于该元素值的元素的个数i,于是该元素就放在目标数组的索引i位(i≥0)。 计数排序基于一个假设,待排序数列的 ゝ一纸荒年。/ 2021年12月18日 05:07/ 0 赞/ 398 阅读
相关 计数排序 计数排序: 假设n个输入元素中的每一个都是在0~区间内的一个整数,其中k为某个整数。当k=O(n)是,排序时间为O(n). 基本思想:对每个输入元素x,确定小于x元素的 淡淡的烟草味﹌/ 2021年09月23日 03:22/ 0 赞/ 516 阅读
还没有评论,来说两句吧...