龙岗网站制作市场,北京搜索关键词优化,手机网站开发c 教程,网站建设服务方案ppt一、基数排序
#xff08;1#xff09;基数排序的简介 基数排序不同于其他的排序算法#xff0c;它不是基于比较的算法。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。它是一种稳定的排序算法。 通常用于对数的排序选择的是最低位优先法#xff…一、基数排序
1基数排序的简介 基数排序不同于其他的排序算法它不是基于比较的算法。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。它是一种稳定的排序算法。 通常用于对数的排序选择的是最低位优先法即先对最次位关键字进行排序再对高一位的关键字进行排序以此类推。
2基数排序的思想 多关键字排序中有两种方法最高位优先法(MSD)和最低位优先法LSD。
元数据为k1k2k3..kn
A、最高位优先(Most Significant Digit first)法先按k1排序分组同一k1组中记录关键码k1相等对各k1组按k2关键字排序分成k2子组同一k2子组中记录关键码k2相等再对各k2子组按k3排序分成k3子组重复这样步骤直至子组按kn排序分成kn子组。再将各组连接起来便得到一个有序序列。B、最低位优先(Least Significant Digit first)法先从kn开始排序再对kn-1进行排序依次重复直到对k1排序后便得到一个有序序列。二、最高位优先(Most Significant Digit first)法 public static void radixSort(int[] data) {//位数if(data.length2)return;int place getPlace(data);//位数大于0if (place 0) {sortUnit(data, 0, data.length, 1, place);}}/*** MSD算法* param data* param s 起始位置* param e 截止位置是最后一个数据的索引1* param curPlace 当前所在数据位置从左边开始起始值为1* param totalPlace 最大数据的位数*/private static void sortUnit(int[] data, int s, int e, int curPlace, int totalPlace) {//十个桶int[] counts new int[10];int p;//计算各个桶的数据个数for (int i s; i e; i) {p getDigit(data[i], curPlace,totalPlace);//获取数据当前位的值counts[p];}//计算各个桶的数据右边索引界限for (int i 1; i counts.length; i) {counts[i] counts[i] counts[i - 1];}//创建数组将所有桶都存放在这个数组里面int[] bucket new int[e - s];int dat;//从右往左扫描保证了算法的稳定性for (int i e-1; i s; i--) {dat data[i];p getDigit(dat, curPlace,totalPlace); //获取数据当前位的值counts[p]--; //找到属于桶的最后一个位置bucket[counts[p]] dat;}//将数据回填回dataSystem.arraycopy(bucket, 0, data, s, bucket.length);int start;int end;//根据Ki分组的每个桶都去创建根据Ki1分组的子桶for (int i 0; i counts.length; i) {start s counts[i];//左边界//右边界if (i 1 counts.length) {end s counts[i 1];} else {end e;}//桶里数据大于2基数位置未到Kn,继续分子桶if (end - start 1 curPlace totalPlace) {sortUnit(data, start, end, curPlace 1, totalPlace);}}} 其他方法调用 /*** 获取第curPlace位的数值* param d* param curPlace* return */private static int getDigit(int d, int curPlace,int totalPlace) {dd/((int) Math.pow(10, totalPlace-curPlace));return d % 10;}/*** 获取元数据的位数** param data* return*/private static int getPlace(int[] data) {//null值或者长度为0if (data null || data.length 1) {return 0;}if(data.length1){return String.format(%d, data[0]).length();}int[] mx getMaxAndMin(data);//最大值的绝对值int max Math.abs(mx[0]);//最小值的绝对值int min Math.abs(mx[1]);//最大值的绝对值的十进制位数max String.format(%d, max).length();//最小值的绝对值的十进制位数min String.format(%d, min).length();return Math.max(max, min);//最大位数}/*** 获取最大和最小值* param data* return */public static int[] getMaxAndMin(int[] data) {int[] mx {Integer.MIN_VALUE, Integer.MAX_VALUE};for (int d : data) {if (mx[0] d) {mx[0] d;} else if (mx[1] d) {mx[1] d;} }return mx;} View Code三、最低位优先(Least Significant Digit first)法 public static void radixSort(int[] data) {//位数if (data.length 2) {return;}int place getPlace(data);//位数大于0for (int i 0; i place; i) {sortUnit(data, i);}}/*** LSD算法** param data* param curPlace 当前所在数据位置从右边开始起始值为0*/private static void sortUnit(int[] data, int curPlace) {//十个桶int[] counts new int[10];int p;//计算各个桶的数据个数for (int i 0; i data.length; i) {p getDigit(data[i], curPlace);//获取数据当前位的值counts[p];}//计算各个桶的数据右边索引界限for (int i 1; i counts.length; i) {counts[i] counts[i] counts[i - 1];}//创建数组将所有桶都存放在这个数组里面int[] bucket new int[data.length];int dat;//从右往左扫描保证了算法的稳定性for (int i data.length - 1; i 0; i--) {dat data[i];p getDigit(dat, curPlace); //获取数据当前位的值counts[p]--; //找到属于桶的最后一个位置bucket[counts[p]] dat;}//将数据回填回dataSystem.arraycopy(bucket, 0, data, 0, bucket.length);} 其他方法 /*** 获取第curPlace位的数值** param d* param curPlace 从0开始* return*/private static int getDigit(int d, int curPlace) {d d / ((int) Math.pow(10, curPlace));return d % 10;}/*** 获取元数据的位数** param data* return*/private static int getPlace(int[] data) {//null值或者长度为0if (data null || data.length 1) {return 0;}if (data.length 1) {return String.format(%d, data[0]).length();}int[] mx getMaxAndMin(data);//最大值的绝对值int max Math.abs(mx[0]);//最小值的绝对值int min Math.abs(mx[1]);//最大值的绝对值的十进制位数max String.format(%d, max).length();//最小值的绝对值的十进制位数min String.format(%d, min).length();return Math.max(max, min);//最大位数}/*** 获取最大和最小值** param data* return*/public static int[] getMaxAndMin(int[] data) {int[] mx {Integer.MIN_VALUE, Integer.MAX_VALUE};for (int d : data) {if (mx[0] d) {mx[0] d;} else if (mx[1] d) {mx[1] d;}}return mx;} View Code四、算法的复杂度
基数排序的算法复杂度最好时间复杂度、最坏时间复杂度和平均时间复杂度都为O(d(nr))空间复杂度为O(nr)是稳定的算法。
