基数排序【C语言】

基数排序（Radix Sort）是一种非比较排序算法，可以在O(nk)的时间复杂度内完成排序，其中n是待排序元素的数量，k是所有数字的最大位数。基数排序首先将数字按照位数进行分组，通常采用稳定的排序算法（如计数排序）来完成每个位的排序。

代码注释版：  void radixSort(int *a, int num) { if (num <= 0) return; // 处理空数组 // 1. 寻找最大值和最小值 int max = a[0], min = a[0]; for (int i = 1; i < num; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } // 2. 处理负数偏移（存在溢出风险） long long offset = -(long long)min; // 转为long long防止溢出 for (int i = 0; i < num; i++) { a[i] += offset; // 隐含风险：若原a[i] + offset超出int范围，实际会溢出 } max += offset; // 更新最大值 // 3. 基数排序主循环 for (long long exp = 1; max / exp > 0; exp *= 10) { // 使用long long防止exp溢出 int count[10] = {0}; // 统计当前位分布 for (int i = 0; i < num; i++) { count[(a[i] / exp) % 10]++; } // 计算累积分布 for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } // 动态分配临时数组（避免栈溢出） int *temp = (int *)malloc(num * sizeof(int)); if (!temp) { perror("Memory allocation failed"); exit(EXIT_FAILURE); } // 从后向前填充临时数组（保证稳定性） for (int i = num - 1; i >= 0; i--) { int digit = (a[i] / exp) % 10; temp[--count[digit]] = a[i]; } // 写回原数组 for (int i = 0; i < num; i++) { a[i] = temp[i]; } free(temp); // 释放临时内存 // 提前终止检测：避免exp溢出后死循环 if (exp >= 1e10) break; } // 4. 恢复原始值（同样注意溢出） for (int i = 0; i < num; i++) { a[i] -= offset; } } 代码引用版（直接用）： int radixSort(int *a, int num) { int max = a[0], min = a[0]; for (int i = 1; i < num; i++) { if (a[i] > max)max = a[i]; if (a[i] < min)min = a[i]; } for (int i = 0; i < num; i++) { a[i] += (-min); } max += (-min); for (int exp = 1; max / exp > 0; exp *= 10) { int count[10] = {0}; for (int i = 0; i < num; i++) { count[(a[i] / exp) % 10]++; } for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } int *temp = (int *)malloc(num * sizeof(int)); for (int i = num - 1; i >= 0; i--) { int q = (a[i] / exp) % 10; temp[count[q] - 1] = a[i]; count[q]--; } for (int i = 0; i < num; i++) { a[i] = temp[i]; } free(temp); if (exp >= 1e10)return -1; } for (int i = 0; i < num; i++) { a[i] -= (-min); } return 0; }