基数排序算法（附 Python/Java/C/C++ 程序）

2025年5月20日 | 10 分钟阅读

基数排序的过程类似于按字母顺序对学生姓名进行排序。在这种情况下，由于英文字母表中有 26 个字母，因此形成了 26 个基数。在第一轮中，学生姓名根据其姓名的首字母升序分组。之后，在第二轮中，他们的姓名根据其姓名的第二个字母升序分组。这个过程会一直持续，直到我们得到排序好的列表。

算法

RADIX_SORT(array, max_digits)
    for digit in 1 to max_digits do
        Create buckets for digits 0 to 9
        for each element in the array, do
            Extract the digit at the current position
            Place the element in the corresponding bucket
        Collect elements from the buckets in order
    return a sorted array

基数排序的步骤

第 1 步： 识别输入数组中的最大数。

第 2 步： 找出最大数有多少位。这个位数决定了排序需要进行的迭代次数。

第 3 步： 使用计数排序的概念，根据个位数字对数字进行排序。

第 4 步： 再次根据十位数字对数字进行排序，然后是百位，并一直重复此过程，直到我们到达最高有效位。

基数排序算法的工作原理

让我们看看基数排序算法的工作原理。考虑以下未排序的数组。

首先，我们必须从给定数组中找到最大的元素（在我们的例子中是 803）。它有三位数字。所以，迭代将进行三次。

第一次迭代

在第一轮中，列表根据个位上的数字进行排序。

第二次迭代

在这一轮中，列表根据下一个有效位（即十位上的数字）进行排序。第二次迭代后，数组元素为

第三次迭代

在这一轮中，列表根据下一个有效位（即百位上的数字）进行排序。第三次迭代后，数组元素为

现在，数组已按升序排序。

在 Python/Java/C/C++/C# 中实现基数排序

Python 程序

# Python program for implementation of Radix Sort
# A function that does a counting sort of arr[] as per 
# the digits shown by exp.
def countingSort(arr, exp):
    s = len(arr)
    # The output array. It will have the sorted array
	# initializing all elements to 0
    outputArray = [0] * (s)
    # count array has 10 elements. 
	# All elements have the value 0
    countArray = [0] * (10)
    # Storing count of occurrences in countArray[]
    for j in range(0, s):
        idx = arr[j] // exp
        countArray[idx % 10] += 1
    # Change countArray[j] so that countArray[j] now contains actual
    # position of this digit in the output array
    for j in range(1, 10):
        countArray[j] += countArray[j - 1]
    # Build the output array
    j = s - 1
    while j >= 0:
        idx = arr[j] // exp
        outputArray[countArray[idx % 10] - 1] = arr[j]
        countArray[idx % 10] -= 1
        j -= 1
    # copy the output array to arr[],
    # Thus, arr now contains numbers in sorted order
    j = 0
    for j in range(0, len(arr)):
        arr[j] = outputArray[j]
# Method to do Radix Sort
def radixSort(arr):
    # Find the maximum number to know the number of digits
    max1 = max(arr)
    # Applying counting sort on every digit. Observe that
    # In lieu of sending a digit number, the exp is sent. 
    exp = 1
    while max1 / exp >= 1:
        countingSort(arr, exp)
        exp *= 10
# Driver code
arr = [171, 46, 76, 91, 803, 25, 3, 67]
print("Before Sorting array elements are: ")
for j in range(len(arr)):
	print("%d" % arr[j], end=" ")
# Function Call
radixSort(arr)
print("\nAfter Sorting array elements are: ")
for j in range(len(arr)):
	print("%d" % arr[j], end=" ")

立即执行

Java 程序

import java.io.*;
import java.util.*;
public class Main {
    // A utility function to get maximum value in a[]
    static int findMax(int a[], int s)
    {
        int max = a[0];
        for (int j = 1; j < s; j++)
            if (a[j] > max)
                max = a[j];
        return max;
    }
    // A function that does a counting sort of a[] as per the digit represented by exp.
    static void countSort(int a[], int s, int exp)
    {
        int outputArray[] = new int[s]; // output array
        int j;
        int countArray[] = new int[10];
        Arrays.fill(countArray, 0);
        // Storing count of occurrences in the countArray[]
        for (j = 0; j < s; j++)
            countArray[(a[j] / exp) % 10]++;
        // Changing countArray[j] so that countArray[j] now contains actual position of this digit in the outputArray[]
        for (j = 1; j < 10; j++)
            countArray[j] += countArray[j - 1];
        // Building the output array
        for (j = s - 1; j >= 0; j--) {
            outputArray[countArray[(a[j] / exp) % 10] - 1] = a[j];
            countArray[(a[j] / exp) % 10]--;
        }
        // Copying the output array to a[], so that a[] now contains sorted numbers according to the current
        // digit
        for (j = 0; j < s; j++)
            a[j] = outputArray[j];
    }
    // The main function to that sorts a[] of size s with the Radix Sort
    static void radixSort(int a[], int s)
    {
        // Find the maximum number to know the number of digits
        int m = findMax(a, s);
        // Applying counting sort on every digit. Observe that in lieu of sending a digit number, exp is sent. 
        for (int exp = 1; m / exp > 0; exp *= 10)
            countSort(a, s, exp);
    }
    // Main method
    public static void main(String[] args)
    {
        int a[] = {171, 46, 76, 91, 803, 25, 3, 67};
        int s = a.length;
        System.out.println("Before Sorting array elements are: ");
        for(int j = 0; j < s; j++)
        {
        	System.out.print(a[j] + " ");
        }
        // Function Call
        radixSort(a, s);
        System.out.println("\nAfter Sorting array elements are: ");
        for(int j = 0; j < s; j++)
        {
        	System.out.print(a[j] + " ");
        }
    }
}

