中国建设银行网站首页u盾登入,工商注册网上核名,网站关键词排名全掉了,国外做多媒体展览的网站大家好#xff0c;我是烤鸭#xff1a; 今天分享一下基础排序算法之基数排序。 1. 基数排序#xff1a; 原理#xff1a;基数排序#xff08;radix sort#xff09;属于“分配式排序”#xff08;distribution sort#xff09;#xff0c;又称“桶子法”#…大家好我是烤鸭 今天分享一下基础排序算法之基数排序。 1. 基数排序 原理基数排序radix sort属于“分配式排序”distribution sort又称“桶子法”bucket sort或bin sort。
将所有待比较数值正整数统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
思路
基数排序即一个数位一个数位地进行排序平常生活中我们经常使用的一种算法思想如要对一个日期进行排序日期中由年、月、日组成的对于这个问题我们经常使用的是先比较年份如果相同再比较月份如果还相同就比较日。
下面四个数进行排序123、312、245、531 个位 十位 百位 531 312 123 312 123 245 123 531 312 245 245 531
代码实现 /*** 基数排序* param d* param array* 时间复杂度 O的log2 N* 基数排序 运用二维数组来分别比较每一位个位、十位、百位…* 输入10个整数的数组*/private void radixSort(int d,int[] array){long nowTime System.nanoTime();int n1;//代表位数对应的数1,10,100000...int k0;//保存每一位排序后的结果用于下一位的排序输入int[][] bucketnew int[10][array.length];//排序桶用于保存每次排序后的结果这一位上排序结果相同的数字放在同一个桶里int[] numnew int[array.length];//用于保存每个桶里有多少个数字 ,最多为输入数组长度while(nd){for(int e:array) //将数组array里的每个数字放在相应的桶里{int digit(e/n)%10;bucket[digit][num[digit]]e;num[digit];}for(int i0;iarray.length;i)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果{if(num[i]!0)//这个桶里有数据从上到下遍历这个桶并将数据保存到原数组中{for(int j0;jnum[i];j){array[k]bucket[i][j];k;}}num[i]0;//将桶里计数器置0用于下一次位排序}n*10;k0;//将k置0用于下一轮保存位排序结果}System.out.println(基数排序花费时间(ms): ((System.nanoTime() - nowTime) / 1000000.0) ms);}
基数排序是稳定算法效率很高其复杂度为O(nlog(r)m)其中r为所采取的基数而m为堆数。但它只能用在整数的排序中且需要借助一定的辅助空间。
上面的代码适用有些局限在于对基数值选取
int [] x {25 ,11 ,22 ,34 ,15 ,44 ,76, 66, 100, 8 ,14, 20 ,2, 5 ,1 };
比如这个数组基数应该选3。附上一个选择基数值的方法。 /*** 获取基数排序中的基数* param array* return*/public int getRadixBasicNumber(int[] array){if(array null array.length 0) {return 0;}int max 0;//1获取最大的绝对值的数for(int i 0;iarray.length;i) {if(Math.abs(max)Math.abs(array[i])) {max array[i];}}int times 0;if(max0) max -max;//2求出最大的绝对值的数是10的times次幂。while(max 0) {max max/10;times ;}return times;} 耗时对比
10W 条随机 数据 运行如图 分别对比了基数排序直插排序希尔排序和快速排序。差距很明显。
50W 条随机 数据 运行如图 分别对比了基数排序直插排序希尔排序和快速排序。差距很明显。
100W 条随机 数据 运行如图 分别对比了基数排序直插排序希尔排序和快速排序。差距很明显。
总结
基数排序
优点效率高。
缺点占用内存大只能对正整数排序采用二维数组做桶时
最坏时间复杂度O(P(NB))。
平均时间复杂度为O(P(NB))。
其中P是排序的趟数N是要被排序元素的个数B是桶数。
各种排序方法比较 更多排序算法
冒泡排序 https://blog.csdn.net/Angry_Mills/article/details/81057900
插入排序 https://blog.csdn.net/Angry_Mills/article/details/81208700
快速排序 https://blog.csdn.net/Angry_Mills/article/details/83339390
