基数排序

基数排序

时间复杂度 O(kn)，k 为要排序的数字的最大长度

例如对 342、58、576、356 进行排序

不足的位数看做是 0
342 058 576 356
第一步
按照个位将数字依次放到不同的位置
0: 
1: 
2: 342
3: 
4: 
5: 
6: 576, 356
7: 
8: 058
9: 

把上边的数字依次拿出来，组成新的序列 342 576 356 058，然后按十位继续放到不同的位置。
0: 
1: 
2: 
3: 
4: 342
5: 356 058
6: 
7: 576
8: 
9: 

把上边的数字依次拿出来，组成新的序列 342 356 058 576，然后按百位继续装到不同的位置。
0: 058
1: 
2: 
3: 342 356
4: 
5: 576 
6: 
7: 
8: 
9: 

把数字依次拿出来，最终结果就是 58 342 356 576

JAVA 实现：

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

public class BaseSort {
    public int[] baseSort(int[] nums) {
        long exp = 1;
        // 找出数组最大值
        int max = Arrays.stream(nums).max().getAsInt();
        // 二维数组，存储当前数位是 0-9 的一维数组
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        // 创建 10 个空数组
        for (int i = 0; i < 10; i++) {
            lists.add(new ArrayList<Integer>());
        }
        // 从个位开始，进行循环
        while (max >= exp) {
            // 清空数组
            for (ArrayList<Integer> list : lists) {
                list.clear();
            }
            // 计算当前位的数组，加入到对应的数组
            for (int num : nums) {
                int x = (int) ((num / exp) % 10);
                lists.get(x).add(num);
            }
            // 将本次循环结果放入 nums
            int i = 0;
            for (ArrayList<Integer> list : lists) {
                for (Integer integer : list) {
                    nums[i++] = integer;
                }
            }
            exp *= 10;
        }
//        String s = Arrays.toString(nums);
//        System.out.println(s);
        return nums;
    }
}