小朋友学数据结构（10）：基数排序

（一）基本思想

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位（即个位数）开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

（二）代码实现

package com.z;

import java.util.ArrayList;
import java.util.Arrays;

public class Sort {

    public static void radixSort(int[] array) {
        //获取最大的数
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        
        int digitCount = 0;
        //判断位数，位数即排序的趟数
        while (max > 0) {
            max /= 10;
            digitCount++;
        }
        
        //建立10个数组;
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            ArrayList<Integer> list1 = new ArrayList<>();
            list.add(list1);
        }

        //进行digitCount次分配和收集;
        for (int i = 0; i < digitCount; i++) {
            //分配数组元素;
            for (int num : array) {
                //得到数字的第i+1位数;
                int x = num % (int)Math.pow(10, i + 1) / (int)Math.pow(10, i);
                ArrayList<Integer> list2 = list.get(x);
                list2.add(num);
                list.set(x, list2);
            }
            int index = 0;
            //重新排列数组中的元素
            for (int k = 0; k < 10; k++) {
                while (list.get(k).size() > 0) {
                    ArrayList<Integer> list3 = list.get(k);
                    array[index] = list3.get(0);
                    list3.remove(0);
                    index++;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {135, 242, 192, 93, 345, 11, 24, 19};
        System.out.println("Original array: " + Arrays.toString(arr));  
        radixSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));   
    }
}

运行结果：

Original array: [135, 242, 192, 93, 345, 11, 24, 19]
Sorted array: [11, 19, 24, 93, 135, 192, 242, 345]

TopCoder & Codeforces & AtCoder交流QQ群：648202993
更多内容请关注微信公众号

wechat_public_header.jpg