基数排序（Radix Sort）

// JavaScript 基数排序（LSD）
function radixSort(arr) {
  const max = Math.max(...arr);
  let digit = 1;

  while (Math.floor(max / digit) > 0) {
    const buckets = Array.from({ length: 10 }, () => []);
    for (let num of arr) {
      const digitValue = Math.floor(num / digit) % 10;
      buckets[digitValue].push(num);
    }
    arr = [].concat(...buckets);
    digit *= 10;
  }

  return arr;
}

# Python 基数排序（LSD）
def radix_sort(arr):
    if not arr: return []
    max_val = max(arr)
    exp = 1

    while max_val // exp > 0:
        count = [0] * 10
        output = [0] * len(arr)

        for num in arr:
            index = (num // exp) % 10
            count[index] += 1

        for i in range(1, 10):
            count[i] += count[i - 1]

        for i in reversed(range(len(arr))):
            index = (arr[i] // exp) % 10
            output[count[index] - 1] = arr[i]
            count[index] -= 1

        arr = output
        exp *= 10
    return arr

// C++ 基数排序（LSD）
#include <vector>
using namespace std;

void countingSort(vector<int>& arr, int exp) {
    vector<int> output(arr.size());
    int count[10] = {0};

    for (int num : arr)
        count[(num / exp) % 10]++;
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (int i = arr.size() - 1; i >= 0; i--) {
        int index = (arr[i] / exp) % 10;
        output[--count[index]] = arr[i];
    }
    arr = output;
}

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSort(arr, exp);
}

// Java 基数排序（LSD）
import java.util.Arrays;

public class RadixSort {
    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().orElse(0);

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

    private static void countingSort(int[] arr, int exp) {
        int[] output = new int[arr.length];
        int[] count = new int[10];

        for (int num : arr)
            count[(num / exp) % 10]++;
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];
        for (int i = arr.length - 1; i >= 0; i--) {
            int index = (arr[i] / exp) % 10;
            output[--count[index]] = arr[i];
        }
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

<?php
// PHP 基数排序
function radixSort(array $arr): array {
    if (empty($arr)) return [];

    $max = max($arr);
    $exp = 1;

    while ((int)($max / $exp) > 0) {
        $buckets = array_fill(0, 10, []);
        foreach ($arr as $num) {
            $digit = (int)(($num / $exp) % 10);
            $buckets[$digit][] = $num;
        }
        $arr = array_merge(...$buckets);
        $exp *= 10;
    }

    return $arr;
}
?>

// Go 基数排序（LSD）
package main

func radixSort(arr []int) []int {
    if len(arr) == 0 {
        return arr
    }
    max := arr[0]
    for _, v := range arr {
        if v > max {
            max = v
        }
    }

    exp := 1
    for max/exp > 0 {
        count := make([]int, 10)
        output := make([]int, len(arr))

        for _, v := range arr {
            digit := (v / exp) % 10
            count[digit]++
        }

        for i := 1; i < 10; i++ {
            count[i] += count[i-1]
        }

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

        arr = output
        exp *= 10
    }

    return arr
}