如何实现基数排序算法？

基数排序(Radix Sort)是一种非比较的整数排序算法。它通过从最低位开始,逐个位数排序,从而达到整体排序的效果。

我们可以实现基数排序算法如下:

public void radixSort(int[] nums) {
    // 1. 找到数组中的最大数,确定排序的趟数
    int maxVal = Integer.MIN_VALUE;
    for (int num : nums) maxVal = Math.max(maxVal, num);
    int maxDigit = 0;
    while ((maxVal /= 10) != 0) maxDigit++;

    // 2. 设立10个桶,用于存储每个桶中的数字
    List<List<Integer>> bucket = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        bucket.add(new ArrayList<>());
    }

    // 3. 进行maxDigit次排序
    for (int i = 0, radix = 1; i < maxDigit; i++, radix *= 10) {
        // 4. 将数据分到对应的桶中
        for (int num : nums) {
            int numLast = (num / radix) % 10;
            bucket.get(numLast).add(num);
        }

        // 5. 从桶中取出数据,放回nums数组
        int index = 0;
        for (int j = 0; j < 10; j++) {
            for (int num : bucket.get(j)) {
                nums[index++] = num; 
            }
            bucket.get(j).clear();
        }
    } 
}

算法流程:

1. 找到最大数,确定排序的趟数。
2. 设立10个桶,用于存储每个位的值。
3. 进行maxDigit次排序,每次按一个位数排序。
4. 将数据放入对应桶,取出末位的值确定桶号。
5. 从桶中取出数据,放回原数组,清空桶。
6. 重复步骤4和5,完成一趟排序。
7. 重复步骤3、4、5和6,直到maxDigit趟排序完成。

时间复杂度O(kn),k为数组最大值的位数,空间复杂度O(n)。

所以,基数排序的关键是:

1. 找到最大数确定排序趟数。
2. 设立10个桶,用于暂存每个位数的值。
3. 按位数进行排序,每次取出末位的值放入对应桶。
4. 从桶中取出数据后清空桶。
5. 重复步骤3和4,直到所有位数排序完成。