基数排序(Radix Sort)详解
一、基数排序简介
基数排序(Radix Sort)是一种非比较型整数排序算法,适用于整数或者字符串的排序。它的基本思想是:按照“位”进行排序,先排低位,再排高位,直到所有位都排好。它通常配合**计数排序(Counting Sort)**在每一位上进行稳定排序。
二、算法原理(以十进制整数为例)
假设我们要排序一组整数:
[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]
最终得到有序序列。
三、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)
- 稳定性:是稳定排序
- 缺点:对大数或变长数字不适合;占用空间较多