公司的网站建设要记到什么科目,做图素材的网站有哪些,wordpress 定时发送,wordpress文章目录插件基数排序#xff08;Radix sort#xff09;是一种非比较型整数排序算法#xff0c;其原理是将整数按位数切割成不同的数字#xff0c;然后按每个位数分别比较。 一、算法基本思想 #xff08;1#xff09;基本思想 基数排序是基于桶排序来实现。通过键值的部分信息#… 基数排序Radix sort是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。 一、算法基本思想 1基本思想 基数排序是基于桶排序来实现。通过键值的部分信息将要排序的元素分配至某些“桶”中以此达到排序的作用。 基数排序的方式可以采用LSDLeast significant digital或MSDMost significant digitalLSD的排序方式由键值的最右边开始而MSD则相反由键值的最左边开始。 2运行过程 基数排序算法LSD的运行过程如下 1、根据待排序整数序列的进制d十进制为10十六进制为16...设置d个桶编号分别为01...d-1 2、各个记录按照其关键字最低位的值的大小放入到相应的桶中 3、按照桶编号从小到大的顺序收集各个桶中的数据对于同一桶中的数据按照先后次序收集先进桶先收集 4、按照关键字的次低位重复上述步骤...没有高位的数据则高位补0 按增量序列个数k对序列进行k 趟排序 3每趟排序根据对应的增量ti将待排序列分割成若干长度为m 的子序列分别对各子表进行直接插入排序。仅增量因子为1 时整个序列作为一个表来处理表长度即为整个序列的长度。 3示例 二、算法实现核心代码 Java实现 public class RadixSort
{public static void sort(int[] number, int d) //d表示最大的数有多少位{intk 0;intn 1;intm 1; //控制键值排序依据在哪一位int[][]temp newint[10][number.length]; //数组的第一维表示可能的余数0-9int[]order newint[10]; //数组orderp[i]用来表示该位是i的数的个数while(m d){for(inti 0; i number.length; i){intlsd ((number[i] / n) % 10);temp[lsd][order[lsd]] number[i];order[lsd];}for(inti 0; i 10; i){if(order[i] ! 0)for(intj 0; j order[i]; j){number[k] temp[i][j];k;}order[i] 0;}n * 10;k 0;m;}}public static void main(String[] args){int[]data {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};RadixSort.sort(data, 3);for(inti 0; i data.length; i){System.out.print(data[i] );}}
}三、性能算法时间、空间复杂度、稳定性分析 基数排序的时间复杂度是O(2*k*n)其中n是排序元素个数k是数字位数空间复杂度采用数组是O(n*d)采用链表是O(dn)d是进制关键字的取值范围是稳定的排序算法。
