编程导航会员会员
登录/注册

一文带你学会"基数排序"

大家好，我是算法学长，一个热爱分享算法知识的开发者。 算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。

介绍

基数排序（Radix Sort）是一种非比较型的排序算法，核心思想是按照数位来排序，从最低有效位（Least Significant Digit, LSD）或最高有效位（Most Significant Digit, MSD）开始，依次对每个位置的数字进行排序。基数排序特别适合用于整数或定长字符串的排序，时间复杂度是 O(n×k)，其中 n 是待排序数组的长度，k 是数据的最大位数。

基数排序不会直接比较元素之间的大小，通过分配和收集过程实现排序，在一些特定场景下性能优于比较排序算法。

算法步骤

  1. 找出待排序数组中的最大值，确定最大位数
  2. 从最低位开始，对每一位上的数字进行计数排序（或桶排序）
  3. 按照当前位的数字大小将元素重新排列
  4. 对下一个更高位重复步骤2和3，直到处理完所有位

核心特性

  • 非比较排序：不通过比较元素大小进行排序
  • 稳定排序：相等元素的相对位置在排序后不会改变
  • 时间复杂度：O(n×k)，其中 k 是数据的最大位数
  • 空间复杂度：O(n+r)，其中 r 是基数（比如十进制数的基数为10）
  • 适用范围：整数或固定长度的字符串

基础实现

接下来大家一起看下基数排序的部分主流语言实现：

Java实现

▼
java
复制代码
public class RadixSort {
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        // 找出最大值，确定最大位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        
        // 对每一位进行计数排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }
    
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 输出数组
        int[] count = new int[10]; // 计数数组，默认为10，因为一位数字的范围是0~9
        
        // 统计当前位上每个数字出现的次数
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }
        
        // 计算累加数组，确定每个数字在输出数组中的位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        
        // 构建输出数组，从后向前遍历以保持稳定性
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }
        
        // 将排序好的数组复制回原数组
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
    
    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("排序前的数组：");
        printArray(arr);
        
        radixSort(arr);
        
        System.out.println("排序后的数组：");
        printArray(arr);
    }
}

注意，在上述代码里，通过：

▼
java
复制代码
// 对每一位进行计数排序
for (int exp = 1; max / exp > 0; exp *= 10) {
    countingSortByDigit(arr, exp);
}

实现基数排序的核心思想，从最低位开始依次对每个位置的数字进行排序。使用计数排序作为每一轮的排序算法，保证排序稳定性。

JavaScript 实现

▼
javascript
复制代码
function radixSort(arr) {
    if (arr == null || arr.length <= 1) {
        return arr;
    }
    
    // 找出最大值，确定最大位数
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 对每一位进行计数排序
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
    
    return arr;
}

function countingSortByDigit(arr, exp) {
    const n = arr.length;
    const output = new Array(n).fill(0);
    const count = new Array(10).fill(0);
    
    // 统计当前位上每个数字出现的次数
    for (let i = 0; i < n; i++) {
        const digit = Math.floor(arr[i] / exp) % 10;
        count[digit]++;
    }
    
    // 计算累加数组，确定每个数字在输出数组中的位置
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    
    // 构建输出数组，从后向前遍历以保持稳定性
    for (let i = n - 1; i >= 0; i--) {
        const digit = Math.floor(arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    // 将排序好的数组复制回原数组
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 测试
const arr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log("排序前：", arr);
radixSort(arr);
console.log("排序后：", arr);

Python 实现

▼
python
复制代码
def radix_sort(arr):
    if not arr or len(arr) <= 1:
        return arr
    
    # 找出最大值，确定最大位数
    max_value = max(arr)
    
    # 对每一位进行计数排序
    exp = 1
    while max_value // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    # 统计当前位上每个数字出现的次数
    for i in range(n):
        digit = (arr[i] // exp) % 10
        count[digit] += 1
    
    # 计算累加数组，确定每个数字在输出数组中的位置
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # 构建输出数组，从后向前遍历以保持稳定性
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
    
    # 将排序好的数组复制回原数组
    for i in range(n):
        arr[i] = output[i]

# 测试
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("排序前：", arr)
radix_sort(arr)
print("排序后：", arr)

Go 实现

▼
go
复制代码
package main

import "fmt"

func radixSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    // 找出最大值，确定最大位数
    max := arr[0]
    for i := 1; i < len(arr); i++ {
        if arr[i] > max {
            max = arr[i]
        }
    }
    
    // 对每一位进行计数排序
    for exp := 1; max/exp > 0; exp *= 10 {
        countingSortByDigit(arr, exp)
    }
    
    return arr
}

func countingSortByDigit(arr []int, exp int) {
    n := len(arr)
    output := make([]int, n)
    count := make([]int, 10) // 计数数组，默认为10
    
    // 统计当前位上每个数字出现的次数
    for i := 0; i < n; i++ {
        digit := (arr[i] / exp) % 10
        count[digit]++
    }
    
    // 计算累加数组，确定每个数字在输出数组中的位置
    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }
    
    // 构建输出数组，从后向前遍历以保持稳定性
    for i := n - 1; i >= 0; i-- {
        digit := (arr[i] / exp) % 10
        output[count[digit]-1] = arr[i]
        count[digit]--
    }
    
    // 将排序好的数组复制回原数组
    for i := 0; i < n; i++ {
        arr[i] = output[i]
    }
}

func main() {
    arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
    fmt.Println("排序前：", arr)
    radixSort(arr)
    fmt.Println("排序后：", arr)
}

C 实现

▼
c
复制代码
#include <stdio.h>
#include <stdlib.h>

// 获取数组中的最大值
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// 对数组按照特定数位进行计数排序
void countingSortByDigit(int arr[], int n, int exp) {
    int* output = (int*)malloc(n * sizeof(int));
    int count[10] = {0}; // 计数数组，默认为10
    
    // 统计当前位上每个数字出现的次数
    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];
    }
    
    free(output);
}

