基数排序 缺乏、安全感 2022-06-04 10:23 173阅读 0赞 比较好理解的算法,以数字为例,先对元素的个位进行分组,组成一个二维数组,然后将此二维数组按照顺序拼接成一个一维数组。再对十位进行分组组成一个二维数组,再做拼接,一次次轮询直到最高位为止。 下面图解一个简单的例子: ![Center][] ![Center 1][] 该算法不仅使用在数字排序上,多维度元素的排序只要合理的建模都可以用基数排序,例如扑克牌中花色代表一个维度,个位数代表一个维度,十位数代表一个维度,十位相等比个位;个位相等比花色。 Java实现: public class RadixSort extends BaseSort{ public static long COUNT;//计数 public static void sort(Integer[] elements, int length) { int position = 1;//位数,从个位开始 int base = 1;//位数对应的数学意义 while (position<=length) { int k = 0; int[][] temps = new int[10][elements.length];//临时准备19个桶,0到9 int[] counts = new int[10];//桶里元素的个数 //将每一个元素扔到对应的桶中 for(int i=0;i<elements.length;i++) { COUNT++;//给元素找到合适的桶视为一次运算 int x = (elements[i]/base)%10; temps[x][counts[x]] = elements[i];//元素放到相应的桶里 counts[x]++; } //按照本轮结果重新排序队列 for(int i=0; i<10; i++) { COUNT++;//找到每一个桶认为一次计算,桶内不做计算,因为桶内元素直接拿来进行排序了 if(counts[i] !=0) { for(int j=0; j<counts[i]; j++) { elements[k] = temps[i][j]; k++; } } } System.out.println("右数第"+position+"位排序完毕后:"); print(elements); position++; base*=10; } } } 测试结果: [783,308,996,102,512,625,498,186,622,349,577,78,404,820,734,413,879,497,981,490,568,257,593,984,91,236,245,259,926,625] Sorting.............. 右数第1位排序完毕后: [820,490,981,91,102,512,622,783,413,593,404,734,984,625,245,625,996,186,236,926,577,497,257,308,498,78,568,349,879,259] 右数第2位排序完毕后: [102,404,308,512,413,820,622,625,625,926,734,236,245,349,257,259,568,577,78,879,981,783,984,186,490,91,593,996,497,498] 右数第3位排序完毕后: [78,91,102,186,236,245,257,259,308,349,404,413,490,497,498,512,568,577,593,622,625,625,734,783,820,879,926,981,984,996] 基数排序消耗:120 时间复杂度上来分析,最影响复杂度的是维度d,每增加一个维度复杂度翻番。其次是每个维度桶的数量和序列长度。时间复杂度=(r1+n)+(r2+n)+(r3+n)+….,假设有d个维度,每次桶的数量都是r,复杂度为O(d(r+n)) 稳定性上来考虑,从图例中可以分析得出相等值再任何一个维度的桶中都会被分配在一起,我们可以在程序中保持他们相对位置不变,所以是稳定的。 空间复杂度上来分析,首先桶数量越大空间占用越大,而且桶的数量跟元素数量 n 是没有关系的,即便是只有 10 个元素我们也可以将他们放在 100 个桶里面,所以从侧面也反映了桶的大小的选择决定了空间资源的消耗。多一个维度,桶空间扩一倍,当然我们可以通过程序来复用桶的空间。元素越多,桶深度需要就越深,如果每个桶都占满将是 r\*n ,但是其实我们只有 n 个元素,虽然二维数组声明了 r\*n 个空间,但是真正只占用了 n 个元素。所以重复使用桶的空间复杂度是 O(r+n), 不重复使用桶的空间复杂度是 O(drn) [Center]: /images/20220604/5c02c27a46c845ab89387e80fb3a0314.png [Center 1]: /images/20220604/8143b5f5355243538748bea2e2c01810.png
相关 基数排序 基数排序与本系列前面讲解的七种排序方法都不同,它不需要比较关键字的大小。 它是根据关键字中各位的值,通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。 不 以你之姓@/ 2022年08月21日 05:35/ 0 赞/ 160 阅读
相关 基数排序 基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。比较官方地说,基数排序是一种基于多关键字的排序。 基 蔚落/ 2022年06月15日 06:11/ 0 赞/ 175 阅读
相关 基数排序 对于一个int数组,请编写一个基数排序算法,对数组元素排序。 给定一个int数组A及数组的大小n,请返回排序后的数组。保证元素均小于等于2000。 测试样例: 分手后的思念是犯贱/ 2022年06月09日 01:36/ 0 赞/ 175 阅读
相关 基数排序 比较好理解的算法,以数字为例,先对元素的个位进行分组,组成一个二维数组,然后将此二维数组按照顺序拼接成一个一维数组。再对十位进行分组组成一个二维数组,再做拼接,一次次轮询直到最 缺乏、安全感/ 2022年06月04日 10:23/ 0 赞/ 174 阅读
相关 基数排序 写在前面 > 计数排序,基数排序 总结 计数排序是非基于比较的排序方式,和一般基于比较的排序不同。 基于比较的排序的算法的平均复杂度的下界也是o(nlgn)。 柔情只为你懂/ 2022年05月12日 02:54/ 0 赞/ 215 阅读
相关 基数排序 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。 客官°小女子只卖身不卖艺/ 2022年01月29日 02:01/ 0 赞/ 241 阅读
相关 基数排序 package com.sort; / @Auther: 大哥的叔 @Date: 2019/8/8 13:06 @ àì夳堔傛蜴生んèń/ 2021年11月05日 18:12/ 0 赞/ 263 阅读
相关 基数排序 在箱子排序中,尽管时间复制度仅仅有(n),但假设其箱子序列较大的话将会导致程序的空间复杂度较大,所以对于对于属性值跨度比較大的序列能够採用基数排序法。 概述:详细的做法 痛定思痛。/ 2021年09月19日 10:12/ 0 赞/ 342 阅读
相关 基数排序 在介绍基数排序前,我们先简单介绍下桶排序:例如有10个桶,我们给分边编号1——10,然后寻找其中装有水的桶。 ![70][] 我们可以显而易见,其中装有水的桶编号是 清疚/ 2021年09月15日 20:52/ 0 赞/ 352 阅读
还没有评论,来说两句吧...