基数排序算法原理及实现的详细解析（Java、Go、Python、JS、C）

基数排序（Radix Sort）是一种非比较排序算法，它根据数字的每一位来进行排序。这种算法适用于整数排序，特别是当整数的位数固定且范围较小的时候，效率非常高。

原理： 基数排序的基本思想是从最低有效位开始，依次按照每一位数字对数据进行排序。通过多次的“收集”和“分配”操作，最终使整个序列有序。

实现步骤：

1. 确定排序的基数（通常是 10，因为是十进制数）和要排序的数字的最大位数。
2. 从最低位开始，对每一位进行“收集”和“分配”操作。
3. 重复步骤 2，直到最高位排序完成。

以下是用多种编程语言实现基数排序的示例代码：

Java 实现：

public class RadixSort {
    public static void radixSort(int[] arr, int radix, int width) {
        for (int i = 0; i < width; i++) {
            int[] count = new int[radix];
            int[] temp = new int[arr.length];

            for (int j = 0; j < arr.length; j++) {
                int digit = (arr[j] / (int) Math.pow(radix, i)) % radix;
                count[digit]++;
            }

            for (int j = 1; j < radix; j++) {
                count[j] += count[j - 1];
            }

            for (int j = arr.length - 1; j >= 0; j--) {
                int digit = (arr[j] / (int) Math.pow(radix, i)) % radix;
                temp[count[digit] - 1] = arr[j];
                count[digit]--;
            }

            System.arraycopy(temp, 0, arr, 0, arr.length);
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr, 10, 3);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Go 实现：

func radixSort(arr []int, maxDigit int) {
    bucket := make([][]int, 10)
    for digit := 0; digit < maxDigit; digit++ {
        for _, num := range arr {
            bucket[(num/(10^digit))%10] = append(bucket[(num/(10^digit))%10], num)
        }
        index := 0
        for i, b := range bucket {
            for _, num := range b {
                arr[index] = num
                index++
            }
            bucket[i] = nil
        }
    }
}

Python 实现：

def radix_sort(arr):
    max_value = max(arr)
    exp = 1
    while max_value / exp > 0:
        bucket = [[] for _ in range(10)]
        for num in arr:
            bucket[(num // exp) % 10].append(num)
        arr = [item for sublist in bucket for item in sublist]
        exp *= 10

JS 实现：

function radixSort(arr, maxDigit) {
    let bucket = new Array(10).fill().map(() => []);
    for (let digit = 0; digit < maxDigit; digit++) {
        for (let num of arr) {
            bucket[Math.floor((num / Math.pow(10, digit)) % 10)].push(num);
        }
        arr = [].concat(...bucket);
        bucket = new Array(10).fill().map(() => []);
    }
}

C 实现：

void radixSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];

    for (int exp = 1; max / exp > 0; exp *= 10)
        radixSort(arr, n, exp);
}

基数排序在特定情况下具有出色的性能，但它也有一些限制，例如对于位数不固定或范围较大的整数排序可能不太适用。在实际应用中，需要根据具体情况选择合适的排序算法。