# 基数排序（Radix Sort）

URL: https://caijiao.org/sort/10-radix-sort
Source: docs/sort/10-radix-sort.md
Description: 基数排序是一种非比较类排序，适用于整数或定长字符串。本文介绍 LSD 方式的基数排序算法，提供 JavaScript、Python、C++、Java、PHP、Go 多语言代码实现

基数排序是一种**非比较类排序算法**，适用于**整数、字符串等可按位切分的元素**。它通过逐位排序的方式，从低位到高位依次排序，最终获得有序结果，常采用**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 基数排序（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)             |
| 稳定性    | ✅ 稳定（使用稳定排序实现）       |
| 是否原地排序 | ❌ 否（需额外空间）           |
| 适用条件   | 非负整数或定长字符串排序         |

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