JAVA排序算法之基数排序

JAVA初识之基数排序

基数排序

理解:

将要排序的数放入一个一维数组中 如num数组
之后定义一个二维数组,排序过程中使用,二维数组,即一维数组中,每一个空间再放入一个一维数组

如一串数值如下所示
73 22 93 43 55 14 28 65 39 81
二维数组分别为0-9行,分别为
0
1 
2 
3  
4  
5  
6  
7 
8  
9 
每一行分别代表整数中某一位上的数(个位,十分为,百分位,低位往高位),第一次循环比较个位上的数,所得结果放入二维数组中,如下所示:
0  
1  81
2  22
3  73 93 43
4  14 55 65
5
6
7
8  28
9  39
将这些数按顺序放入一维数组num数组中得到:
81 22 73 93 43 14 55 65 28 39

之后将二维数组中的数据全部清0,因为之前二维数组保存的是按个位上德数排序所得到的结果,再次循环,需要保存按十分位上的数排序所得到的结果,按十分位上德数排序所得结果为:
0  
1  14 
2  22 28
3  39
4  43
5  55
6  65
7  73
8  81
9  93

将这次排序所得结果依次放入num数组中得到:
14 22 28 39 43 55 65 73 81 93

这个时候整个数列已经排序完毕,如果排序对象有三位数以上,则持续进行以上的排序,直至最高位数为止

代码实现

    //初始数组
    int[] a = {23,100,86,452,314,9,50,42,66,123,645}; 
    /*10代表0-9,即某一位(个位/十分位/百分位)上的数字;a.length代表每一行最多可能出现的个数,如上述数组中的数据如果全为15,即相同的数,则某一行全部放满数据*/
    int[][] num =new int[10][a.length];
    /*key数组初始值都是0,用来表示某一个数字出现的次数,如0出现一次,则key[0]++;0再出现1次,则key[0]++,结果为2,如3出现1次,则key[3]++,结果为1,依次类推*/
    int[] key = new int[10];  //初值都是0,key[0]代表这个数是0,key[0]++就是1,代表这个数也就是0出现过一次,则key[0]=1
    int i = 1;//为1时,代表个位,为2时,代表10位,为3时,代表百分位,类推
    int m = 3;//明确要排序的数组中最大的数是几位数,程序员自己确认最大位数,也可编程实现
    int h = 1;//作为被除数取整,第一次除以1,第二次循环h扩大10倍,即数组中的数除以10取整,先取整,再取余,以便得到个位,十分位,百分位上的数
    int x = 0;//a数组的下标,将二维数组中德数据放入一维数组中时使用
    while(i <= m) {
        for(int k = 0;k < a.length;k++) {
            int temp = ((a[k] / h )% 10);//temp为某一位上德数,分别为个位\十位\百位上的数,先取整,后取余
            num[temp][key[temp]] = a[k];//若temp=2,则a[k]放入num[2][0]中,随后key[temp]中的值要增加1
            key[temp] = key[temp] + 1;
            //num[temp]这一行上的第一个位置已放入数,下标加一,右移一位,以便放入下一个(个位/十分位/百分位..)相同的数
            }
        for(int k = 0;k < 10;k ++) { //第一轮循环结束,得到按个位排序的二维数组,将二维数组中德数据放入一维数组中
            if(key[k] != 0) {  //判断这一行中是否放入了数据,每当放入数据时,key[k]的值就会加1
                for(int f = 0;f < key[k];f++) {
                    a[x] = num[k][f];   //有数据,就放入一维数组中,即更新原来的一维数组
                    x++;   //下标加1
                }
                key[k] = 0;  //二维数组的这一个空间清0,以便第二次循环,即比较十分位上的数字时,再次放入数据
            }
        }
        h = h * 10;  //乘以10,即扩大10倍,a[k] / h % 10就得到十分位上的数字,再次循环,可得到百分位上的数字
        x = 0;//一维数组下标清零,以便再次循环时,更新一维数组时,下标从0开始
        i ++; //代表个位,加1,代表十分位,再加1,代表百分位,用于控制while循环的结束
    }
    for(int l = 0;l < a.length;l++) { //==打印数组==
        System.out.print(a[l] + " ");
    }

结语:

以上代码皆是个人理解,放入eclipse软件中,定义一个main函数后,可直接使用.