11、数据结构与算法 - 实战：排序算法之基数排序

1、基本思想

把待排序序列的数值统一为同样的数位长度，数位较短的数字在前面补零。然后从最低位开始，依此进行依此排序。这样从最低位排序一直到最高位排序完成后，数列就变成一个有序序列。
基数排序属于分配式排序，又称桶子法。

2、图解

假设存在10个桶，分别为0-9号桶。

假设待排序序列为：{64，8，216，512，27，729，000，001，343，125}
首先把数值统一为同样的长度：{064，008，216，512，027，729，000，001，343，125}
然后从最低位开始，依此进行依此排序。
第一轮，遍历序列，依次把数值放置到和个位数相同的编号的桶当中。

然后按照桶编号依次拿出数字：{000，001，512，343，064，125，216，027，008，729}
第二轮，遍历第一轮结束的序列，依次把数值放置到和十位数相同的编号的桶当中。

然后按照桶的编号依次拿出数字：{000，001，008，512，216，125，027，729，343，064}
第三轮，遍历第二轮结束的序列，依次把数值放置到和百位数相同的编号的桶当中。

然后按照桶的编号依次拿出数字：{000，001，008，027，064，125，216，343，512，729}。
最大数字对应字符串长度位3，所以执行3轮就排序好了。

3、代码实现

package cn.klb.datastructures.sort;

/**
 * @author DDKK.COM 弟弟快看，程序员编程资料站
 * @Description: 实现数组的基数排序（桶子法）
 * @Date: Create in 2023/4/5 15:06
 * @Modified By:
 */
public class Radix {
   
     

    public static void sort(int[] arr) {
   
     
        // 找到待排序序列最大的数字
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
   
     
            if (max < arr[i]) {
   
     
                max = arr[i];
            }
        }

        // 获取最大数字的对应字符串长度
        int maxLength = ("" + max).length();

        // 定义一个二维数组代表所有桶
        // 比如：bucket[0] 表示0号桶
        int[][] bucket = new int[10][arr.length];

        // 定义一个一维数组保存每个桶元素的数量
        // 比如：elementNums[2] == 3 表示2号桶有3个元素
        int[] elementNums = new int[10];

        // 桶的序号 0~9
        int no = 0;

        // 元素从桶里放回数组时用到
        int index = 0;

        // i == {0,1,2,...,maxLength} 分别表示个、十、百...
        for (int i = 0; i < maxLength; i++) {
   
     
            // arr数组每个元素放到指定的桶里
            for (int j = 0; j < arr.length; j++) {
   
     
                no = (int) (arr[j] / Math.pow(10, i) % 10);
                bucket[no][elementNums[no]++] = arr[j];
            }
            // 每个桶里的元素按顺序覆盖回原数组
            for (int k = 0; k < 10; k++) {
   
     
                for (int count = 0; count < elementNums[k]; count++) {
   
     
                    arr[index++] = bucket[k][count];
                }
                elementNums[k] = 0; // 放好了存量就为0
            }
            // 执行完一轮后，执行清零操作
            index = 0;
        }
    }
}

4、时间复杂度

代码中的基数排序不能排序负数，若要排序负数，得进行附加操作，但是原理是不变的。基数排序的一个应用是将字符串排序。
一般来说，在第k轮后，元素按第k低位有序，所以运行结束后所有元素就完全有序了。运行时间是O(p(n+b))，其中p是轮数，n是待排序元素个数，b是桶的个数。

5、稳定性

元素装入桶的顺序和从桶里倒出来的顺序是不变的，因此，相同元素的前后顺序不会发生改变，因此基数排序是稳定的。

6、测试

package cn.klb.test.datastructurestest;

import cn.klb.datastructures.sort.*;
import org.junit.Test;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author DDKK.COM 弟弟快看，程序员编程资料站
 * @Description: 排序测试
 * @Date: Create in 2023/4/3 21:32
 * @Modified By:
 */
public class SotrTest {
   
     
    @Test
    public void testRadix(){
   
     
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
   
     
            arr[i] = (int) (Math.random() * 80000000);
        }
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        Date date1 = new Date();
        System.out.println("-----" + sdf.format(date1) + "-----");
        //System.out.println(Arrays.toString(arr));

        Radix.sort(arr);

        Date date2 = new Date();
        System.out.println("-----" + sdf.format(date2) + "-----");
        //System.out.println(Arrays.toString(arr));
        // 800万的随机数据进行基数排序，我的电脑花了大约2秒（测不了8000万，内存炸了）
    }
}