// 基数排序
void radixSort(int arr[], int n) {
    if (n <= 1) {
        return;
    }
    
    // 找出最大值，确定最大位数
    int max = getMax(arr, n);
    
    // 对每一位进行计数排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, n, exp);
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前：");
    printArray(arr, n);
    
    radixSort(arr, n);
    
    printf("排序后：");
    printArray(arr, n);
    
    return 0;
}

C++ 实现

▼
cpp
复制代码
#include <iostream>
#include <vector>
#include <algorithm>

// 对数组按照特定数位进行计数排序
void countingSortByDigit(std::vector<int>& arr, int exp) {
    int n = arr.size();
    std::vector<int> output(n);
    std::vector<int> count(10, 0); // 计数数组，默认为10
    
    // 统计当前位上每个数字出现的次数
    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(std::vector<int>& arr) {
    if (arr.size() <= 1) {
        return;
    }
    
    // 找出最大值，确定最大位数
    int max = *std::max_element(arr.begin(), arr.end());
    
    // 对每一位进行计数排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

// 打印数组
void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    
    std::cout << "排序前：";
    printArray(arr);
    
    radixSort(arr);
    
    std::cout << "排序后：";
    printArray(arr);
    
    return 0;
}

优化策略

处理负数

标准的基数排序不能直接处理负数，可以通过以下方式优化：

▼
java
复制代码
public static void radixSortWithNegatives(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    
    // 将数组分为负数和非负数两部分
    List<Integer> negatives = new ArrayList<>();
    List<Integer> nonNegatives = new ArrayList<>();
    
    for (int num : arr) {
        if (num < 0) {
            negatives.add(-num); // 负数取绝对值
        } else {
            nonNegatives.add(num);
        }
    }
    
    // 将负数数组转换为整数数组
    int[] negArr = new int[negatives.size()];
    for (int i = 0; i < negatives.size(); i++) {
        negArr[i] = negatives.get(i);
    }
    
    // 将非负数数组转换为整数数组
    int[] nonNegArr = new int[nonNegatives.size()];
    for (int i = 0; i < nonNegatives.size(); i++) {
        nonNegArr[i] = nonNegatives.get(i);
    }
    
    // 对两部分分别进行基数排序
    radixSort(negArr);
    radixSort(nonNegArr);
    
    // 将排序后的负数部分逆序并取反，与非负数部分合并
    int index = 0;
    for (int i = negArr.length - 1; i >= 0; i--) {
        arr[index++] = -negArr[i];
    }
    
    for (int i = 0; i < nonNegArr.length; i++) {
        arr[index++] = nonNegArr[i];
    }
}

使用不同基数

通过改变基数（radix）来优化算法性能：

▼
java
复制代码
public static void radixSortWithCustomBase(int[] arr, int base) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    
    // 找出最大值，确定最大位数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 对每一位进行计数排序
    for (int exp = 1; max / exp > 0; exp *= base) {
        countingSortByDigitWithBase(arr, exp, base);
    }
}

private static void countingSortByDigitWithBase(int[] arr, int exp, int base) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[base]; // 计数数组大小为基数
    
    // 统计当前位上每个数字出现的次数
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % base;
        count[digit]++;
    }
    
    // 计算累加数组
    for (int i = 1; i < base; i++) {
        count[i] += count[i - 1];
    }
    
    // 构建输出数组
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % base;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

优缺点

优点

  • 在固定位数的情况下，时间复杂度可达到 O(n)，比 比较排序 更快
  • 稳定排序算法，能保持相等元素的相对顺序
  • 适合处理大量数据和长整数
  • 不受输入数据分布影响，排序性能稳定
  • 适合处理位数相同的字符串

缺点

  • 只适用于整数和定长字符串等可以分解为独立"位"的数据
  • 需要额外的空间进行计数和输出
  • 如果数据最大值很大，但数据量很小，会导致很多不必要的空桶操作
  • 对负数需要特殊处理
  • 不适合对浮点数直接进行排序（需要特殊转换）

应用场景

1）固定长度的整数排序，如电话号码、邮政编码等

2）字符串排序，比如单词字典、文件名

