基数排序算法

2022年12月30日 · 282 字 · 2 分钟

基数排序又叫桶排序，是一种时间复杂度为$O(n)$的排序算法，但是相比于其他排序算法有$O(n)$的空间复杂度。

思路

基数排序的核心思路如下：

  1. 准备0~9的10个桶，根据数字当前比较位的值来决定放入哪个桶。如当前比较个位，则数字13应该放入索引为3的桶中；当前比较百位，则123应该放入索引为1的桶中。
  2. 当所有数字全部放入桶之后，遍历0~9这10个桶，然后依次将数字保存到待排序数组，因为桶是有序的，所以本轮放回去的数字是有序的。
  3. 当前比较的位数左移，比如本轮比较个位，下一轮应该比较百位。
  4. 重复步骤1~3。

举例

现在我们来看一个实际例子。

待排序数字：717, 328, 803, 422, 586, 944, 557, 308, 496, 624

第1轮比较个位

直接按照个位放入桶中。

0123456789
422803624586717328
496557308

按照从左到右，从上到下的原则将数字归位：422,803,624,586,496,717,557,328,308

第2轮比较十位

0123456789
803717422557586496
308624
328

按照从左到右，从上到下的原则将数字归位：803,308,717,422,624,328,557,586,496

第3轮比较百位

0123456789
308422557624717803
328496586

按照从左到右，从上到下的原则将数字归位：308,328,422,496,557,586,624,717,803

可以发现，比较的轮次由数组中最大的数字决定，以上面的例子来说，如果还存在一个1234数字，那么需要比较4轮才可以完成排序。

代码实现


class RadixSort {

    // 基数排序
    public void sort(int[] nums) {
        if (nums.length <= 1) {
            return;
        }
        var max = Arrays.stream(nums).max().getAsInt();
        // 当前处理位数
        var exp = 1;
        // 桶
        var bucket = new int[10][nums.length];
        // 记录每个桶有几个数字
        var bucketCount = new int[10];
        while (max >= exp) {
            // 求得每个数字当前位数的值
            for (var num : nums) {
                // 求得当前位余数
                var bitNumber = (num / exp) % 10;
                // 放入桶, index是桶的index，在同一个桶的数字需要index来标识位置
                var index = bucketCount[bitNumber];
                bucket[bitNumber][index] = num;
                // 桶内数量+1
                bucketCount[bitNumber]++;
            }
            // 桶内数字归位
            int k = 0; // 已归位的数字下标
            for (var i = 0; i < 10; i++) {
                if (bucketCount[i] > 0) { // 当前桶有数字
                    for (int j = 0; j < bucketCount[i]; j++) { // 遍历同一个桶的数字
                        nums[k] = bucket[i][j];
                        k++;
                    }
                }
                // 桶数字清空
                bucketCount[i] = 0;
            }
            // 位数左移
            exp *= 10;
        }

        max = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            var gap = nums[i] - nums[i - 1];
            if (gap > max) {
                max = gap;
            }
        }
    }

    public static void main(String[] args) {
        var sort = new RadixSort();
        var list = new int[]{422, 803, 624, 586, 496, 717, 557, 328, 308};
        sort.sort(list);
        System.out.println(Arrays.toString(list));
    }
}

时间复杂度: $O(n)$ ，严格来说是$O(log(n))$。$n$是待排序数组长度，在数据量小的情况下，最外层的while循环遍历次数可以认为是常数，内部嵌套的for循环次数为数组长度$n$，因此时间复杂度为$O(n)$；在数据量大的情况下，最外层的while循环次数为$O(log(n))$，内部嵌套的for循环次数依旧是$n$，因此时间复杂度为$O(nlog(n))$。

空间复杂度：$O(n)$。$n$是待排序数组长度，$bucket$的大小为$10*n$，$bucketCount$大小为$n$，因此总体空间复杂度为$O(n)$。

qrcode