基数排序

蔚落 2022-06-15 06:11 220阅读 0赞

基数排序(Radix sort)是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。比较官方地说，基数排序是一种基于多关键字的排序。

基数排序具体过程如下：  
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。  
然后，从最低位开始，依次进行一次排序。这个排序并非比较大小，而是将对应的数字放置在其对应的桶中。即个位数字是0的数字放置在索引为0的桶，以此类推。这个过程称为“分配过程”。  
个位完成这个操作以后，然后依次从桶中取出数字形成新的序列。这个过程称为“收集过程”。  
然后，再从十位数字开始进行同样的操作，直到最高位。  
这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

下面给出图示，帮助理解基数排序的过程。

![基数排序][SouthEast]

下面给出示例代码（Java版，适用于正整数排序）

/** * @param number 给定一个数字 * @param order 指定要获取的位数，取值应该大于0（个位用1表示，十位用2表示，以此类推） * @return 返回指定位置上的数字，合理的返回结果是0~9共十种可能的结果 */
    public static int digit(int number, int order) {
        int digit = number;
        while (--order > 0) digit /= 10;
        return digit % 10;
    }
    
    /** * 返回给定数字的位数 */
    public static int maxOrder(int number) {
        int order = 1;
        while ((number /= 10) != 0) order++;
        return order;
    }
    
    public static void radixSort(int[] numbers) {
        int radix = 10;
        int size = numbers.length;
        int[][] bucket = new int[radix][size];  // 桶数组，radix为桶的个数，size为桶的大小
        int[] counter = new int[radix];  // 记录每个桶中保存的数据个数
    
        int maxNum = numbers[0];
        for (int num: numbers)
            if (num > maxNum) maxNum = num;
        int maxOrder = maxOrder(maxNum);  // 比较序列中最大数的位数
    
        // 基数排序分为分配过程和收集过程两大步
        for (int i = 1; i <= maxOrder; i++) {
            // 分配过程（数据序列装入桶中）
            for (int j = 0; j < size; j++) {
                int row = digit(numbers[j], i);
                int col = counter[row]++;
                bucket[row][col] = numbers[j];
            }
            // 收集过程（从桶中取出数据）
            int j = 0;
            for (int r = 0; r < radix; r++) {
                for (int c = 0; c < counter[r]; c++)
                    numbers[j++] = bucket[r][c];
                counter[r] = 0;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] numbers = {
       73, 22, 93, 43, 55, 14, 28, 9};
        radixSort(numbers);
        System.out.println(Arrays.toString(numbers));
    }

[SouthEast]: /images/20220615/55c38c7882314cf9aa993ace2578e001.png