编译并运行

C++ 程序

#include <iostream>
using namespace std;
// A utility function to get maximum value in a[]
int findMax(int a[], int s)
{
    int max = a[0];
    for (int j = 1; j < s; j++)
        if (a[j] > max)
            max = a[j];
    return max;
}
// A function that does a counting sort of a[] as per the digit represented by exp.
void countSort(int a[], int s, int exp)
{
    int outputArray[s]; // output array
    int j;
    int countArray[10]; // count array
    // assigning all elements value 0
    for(int i = 0; i < 10; i++) 
    	countArray[i] = 0;
    // Storing count of occurrences in the countArray[]
    for (j = 0; j < s; j++)
        countArray[(a[j] / exp) % 10]++;
    // Changing countArray[j] so that countArray[j] now contains
    // actual position of this digit in the outputArray[]
    for (j = 1; j < 10; j++)
        countArray[j] += countArray[j - 1];
    // Building the output array
    for (j = s - 1; j >= 0; j--) {
        outputArray[countArray[(a[j] / exp) % 10] - 1] = a[j];
        countArray[(a[j] / exp) % 10]--;
    }
    // Copying the output array to a[], so that a[] now
    // contains sorted numbers according to the current
    // digit
    for (j = 0; j < s; j++)
        a[j] = outputArray[j];
}
void radixSort(int a[], int s)
{
    // Find the maximum number to know the number of digits
    int m = findMax(a, s);
    // Applying counting sort on every digit. Observe that in lieu of sending a digit number, exp is sent. 
    for (int exp = 1; m / exp > 0; exp *= 10)
        countSort(a, s, exp);
}
// Main method
int main()
{
    int a[] = {171, 46, 76, 91, 803, 25, 3, 67};
    int s = sizeof(a) / sizeof(a[0]);
    cout<<"Before Sorting array elements are: \n";
    for(int j = 0; j < s; j++)
    {
    	cout<<a[j]<<" ";
    }
    // Function Call
    radixSort(a, s);
    cout<<"\nAfter Sorting array elements are: \n";
    for(int j = 0; j < s; j++)
    {
    	cout<<a[j]<<" ";
    }
    return 0;
}

编译并运行

C 语言程序

#include <stdio.h>
// A utility function to get the maximum value in a[]
int findMax(int a[], int s)
{
    int max = a[0];
    for (int j = 1; j < s; j++)
        if (a[j] > max)
            max = a[j];
    return max;
}
// A function that does a counting sort of a[] as per the digit represented by exp.
void countSort(int a[], int s, int exp)
{
    int outputArray[s]; // output array
    int j;
    int countArray[10]; // count array
    // assigning all elements value 0
    for(int i = 0; i < 10; i++) 
    	countArray[i] = 0;
    // Storing count of occurrences in the countArray[]
    for (j = 0; j < s; j++)
        countArray[(a[j] / exp) % 10]++;
    // Changing countArray[j] so that countArray[j] now contains actual position of this digit in the outputArray[]
    for (j = 1; j < 10; j++)
        countArray[j] += countArray[j - 1];
    // Building the output array
    for (j = s - 1; j >= 0; j--) {
        outputArray[countArray[(a[j] / exp) % 10] - 1] = a[j];
        countArray[(a[j] / exp) % 10]--;
    }
    // Copying the output array to a[], so that a[] now contains sorted numbers according to the current digit
    for (j = 0; j < s; j++)
        a[j] = outputArray[j];
}
void radixSort(int a[], int s)
{
    // Find the maximum number to know number of digits
    int m = findMax(a, s);
    // Applying counting sort on every digit. Observe that in lieu of sending a digit number, exp is sent. 
    for (int exp = 1; m / exp > 0; exp *= 10)
        countSort(a, s, exp);
}
// Main method
int main()
{
    int a[] = {171, 46, 76, 91, 803, 25, 3, 67};
    int s = sizeof(a) / sizeof(a[0]);
    printf("Before Sorting array elements are: \n");
    for(int j = 0; j < s; j++)
    {
    	printf("%d ", a[j]);
    }
    // Function Call
    radixSort(a, s);
    printf("\nAfter Sorting array elements are: \n");
    for(int j = 0; j < s; j++)
    {
    	printf("%d ", a[j]);
    }
    return 0;
}

编译并运行

C# 程序

