凡科建的网站怎么做seo,小制作小发明手工图片,二级域名是什么,国航网站建设参加 2018 AI开发者大会#xff0c;请点击 ↑↑↑————— 第二天 —————————————————假定20个随机整数的值如下#xff1a;9#xff0c;3#xff0c;5#xff0c;4#xff0c;9#xff0c;1#xff0c;2#xff0c;7#xff0c;8#xff0c;1请点击 ↑↑↑————— 第二天 —————————————————假定20个随机整数的值如下9354912781365340109 79如何给这些无序的随机整数排序呢非常简单让我们遍历这个无序的随机数列每一个整数按照其值对号入座对应数组下标的元素进行加1操作。比如第一个整数是9那么数组下标为9的元素加1第二个整数是3那么数组下标为3的元素加1继续遍历数列并修改数组......最终数列遍历完毕时数组的状态如下数组每一个下标位置的值代表了数列中对应整数出现的次数。有了这个“统计结果”排序就很简单了。直接遍历数组输出数组元素的下标值元素的值是几就输出几次011233344556778999910显然这个输出的数列已经是有序的了。public static int[] countSort(int[] array) { //1.得到数列的最大值 int max array[0]; for(int i1; iarray.length; i){ if(array[i] max){ max array[i]; } } //2.根据数列最大值确定统计数组的长度 int[] countArray new int[max1]; //3.遍历数列填充统计数组 for(int i0; iarray.length; i){ countArray[array[i]]; } //4.遍历统计数组输出结果 int index 0; int[] sortedArray new int[array.length]; for(int i0; icountArray.length; i){ for(int j0; jcountArray[i]; j){ sortedArray[index] i; } } return sortedArray;}public static void main(String[] args) { int[] array new int[] {4,4,6,5,3,2,8,1,7,5,6,0,10}; int[] sortedArray countSort(array); System.out.println(Arrays.toString(sortedArray));}这段代码在一开头补充了一个步骤就是求得数列的最大整数值max。后面创建的统计数组countArray长度就是max1以此保证数组的最后一个下标是max。95949198999099939192怎么解决这个问题呢很简单我们不再以输入数列的最大值1作为统计数组的长度而是以数列最大值和最小值的差1作为统计数组的长度。同时数列的最小值作为一个偏移量用于统计数组的对号入座。以刚才的数列为例统计数组的长度为 99-901 10 偏移量等于数列的最小值 90 。对于第一个整数95对应的统计数组下标是 95-90 5如图所示什么意思呢让我们看看下面的例子给定一个学生的成绩表要求按成绩从低到高排序如果成绩相同则遵循原表固有顺序。那么当我们填充统计数组以后我们只知道有两个成绩并列95分的小伙伴却不知道哪一个是小红哪一个是小绿下面的讲解会有一些烧脑请大家扶稳坐好。我们仍然以刚才的学生成绩表为例把之前的统计数组变形成下面的样子这是如何变形的呢统计数组从第二个元素开始每一个元素都加上前面所有元素之和。为什么要相加呢初次看到的小伙伴可能会觉得莫名其妙。这样相加的目的是让统计数组存储的元素值等于相应整数的最终排序位置。比如下标是9的元素值为5代表原始数列的整数9最终的排序是在第5位。接下来我们创建输出数组sortedArray长度和输入数列一致。然后从后向前遍历输入数列第一步我们遍历成绩表最后一行的小绿小绿是95分我们找到countArray下标是5的元素值是4代表小绿的成绩排名位置在第4位。同时我们给countArray下标是5的元素值减1从4变成3,代表着下次再遇到95分的成绩时最终排名是第3。第二步我们遍历成绩表倒数第二行的小白小白是94分我们找到countArray下标是4的元素值是2代表小白的成绩排名位置在第2位。同时我们给countArray下标是4的元素值减1从2变成1,代表着下次再遇到94分的成绩时实际上已经遇不到了最终排名是第1。第三步我们遍历成绩表倒数第三行的小红小红是95分我们找到countArray下标是5的元素值是3最初是4减1变成了3代表小红的成绩排名位置在第3位。同时我们给countArray下标是5的元素值减1从3变成2,代表着下次再遇到95分的成绩时实际上已经遇不到了最终排名是第2。这样一来同样是95分的小红和小绿就能够清楚地排出顺序了也正因此优化版本的计数排序属于稳定排序。后面的遍历过程以此类推这里就不再详细描述了。public static int[] countSort(int[] array) { //1.得到数列的最大值和最小值并算出差值d int max array[0]; int min array[0]; for(int i1; iarray.length; i) { if(array[i] max) { max array[i]; } if(array[i] min) { min array[i]; } } int d max - min; //2.创建统计数组并统计对应元素个数 int[] countArray new int[d1]; for(int i0; iarray.length; i) { countArray[array[i]-min]; } //3.统计数组做变形后面的元素等于前面的元素之和 int sum 0; for(int i0;icountArray.length;i) { sum countArray[i]; countArray[i] sum; } //4.倒序遍历原始数列从统计数组找到正确位置输出到结果数组 int[] sortedArray new int[array.length]; for(int iarray.length-1;i0;i--) { sortedArray[countArray[array[i]-min]-1]array[i]; countArray[array[i]-min]--; } return sortedArray;}public static void main(String[] args) { int[] array new int[] {95,94,91,98,99,90,99,93,91,92}; int[] sortedArray countSort(array); System.out.println(Arrays.toString(sortedArray));}1.当数列最大最小值差距过大时并不适用计数排序。比如给定20个随机整数范围在0到1亿之间这时候如果使用计数排序需要创建长度1亿的数组。不但严重浪费空间而且时间复杂度也随之升高。2.当数列元素不是整数并不适用计数排序。如果数列中的元素都是小数比如25.213或是0.00000001这样子则无法创建对应的统计数组。这样显然无法进行计数排序。完1.微信群添加小编微信tangguoyemeng备注“进群姓名公司职位”即可加入【云计算学习交流群】和志同道合的朋友们共同打卡学习2.征稿投稿邮箱lijycsdn.net微信号tangguoyemeng。请备注投稿姓名公司职位。推荐阅读为什么阿里飞猪、滴滴、携程都被质疑滥用大数据杀熟程序员入错行怎么办我们研究了1.5万场活动换个大城市生活可能对你有用大数据揭秘: 原来单身女生有这些特点...放弃培训班自学编程9 个月后我成为年薪 6 位数的软件工程师82岁的北大教授证明了黎曼猜想继承变量覆盖及构造函数失配竟然会导致这些漏洞35岁IT老兵转型AI我做错了吗↓↓↓ 点击【阅读原文】查看「CSDN云计算」往期精彩内容