3）大数据量但数值范围有限的数据集排序

4）配合其他排序算法构建混合排序策略

扩展

字符串排序

▼
java
复制代码
public static void radixSortStrings(String[] arr, int maxLength) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    
    // 从最低位（最右侧）开始，对每一位进行计数排序
    for (int pos = maxLength - 1; pos >= 0; pos--) {
        countingSortByCharPosition(arr, pos);
    }
}

private static void countingSortByCharPosition(String[] arr, int pos) {
    int n = arr.length;
    String[] output = new String[n];
    
    // 字符的ASCII范围，这里简化为128
    int[] count = new int[128];
    
    // 对于短于pos的字符串，认为该位是空字符（ASCII为0）
    for (int i = 0; i < n; i++) {
        int charIndex = (pos < arr[i].length()) ? arr[i].charAt(pos) : 0;
        count[charIndex]++;
    }
    
    // 计算累加数组
    for (int i = 1; i < 128; i++) {
        count[i] += count[i - 1];
    }
    
    // 构建输出数组，从后向前遍历以保持稳定性
    for (int i = n - 1; i >= 0; i--) {
        int charIndex = (pos < arr[i].length()) ? arr[i].charAt(pos) : 0;
        output[count[charIndex] - 1] = arr[i];
        count[charIndex]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

MSD基数排序

最高位优先（Most Significant Digit, MSD）的基数排序适合字典排序：

▼
java
复制代码
public static void msdRadixSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    
    // 找出最大值，确定最大位数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 计算最大位数
    int maxDigits = 0;
    while (max > 0) {
        maxDigits++;
        max /= 10;
    }
    
    // 从最高位开始排序
    int[] temp = new int[arr.length];
    msdRadixSortRecursive(arr, temp, 0, arr.length - 1, maxDigits);
}

private static void msdRadixSortRecursive(int[] arr, int[] temp, int low, int high, int digit) {
    if (low >= high || digit <= 0) {
        return;
    }
    
    // 计算当前位的除数
    int divisor = (int)Math.pow(10, digit - 1);
    
    // 统计每个数字出现的次数
    int[] count = new int[10];
    for (int i = low; i <= high; i++) {
        int d = (arr[i] / divisor) % 10;
        count[d]++;
    }
    
    // 计算起始位置
    int[] startPos = new int[10];
    startPos[0] = low;
    for (int i = 1; i < 10; i++) {
        startPos[i] = startPos[i - 1] + count[i - 1];
    }
    
    // 排序当前位
    for (int i = low; i <= high; i++) {
        int d = (arr[i] / divisor) % 10;
        temp[startPos[d]++] = arr[i];
    }
    
    // 复制回原数组
    for (int i = low; i <= high; i++) {
        arr[i] = temp[i];
    }
    
    // 对每个数字分组进行递归排序
    int start = low;
    for (int i = 0; i < 10; i++) {
        int end = start + count[i] - 1;
        if (end > start) {
            msdRadixSortRecursive(arr, temp, start, end, digit - 1);
        }
        start = end + 1;
    }
}

测验

这里准备了一些测试题，方便大家判断自己的掌握情况：

  1. 基数排序的时间复杂度是多少？它跟归并排序相比有什么优势？
  2. LSD（最低位优先）和MSD（最高位优先）基数排序有什么区别？
  3. 基数排序在处理不同类型数据时有哪些限制？

测验答案

  1. 基数排序的时间复杂度是 O(n×k)，其中 k 是数据的最大位数。当 k 较小时，基数排序可以接近 O(n)，比归并排序的 O(nlogn) 更高效。
  2. LSD从最低位开始排序，适合按数值大小排序；MSD从最高位开始排序，适合字典序排序。LSD需要对所有数据统一排序每一位，MSD可以递归处理不同的子集。
  3. 基数排序主要适合处理可以分解为独立"位"的数据，比如整数和定长字符串，不适合直接处理浮点数、变长字符串等类型。

相关的 LeetCode 热门题目

给大家推荐一些可以用来练手的 LeetCode 题目：

基数排序在处理整数和字符串排序时有独特优势，特别是在数据量大但位数有限的情况下，能够实现接近线性时间的排序性能。

学算法就上算法导航：https://algo.codefather.cn/ ，交互式算法学习平台！

算法
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
算法学长
算法学长
等级vip
内容推荐
更多
最近刷算法的一些心得~
6
Claude Code 源码架构深度解析：1884 个文件背后的 AI 编程工具设计哲学
23
深度解析 Claude Code 记忆系统：从源码看 AI 编程助手如何"记住"你的项目
6
LeetCode Hot 100 二分查找篇 - 每次砍一半，六道题从入门到穿透
2
卷AI、卷算法、2026 年的前端工程师到底在卷什么？
7
作者分享
更多
一文带你学会"最近点对问题"
4
一文带你学会"分治算法"
4
一文带你学会"KMP 算法"
6
一文带你学会"Boyer-Moore算法"
3
一文带你学会"Rabin-Karp算法"
3
下载 APP