基數排序是一種非比較型的排序演算法，其核心思想是分配與收集。對於每個數字，從最低有效位開始，根據該位的數值將其分配到對應的桶中，然後按照桶的順序收集回來。重複這一過程，直到所有的位都被考慮過。

基數排序法簡介
基數排序的基本思想是多次使用穩定的排序演算法（例如：計數排序或桶排序）來排序整數的每一位數。當所有位都排序完畢後，整個數列就會被完全排序。

C++實現
以下是使用C++實現的基數排序法：

#include <iostream>
#include <algorithm>

void countingSort(int arr[], int n, int position) {
    const int maxNumber = 10;
    int output[n], count[maxNumber] = {0};

    // 計算該位數的出現次數
    for (int i = 0; i < n; i++) {
        count[(arr[i] / position) % 10]++;
    }

    // 累計次數
    for (int i = 1; i < maxNumber; i++) {
        count[i] += count[i - 1];
    }

    // 根據該位數值重構排序後的數列
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / position) % 10] - 1] = arr[i];
        count[(arr[i] / position) % 10]--;
    }

    // 複製回原數列
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

void radixSort(int arr[], int n) {
    int maxElement = *std::max_element(arr, arr + n);  // 找到最大值
    for (int position = 1; maxElement / position > 0; position *= 10) {
        countingSort(arr, n, position);
    }
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    radixSort(arr, n);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

性能考慮
基數排序的時間複雜度是 ，其中 是要排序的數據量，而 是數據中的位數。因為基數排序是一種非比較型排序，所以當 不是很大時，基數排序會比許多比較型排序（如快速排序）更快。

在AI中的應用
基數排序是一種專為整數設計的高效排序演算法。在某些AI和機器學習的應用中，可能會有大量的整數數據需要排序。基數排序在這些場景中可以提供高效的解決方案，特別是當數據的位數相對較小時。