基数排序
最后更新
基数排序是一种用于整数的非比较排序。它不比较数值的大小，而是逐位对数字排序。最低位优先（LSD）版本先处理个位，再处理十位，然后是百位，每一位都使用稳定的计数排序。因为每一轮都是稳定的，所以处理完最高位后，整个数组就有序了。点击上方的“播放”，观看每一轮按位排序如何重新排列这些条形。
基数排序的时间复杂度是 O(d·(n + k))，其中 d 是位数，k 是基数（这里是 10）。对于固定位宽的整数，这实际上是线性时间，可以胜过 O(n log n) 的比较排序，但它只适用于能拆分成数位或键的数据。
时间复杂度与空间复杂度
| 情况 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(d·(n + k)) | d 位数，基数 k（d 固定时为线性） |
| 空间 | O(n + k) | 输出数组 + 各数位的计数 |
| 稳定性 | 稳定 | 每一轮都是稳定的计数排序 |
| 是否比较？ | 否 | 按数位排序，不比较数值大小 |
| 适用于 | 整数/键 | 不适用于一般的可比较对象 |
分步说明
| 步骤 | 发生了什么 |
|---|---|
| 1 | 找出最大值，确定需要处理多少位。 |
| 2 | 从最低位（个位）开始。 |
| 3 | 用计数排序按这一位对数组做稳定排序。 |
| 4 | 移到下一个更高的数位。 |
| 5 | 重复以上步骤，直到处理完所有数位。 |
实例演示
对 [170, 45, 75, 90, 2, 24, 66] 排序：
| 轮次 | 数组 | 操作 |
|---|---|---|
| 开始 | [170, 45, 75, 90, 2, 24, 66] | 最大值是 170，所以需要三轮按位排序。 |
| 个位 | [170, 90, 2, 24, 45, 75, 66] | 按个位稳定排序：0, 0, 2, 4, 5, 5, 6。 |
| 十位 | [2, 24, 45, 66, 170, 75, 90] | 按十位稳定排序：0, 2, 4, 6, 7, 7, 9（170 仍排在 75 前面）。 |
| 百位 | [2, 24, 45, 66, 75, 90, 170] | 按百位稳定排序；只有 170 的百位是 1，所以它移到最后。排序完成。 |
什么时候用基数排序
| 适合使用 | 不适合使用 |
|---|---|
| 键是整数或定长字符串，可以拆分成数位。 | 你必须用自定义比较器对任意对象排序。 |
键的位数 d 少且有上限，所以 O(d·(n + k)) 能胜过 O(n log n)。 | 键非常长或没有上限，导致 d 很大，每一轮的开销都很高。 |
你需要稳定排序，并且能承受 O(n + k) 的额外空间。 | 内存紧张，无法接受 O(n + k) 的缓冲区。 |
取值范围或基数 k 相对 n 不大。 | k 极大，每一轮计数排序都会成为运行时间的主要部分。 |
Radix Sort 代码
简洁、可运行的 Radix Sort 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Radix Sort 的 Python 代码
Python
1def radix_sort(a):2 # Sort by each decimal digit, least significant first3 max_value = max(a)4 exp = 15 while max_value // exp > 0:6 a = sort_by_digit(a, exp)7 exp *= 108 return a9
10
11def sort_by_digit(a, exp):12 buckets = [[] for _ in range(10)]13 for value in a:14 digit = (value // exp) % 1015 buckets[digit].append(value)16 # Concatenating buckets 0..9 keeps the sort stable17 return [value for bucket in buckets for value in bucket]18
19
20nums = [170, 45, 75, 90, 802, 24, 2, 66]21print("Before:", nums)22print("After: ", radix_sort(nums))Radix Sort 的 JavaScript 代码
JavaScript
1function radixSort(arr) {2 let a = [...arr];3 const max = Math.max(...a);4 // One counting pass per digit, least significant first5 for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {6 const buckets = Array.from({ length: 10 }, () => []);7 for (const x of a) {8 buckets[Math.floor(x / exp) % 10].push(x);9 }10 a = buckets.flat();11 }12 return a;13}14
15const data = [170, 45, 75, 90, 802, 24, 2, 66];16console.log("Before:", data);17console.log("Sorted:", radixSort(data));Radix Sort 的 Java 代码
Java
1import java.util.Arrays;2
3public class Main {4 static void radixSort(int[] arr) {5 int max = 0;6 for (int v : arr) max = Math.max(max, v);7 // One stable counting pass per decimal digit8 for (int exp = 1; max / exp > 0; exp *= 10) countingPass(arr, exp);9 }10
11 static void countingPass(int[] arr, int exp) {12 int n = arr.length;13 int[] out = new int[n];14 int[] count = new int[10];15 for (int v : arr) count[(v / exp) % 10]++;16 for (int i = 1; i < 10; i++) count[i] += count[i - 1];17 // Walk backwards to keep the pass stable18 for (int i = n - 1; i >= 0; i--) {19 int digit = (arr[i] / exp) % 10;20 out[--count[digit]] = arr[i];21 }22 System.arraycopy(out, 0, arr, 0, n);23 }24
25 public static void main(String[] args) {26 int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};27 System.out.println("Before: " + Arrays.toString(arr));28 radixSort(arr);29 System.out.println("After: " + Arrays.toString(arr));30 }31}Radix Sort 的 C++ 代码
C++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)11void countingPass(std::vector<int>& a, int exp) {12 std::vector<int> output(a.size());13 std::vector<int> count(10, 0);14 for (int x : a) ++count[(x / exp) % 10];15 for (int d = 1; d < 10; ++d) count[d] += count[d - 1];16 for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {17 int digit = (a[i] / exp) % 10;18 output[--count[digit]] = a[i];19 }20 a = output;21}22
23void radixSort(std::vector<int>& a) {24 int maxVal = *std::max_element(a.begin(), a.end());25 for (int exp = 1; maxVal / exp > 0; exp *= 10) {26 countingPass(a, exp);27 }28}29
30int main() {31 std::vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};32 std::cout << "Before: ";33 printVec(data);34 radixSort(data);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Radix Sort 的 C 代码
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)10void countingPass(int a[], int n, int exp) {11 int* output = malloc(n * sizeof(int));12 int count[10] = {0};13 for (int i = 0; i < n; i++) count[(a[i] / exp) % 10]++;14 for (int d = 1; d < 10; d++) count[d] += count[d - 1];15 for (int i = n - 1; i >= 0; i--) {16 int digit = (a[i] / exp) % 10;17 output[--count[digit]] = a[i];18 }19 for (int i = 0; i < n; i++) a[i] = output[i];20 free(output);21}22
23void radixSort(int a[], int n) {24 int maxVal = a[0];25 for (int i = 1; i < n; i++) {26 if (a[i] > maxVal) maxVal = a[i];27 }28 for (int exp = 1; maxVal / exp > 0; exp *= 10) {29 countingPass(a, n, exp);30 }31}32
33int main(void) {34 int data[] = {170, 45, 75, 90, 802, 24, 2, 66};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 radixSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}基数排序常见问题
基数排序的时间复杂度是多少？
基数排序是
O(d·(n + k))，其中 d 是位数，k 是基数。对于固定位宽的整数，这实际上就是 O(n)，可能比比较排序更快。它需要 O(n + k) 的额外空间。基数排序是稳定的吗？
是的。LSD 基数排序在每一位上都依赖稳定的计数排序；正是这种稳定性，才让逐位排序的方法得到正确的有序结果。
什么时候可以用基数排序？
基数排序适用于能拆分成数位或固定大小键的数据，例如整数或定长字符串。它不是通用的比较排序，所以无法用自定义比较器对任意对象排序。
基数排序和计数排序有什么区别？
计数排序一轮就按单个键排好序，需要一个和取值范围一样大的计数数组，所以数值分布很广时效率会下降。基数排序逐位应用计数排序，每一轮的计数数组都很小（大小为基数
k），因此能处理普通计数排序应付不了的大取值范围。LSD 基数排序为什么从最低位开始？
从最低位开始，每一轮稳定排序都能保留之前所有低位已经确定的顺序。等到处理最高位时，最高位相同的元素已经按低位排好了，所以整个数组最终完全有序。如果先从最高位排序，就会破坏这一点，需要改用另一种递归的方法（MSD 基数排序）。
基数排序能处理负数吗？
不能直接处理，基本的取数位操作假定数据是非负整数。常见的解决办法是给所有值加上一个偏移量（减去最小值），让它们都变成非负数；或者把负数和非负数分开排序，再拼接起来。把基数排序用在真实数据上时，忽略这一点是常见的 bug。
相关资源
更多可视化
