您的位置 首页 java

Java排序算法——基数排序(Radix Sort)

基数排序

基数排序是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数;

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

Java 代码

以下代码方便复制

public class RadixSort {
 public static void main(String[] args) {
 int[] array = new int[]{0,53,63,38,71,25,22,11,95,38};
 sort(array);
 System.out.println(Arrays.toString(array));
 }
 public static int[] sort(int[] array) {
 if (array == null || array.length < 2){ return array;}
 int max = array[0];
 for (int i = 1; i < array.length; i++) {
 max = Math.max(max, array[i]);
 }
 //计算最大数的位数
 int maxDigit = 0;
 while (max != 0) {
 max /= 10;
 maxDigit++;
 }
 int mod = 10, div = 1;
 ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
 for (int i = 0; i < mod; i++){
 bucketList.add(new ArrayList<>());
 }
 for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
 for (int j = 0; j < array.length; j++) {
 int num = (array[j] % mod) / div;
 bucketList.get(num).add(array[j]);
 }
 int index = 0;
 for (int j = 0; j < bucketList.size(); j++) {
 for (int k = 0; k < bucketList.get(j).size(); k++) {
 array[index++] = bucketList.get(j).get(k);
 }
 bucketList.get(j).clear();
 }
 }
 return array;
 }
}
 

文章来源:智云一二三科技

文章标题:Java排序算法——基数排序(Radix Sort)

文章地址:https://www.zhihuclub.com/180854.shtml

关于作者: 智云科技

热门文章

网站地图