Skip to content
酷学小栈

基数排序

基数排序(Radix Sort)详解 一、基数排序简介 基数排序(Radix Sort)是一种非比较型整数排序算法,适用于整数或者字符串的排序。它的基本思想是:按照“位”进行排序,先排低位,再排高位,直到所有位都排好。它通常配合 计数排序(Counting Sort) 在每一位上进行稳定排序。…

On this page
  1. 一、基数排序简介
  2. 二、算法原理(以十进制整数为例)
  3. 三、C++ 程序实例(含详细注释)
  4. 四、输出示例
  5. 五、适用范围与特点

基数排序(Radix Sort)详解

一、基数排序简介

基数排序(Radix Sort)是一种非比较型整数排序算法,适用于整数或者字符串的排序。它的基本思想是:按照“位”进行排序,先排低位,再排高位,直到所有位都排好。它通常配合**计数排序(Counting Sort)**在每一位上进行稳定排序。

二、算法原理(以十进制整数为例)

假设我们要排序一组整数:

[170, 45, 75, 90, 802, 24, 2, 66]

我们按照如下步骤排序:

  1. 个位排序:对每个数字的个位数排序
    → [170, 90, 802, 2, 24, 45, 75, 66]
  2. 十位排序:对每个数字的十位排序
    → [802, 2, 24, 45, 66, 170, 75, 90]
  3. 百位排序:对每个数字的百位排序
    → [2, 24, 45, 66, 75, 90, 170, 802]

最终得到有序序列。

三、C++ 程序实例(含详细注释)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 获取数组中的最大值,用来决定排序的轮数(最大位数)
int getMax(const vector<int>& arr) {
return *max_element(arr.begin(), arr.end());
}
// 对数组按位数进行计数排序
void countingSort(vector<int>& arr, int exp) {
int n = arr.size();
vector<int> output(n); // 输出数组
int count[10] = {0}; // 计数数组(十进制 0~9)
// 统计每个数字在该位(exp)上的出现次数
for (int i = 0; i < n; i++) {
int digit = (arr[i] / exp) % 10;
count[digit]++;
}
// 将 count 数组转化为前缀和数组,确定每个数字在 output 中的位置
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];
}
}
// 基数排序主函数
void radixSort(vector<int>& arr) {
int maxVal = getMax(arr); // 获取最大数,确定最大位数
// 从个位开始,对每一位进行排序(exp: 1, 10, 100, ...)
for (int exp = 1; maxVal / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
// 打印数组的辅助函数
void printArray(const vector<int>& arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
// 测试程序
int main() {
vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
cout << "原始数组: ";
printArray(arr);
radixSort(arr);
cout << "排序后数组: ";
printArray(arr);
return 0;
}

四、输出示例

原始数组: 170 45 75 90 802 24 2 66
排序后数组: 2 24 45 66 75 90 170 802

五、适用范围与特点

  • 适用场景:整数、固定长度字符串
  • 时间复杂度:O(nk),其中 n 是元素个数,k 是位数
  • 空间复杂度:O(n + k)
  • 稳定性:是稳定排序
  • 缺点:对大数或变长数字不适合;占用空间较多