非比较排序算法详解
非比较排序的基本原理
与传统基于元素间大小比较的排序算法不同，非比较排序不依赖于直接比较两个元素的大小关系。它通过分析数据的分布特征或数值结构，利用计数、位数等信息实现高效排序。
典型实现方式
1. 计数排序（Counting Sort）
该方法适用于整数范围有限的情况。其核心思想是：统计每个值出现的频次，然后根据频次顺序还原有序序列。
实现逻辑：
- 遍历数组，找出最小值和最大值，确定值域范围。
- 创建一个大小为（最大值 - 最小值 + 1）的计数数组，初始化为零。
- 遍历原数组，对每个元素对应的索引位置进行计数。
- 按顺序将计数数组中的元素还原回原数组，完成排序。
void CountSort(int* data, size_t length) {
assert(data && length > 0);
int min_val = data[0], max_val = data[0];
for (size_t i = 1; i < length; ++i) {
if (data[i] < min_val) min_val = data[i];
if (data[i] > max_val) max_val = data[i];
}
int range = max_val - min_val + 1;
int* freq = new int[range]();
// 统计频次
for (size_t i = 0; i < length; ++i) {
freq[data[i] - min_val]++;
}
// 重建有序数组
size_t pos = 0;
for (int i = 0; i < range; ++i) {
while (freq[i]-- > 0) {
data[pos++] = i + min_val;
}
}
delete[] freq;
}优缺点分析：
- 优点：时间复杂度稳定在 O(n + k)，其中 k 为数据范围，适合密集且取值集较小的数据。
- 缺点：空间开销大，当数据范围过大时不可行；需处理负数时需偏移调整，增加复杂性。
2. 基数排序（Radix Sort）——最低位优先法（LSD）
适用于整数或可拆分为固定位数的数值类型。从个位开始，逐位进行稳定排序，最终得到整体有序序列。
核心思想：每次按某一位数字（如个位、十位）进行稳定排序，由于每一步都保持原有相对顺序，因此最终结果正确。
为什么低位排序后高位再排即可？
因为低权重位的排序先于高权重位执行，且使用的是稳定排序，所以相同高位的元素会按低位顺序排列，从而保证整体有序。
int GetMaxDigits(const int* arr, size_t n) {
int max_digit = 0;
for (size_t i = 0; i < n; ++i) {
int temp = arr[i];
int digits = 0;
while (temp) {
++digits;
temp /= 10;
}
if (digits > max_digit) max_digit = digits;
}
return max_digit;
}
void LSDRadixSort(int* data, size_t length) {
assert(data && length > 0);
int max_digits = GetMaxDigits(data, length);
int bucket[10] = {0};
int count[10] = {0};
int* temp_arr = new int[length];
int divisor = 1;
for (int digit = 0; digit < max_digits; ++digit) {
// 重置计数数组
memset(count, 0, sizeof(count));
// 统计当前位数字频次
for (size_t i = 0; i < length; ++i) {
int digit_val = (data[i] / divisor) % 10;
count[digit_val]++;
}
// 构建起始索引表
bucket[0] = 0;
for (int i = 1; i < 10; ++i) {
bucket[i] = bucket[i-1] + count[i-1];
}
// 按当前位分配到临时数组
for (size_t i = 0; i < length; ++i) {
int d = (data[i] / divisor) % 10;
temp_arr[bucket[d]++] = data[i];
}
// 复制回原数组
memcpy(data, temp_arr, sizeof(int) * length);
divisor *= 10;
}
delete[] temp_arr;
}适用场景：适合用于大量整数排序，尤其在数据范围明确、位数固定的场景中表现优异。
