基數排序的簡單理解

• 2022 年 7 月 2 日
• 筆記
• 排序, 數據結構與演算法, 演算法

詳細描述

從基數排序的描述可以看得出，其適用於整數，但是，整數也可以表達字元串（比如名字或時間）和特定格式的浮點數，因此基數排序並不只是適用於整數。

基數排序詳細的執行步驟如下：

1. 首先準備 10 個桶，分別用於存儲所在位數為 0 ~ 9 的數；
2. 提取出序列中元素的個位，將該元素移動到對應個位所屬的桶內；
3. 重複執行第 2 步，從個位、十位、百位直到最大元素的最大位數，沒有所在位時賦為 0；
4. 執行完第 3 步，組合每個桶內的元素成有序序列。

演算法圖解

問題解疑

基數排序的複雜度是多少？

基數排序的時間複雜度和待排序序列的最大位數有關係，由於需要對每一個位數遍歷一次序列，基數排序的時間複雜度是 \(O(n \times k)\)，其中 k 是最大位數。

基數排序的空間複雜度是 \(O(n+k)\)，其中 k 是桶的數量。

基數排序和快速排序哪個效率更好？

基數排序是一種空間換時間的非比較類排序演算法，其時間複雜度是 \(O(n \times k)\)；快速排序是一種常規的比較類排序演算法，其時間複雜度是 \(O(n\log_2n)\)。

從時間複雜度上看，主要在於其係數的比較。通常是，待排序序列的最大位數越大， 基數排序的效率就越低，這時選擇快速排序則更優；如果數據量非常大的時候，則基數排序比較佔優。

程式碼實現

排序抽象類

package cn.fatedeity.algorithm.sort;

/**
 * 排序抽象類
 */
public abstract class Sort {
    protected void swap(int[] numbers, int src, int target) {
        int temp = numbers[src];
        numbers[src] = numbers[target];
        numbers[target] = temp;
    }

    public abstract int[] sort(int[] numbers);
}

計數排序類

package cn.fatedeity.algorithm.sort;

import java.util.List;
import java.util.ArrayList;

/**
 * 計數排序演算法類
 */
public class RadixSort extends Sort {
    public int[] sort(int[] numbers) {
        if (numbers.length == 0) {
            return numbers;
        }

        int min = numbers[0], max = numbers[0];
        for (int number : numbers) {
            if (number < min) {
                min = number;
            }
            if (number > max) {
                max = number;
            }
        }
        int k = String.valueOf(Math.max(Math.abs(min), Math.abs(max))).length();

        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 19; i++) {
            buckets.add(new ArrayList<>());
        }

        int x = 1;
        while (x <= k) {
            for (int number : numbers) {
                int index = (number / (int) Math.pow(10, x - 1)) % 10;
                List<Integer> bucket = buckets.get(index + 9);
                bucket.add(number);
            }

            int index = 0;
            for (int i = 0; i < buckets.size(); i++) {
                for (int number : buckets.get(i)) {
                    numbers[index++] = number;
                }
                buckets.set(i, new ArrayList<>());
            }

            x++;
        }

        return numbers;
    }
}