using System;
class RadixSort {
    // A utility function to get maximum value in a[]
    public static int findMax(int[] a, int s)
    {
        int max = a[0];
        for (int j = 1; j < s; j++)
            if (a[j] > max)
                max = a[j];
        return max;
    }
    // A function that does a counting sort of a[] as per the digit represented by exp.
    public static void countSort(int[] a, int s, int exp)
    {
        int[] outputArray = new int[s]; // output array
        int j;
    	int[] countArray = new int[10]; // count array
    	// assigning all elements value 0
    	for(int i = 0; i < 10; i++) 
    		countArray[i] = 0;
        // Storing count of occurrences in the countArray[]
        for (j = 0; j < s; j++)
            countArray[(a[j] / exp) % 10]++;
        // Changing countArray[j] so that countArray[j] now contains actual position of this digit in the outputArray[]
        for (j = 1; j < 10; j++)
            countArray[j] += countArray[j - 1];
        // Building the output array
        for (j = s - 1; j >= 0; j--) {
            outputArray[countArray[(a[j] / exp) % 10] - 1] = a[j];
            countArray[(a[j] / exp) % 10]--;
        }
        // Copying the output array to a[], so that a[] now contains sorted numbers according to the current
        // digit
        for (j = 0; j < s; j++)
            a[j] = outputArray[j];
    }
    public static void radixSort(int[] a, int s)
    {
        // Find the maximum number to know the number of digits
        int m = findMax(a, s);
        // Applying counting sort on every digit. Observe that in lieu of sending a digit number, exp is sent. 
        for (int exp = 1; m / exp > 0; exp *= 10)
            countSort(a, s, exp);
    }
// Main method
public static void Main()
{
    int[] a = {171, 46, 76, 91, 803, 25, 3, 67};
    int s = a.Length;
    Console.Write("Before Sorting array elements are: \n");
    for(int j = 0; j < s; j++)
    {
    	Console.Write(a[j] + " ");
    }
    // Function Call
    radixSort(a, s);
    Console.Write("\nAfter Sorting array elements are: \n");
    for(int j = 0; j < s; j++)
    {
    	Console.Write(a[j] + " ");
    }
}
}

编译并运行

输出

Before Sorting array elements are: 
171 46 76 91 803 25 3 67 
After Sorting array elements are: 
3 25 46 67 76 91 171 803

复杂度分析

时间复杂度

情况	时间复杂度
最佳情况	O(d * (n + b))
平均情况	O(d * (n + b))
最坏情况	O(d * (n + b))

在所有三种情况下，基数排序的时间复杂度为 O(d * (n + b))，其中 d 是数组中最大元素存在的位数。n 是数组中存在的元素总数，b 是程序中使用的数字系统的基数。在我们的例子中，我们使用了基数 10。

空间复杂度

基数排序的空间复杂度为 O(n + b)，其中 n 是数组中存在的元素总数，b 是数字系统的基数。

基数排序的应用

它是一种常用的算法，适用于范围不大但有限的场景。例如，按时间对事件排序，按成绩对学生排序，按日、年、月、时间等对事件排序。
它曾被用于有 80 列的卡片排序设备，在每一列中，设备只能在 12 个位置打孔。然后，排序机被设计为根据卡片被打孔的位置对卡片进行排序。

基数排序的优点

基数排序具有线性时间复杂度。因此，对于大型数据集，它比其他基于比较的排序算法（如归并排序和快速排序）更快。
基数排序是一种稳定的排序算法。
基数排序非常适合对大量字符串或整数进行排序。
在基数排序中可以轻松实现并行化。

基数排序的缺点

基数排序不适用于对浮点数或其他无法映射到少量位数的数据类型进行排序。
基数排序需要相当大的内存来存储每个数字出现的频率。
它不适合小型数据集或唯一键数量少的数据集。
基数排序要求待排序的数据可以用固定位数的数字表示，这对于某些类型的数据可能不成立。

结论

在处理需要高效排序的庞大数据集时，基数排序是一种有用的排序技术，当使用字符或数字来组织数据时，它的效果最好。

下一个主题计数排序

基数排序算法（附 Python/Java/C/C++ 程序）

算法

基数排序的步骤

基数排序算法的工作原理

第一次迭代

第二次迭代

第三次迭代

在 Python/Java/C/C++/C# 中实现基数排序

Python 程序

Java 程序

C++ 程序

C 语言程序

C# 程序

复杂度分析

时间复杂度

空间复杂度

基数排序的应用

基数排序的优点

基数排序的缺点

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

基数排序算法 （附 Python/Java/C/C++ 程序）

算法

基数排序的步骤

基数排序算法的工作原理

第一次迭代

第二次迭代

第三次迭代

在 Python/Java/C/C++/C# 中实现基数排序

Python 程序

Java 程序

C++ 程序

C 语言程序

C# 程序

复杂度分析

时间复杂度

空间复杂度

基数排序的应用

基数排序的优点

基数排序的缺点

结论

相关帖子

归并排序算法

堆排序算法

冒泡排序算法

排序算法的时间复杂度

插入排序算法

排序算法

选择排序算法

希尔排序算法

桶排序算法

快速排序算法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器

基数排序算法（附 Python/Java/C/C++ 程序）