基数排序（Radix Sort）

基数排序是一种非比较类排序算法，适用于整数、字符串等可按位切分的元素。它通过逐位排序的方式，从低位到高位依次排序，最终获得有序结果，常采用LSD（Least Significant Digit）低位优先策略。

📌 算法原理解释

基数排序以每位数字作为关键字，采用稳定排序算法（如计数排序）对每一位进行排序，直到所有位都排完。

LSD（从低位到高位）流程如下：

1. 确定最大值的位数 d；
2. 按个位、十位、百位……排序 d 次；
3. 每次排序必须使用稳定排序保持顺序；
4. 得到最终有序数组。

例子：对 [170, 45, 75, 90, 802, 24, 2, 66] 排序：

• 第一次按个位：[170, 90, 802, 2, 24, 45, 75, 66]
• 第二次按十位：[802, 2, 24, 45, 66, 170, 75, 90]
• 第三次按百位：[2, 24, 45, 66, 75, 90, 170, 802]

💻 多语言代码实现

javascript

// 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

# 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

cpp

// 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

// 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
// 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

// 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
}

✅ 算法特点与总结

属性	描述
时间复杂度	O(nk)，k 为位数（例如最大为千位）
空间复杂度	O(n + k)
稳定性	✅ 稳定（使用稳定排序实现）
是否原地排序	❌ 否（需额外空间）
适用条件	非负整数或定长字符串排序

📌 提示：基数排序适合大量整数或定长字符串排序，不适合浮点数或需比较的对象排序。