大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

小朋友学数据结构(10):基数排序

(一)基本思想

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

8.png

(二)代码实现

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) {
            digitCount++;
            max /= 10;
        }
        
        //二维数组list由10个一维数组list1组成;
        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