用java实现基数排序

用java实现基数排序

一、什么是奇数排序

假设有一串数字，12,12, 10, 45, 32, 56, 677, 93, 22, 22, 30。

先准备一个盒子，里面有0到9的数据。

第一步、根据个位的数字将按照顺序排列到盒子里：10, 30, 12, 12, 32, 22, 22, 93, 45, 56, 677

第二步、根据十位的数字将按照顺序排列到盒子里：10, 12, 12, 22, 22, 30, 32, 45, 56, 677, 93

第三步、根据百位的的数字按照顺序排列到盒子里：10, 12, 12, 22, 22, 30, 32, 45, 56, 93, 677

最后得出结果就是排好的顺序了。

二、基数排序实现的步骤

1、判断这一串数字中最大数的位数。

2、因为每次排序只有位数不一样，所以排序的代码基本相同，用一个循环实现排序。

3、打印排序好的数。

三、实现代码如下

import java.util.Arrays;

public class Paix {
    public static void main(String[] args) {
        int[] arr = new int[]{12,12, 10, 45, 32, 56, 677, 93, 22, 22, 30};  //定义一个数组
        int max = 0;
        for (int k : arr) {       //得到这些数里面最大数的长度
            if ((k + "").length() > max) {
                max = (k + "").length();
            }
        }

        for (int x = 0; x < max; x++) {
            int[][] temp = new int[10][arr.length];
            int[] tempcount = new int[10];
            int n = (int) Math.pow(10, x);
            for (int k : arr) {
                int number = (((k / n) % 10));
                temp[number][tempcount[number]] = k;   //temp[number]默认值为0
                tempcount[number]++;
            }

            int result = 0;
            for (int i = 0; i < tempcount.length; i++) {
                for (int j = 0; j < tempcount[i]; j++) {
                    arr[result] = temp[i][j];
                    result++;
                }
            }

            System.out.println(Arrays.toString(arr));
        }
    }
}

结果：

 

 

四、部分代码讲解

1、(k + "").length()

这个表示的意思是arr[k] 的长度。

2、int n = (int) Math.pow(10, x);

这个表示10的x次方

3、int[] tempcount = new int[10];

这边用一个数组来当做二维数组的列。初始值为0；

五、此方法的不足

此方法每一次循环都会生成一个一维数组的一个二维数组。如果需要判断的数中有位数很大的数，将会产生很多个数组。