一、算法简介基数排序属于非比较型排序依靠分配与收集思想完成排序不依靠元素大小比较。原理将整数按个位、十位、百位依次排序从低位到高位逐轮稳定排序最终实现整体有序常用LSD 低位优先方式。时间复杂度\(O(d(nr))\) d 为最大位数r 为基数空间复杂度\(O(nr)\)稳定性稳定排序适用场景整数、手机号、日期等固定位数数据排序二、排序思路找出数组中最大值确定最大数字位数决定排序轮数以 10 为基数依次对个位、十位、百位进行排序每一轮使用计数排序思想统计频次完成一轮位次排序逐位循环全部位数排完即整体有序三、C 完整实现代码#include iostream #include vector #include algorithm using namespace std; // 获取数组最大值 int getMax(vectorint arr) { int maxVal arr[0]; for (int num : arr) { if (num maxVal) maxVal num; } return maxVal; } // 基数排序 LSD 低位优先 void radixSort(vectorint arr) { if (arr.size() 1) return; int maxNum getMax(arr); // exp 代表当前位数 1个位 10十位 100百位 int exp 1; while (maxNum / exp 0) { vectorint temp(arr.size()); // 0~9计数桶 vectorint count(10, 0); // 1.统计当前位数字出现次数 for (int i 0; i arr.size(); i) { int digit (arr[i] / exp) % 10; count[digit]; } // 2.累加次数确定元素位置 for (int i 1; i 10; i) { count[i] count[i - 1]; } // 3.倒序放入临时数组保证排序稳定 for (int i arr.size() - 1; i 0; i--) { int digit (arr[i] / exp) % 10; temp[count[digit] - 1] arr[i]; count[digit]--; } // 4.临时数组覆盖原数组 arr temp; // 进位处理下一位 exp * 10; } } // 打印数组 void printArr(vectorint arr) { for (int val : arr) { cout val ; } cout endl; } int main() { vectorint nums {53, 3, 542, 748, 14, 214, 154, 63, 616}; cout 排序前; printArr(nums); radixSort(nums); cout 排序后; printArr(nums); return 0; }四、代码核心解析getMax 函数遍历数组拿到最大值用来判断需要排序多少位数字。逐位排序逻辑(arr[i]/exp)%10取出当前位次数字count 数组统计 0-9 每个数字出现次数倒序遍历赋值保证稳定排序不打乱前面低位排好的顺序位数递进exp * 10依次切换个位、十位、百位直到所有位数排序完成。五、优缺点总结优点线性排序效率高数据量大时远超冒泡、插入排序排序稳定相同数值相对位置不变逻辑简单容易手写实现缺点仅适合整数类数据排序使用场景受限存在额外数组开销占用内存数字位数极大时排序轮数变多效率下降六、使用场景海量手机号、QQ 号、学号排序统计类大数据整数排序笔试面试手写稳定排序优先选择基数排序