基数排序有两种实现方式。本例属于最高位优先法，思路是从最高位开始，依次对基数进行排序。与之对应的是「最低位优先法」，思路是从最低位开始，依次对基数进行排序。
基数排序可以分为以下三个步骤：
1.找到数组中的最大值，确定最大数字的位数
2.从最低位开始，对数组进行计数排序。计数排序是稳定排序，所以在每一位排序后，相同数值的元素仍然保持相对顺序。
3.重复上述步骤，逐渐向更高位进行排序，直到完成所有位的排序。
4.最终，数组中的元素将按照各个位上的数值排序，从而得到有序数组.
基数排序的时间复杂度是 O(nk)，其中 n 是数组的元素个数，k 是最大数字的位数。它的时间复杂度通常比较稳定，适用于对整数或字符串进行排序。
// 获取数组中的最大值
int getMax(std::vector<int>& arr) {
int max = arr[0];
for (int value : arr) {
if (value > max) {
max = value;
}
}
return max;
}
// 基数排序的辅助函数，对数组按照指定位数进行计数排序
void countingSort(std::vector<int>& arr, int exp) {
int n = arr.size();
std::vector<int> output(n);
int counting[10] = {0};
// 统计当前位数上的数字出现次数
for (int i = 0; i < n; i++) {
counting[(arr[i] / exp) % 10]++;
}
// 计算累计次数
for (int i = 1; i < 10; i++) {
counting[i] += counting[i - 1];
}
// 构建排序后的输出数组
for (int i = n - 1; i >= 0; i--) {
output[counting[(arr[i] / exp) % 10] - 1] = arr[i];
counting[(arr[i] / exp) % 10]--;
}
// 将排序后的结果复制回原数组
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// 基数排序函数
void radixSort(std::vector<int>& arr) {
if (arr.empty()) return;
int max = getMax(arr);
// 从最低位到最高位进行排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
对包含负数的数组进行基数排序
// 获取数组中的最大值
int getMax(std::vector<int>& arr) {
int max = arr[0];
for (int value : arr) {
if (value > max) {
max = value;
}
}
return max;
}
// 基数排序的辅助函数，对非负整数数组按照指定位数进行计数排序
void countingSort(std::vector<int>& arr, int exp) {
int n = arr.size();
std::vector<int> output(n);
int counting[10] = {0};
// 统计当前位数上的数字出现次数
for (int i = 0; i < n; i++) {
counting[(arr[i] / exp) % 10]++;
}
// 计算累计次数
for (int i = 1; i < 10; i++) {
counting[i] += counting[i - 1];
}
// 构建排序后的输出数组
for (int i = n - 1; i >= 0; i--) {
output[counting[(arr[i] / exp) % 10] - 1] = arr[i];
counting[(arr[i] / exp) % 10]--;
}
// 将排序后的结果复制回原数组
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// 基数排序函数，包含对非负和负数的排序
void radixSort(std::vector<int>& arr) {
if (arr.empty()) return;
// 分离正数和负数
std::vector<int> positive;
std::vector<int> negative;
for (int num : arr) {
if (num >= 0) {
positive.push_back(num);
} else {
negative.push_back(-num); // 负数取相反数
}
}
// 对非负整数排序
if (!positive.empty()) {
int maxPositive = getMax(positive);
for (int exp = 1; maxPositive / exp > 0; exp *= 10) {
countingSort(positive, exp);
}
}
// 对负数排序
if (!negative.empty()) {
int maxNegative = getMax(negative);
for (int exp = 1; maxNegative / exp > 0; exp *= 10) {
countingSort(negative, exp);
}
}
// 合并正数和负数
arr.clear();
arr.insert(arr.end(), negative.rbegin(), negative.rend());
arr.insert(arr.end(), positive.begin(), positive.end());
}
最高位优先发（MSD）
// 获取数组中的最大值的绝对值
int getMax(std::vector<int>& arr) {
int max = 0;
for (int value : arr) {
if (std::abs(value) > max) {
max = std::abs(value);
}
}
return max;
}
// 计数排序函数
void countingSort(std::vector<int>& arr, int exp) {
int n = arr.size();
std::vector<int> output(n);
int counting[19] = { 0 };
// 统计当前位数上的数字出现次数
for (int i = 0; i < n; i++) {
int radix = (arr[i] / exp) % 10 + 9; // 转换为正数索引
counting[radix]++;
}
// 计算累计次数
for (int i = 1; i < 19; i++) {
counting[i] += counting[i - 1];
}
// 构建排序后的输出数组
for (int i = n - 1; i >= 0; i--) {
int radix = (arr[i] / exp) % 10 + 9; // 转换为正数索引
output[--counting[radix]] = arr[i];
}
// 将排序后的结果复制回原数组
std::copy(output.begin(), output.end(), arr.begin());
}
// 最高位优先的基数排序函数，从大到小排序
void radixSortDescending(std::vector<int>& arr, int max) {
if (arr.empty()) return;
int exp = 1; // 从最低位开始
while (max / exp > 0) {
countingSort(arr, exp);
exp *= 10;
}
// 倒序输出结果，以实现从大到小排序
std::reverse(arr.begin(), arr.end());
}
