基数排序适合定长字符串字典序重排，通过MSD策略逐位映射字符为整数（如A→0…Z→25，0→26…9→35，k=36），用计数排序实现稳定线性时间排序，并支持预分配、复用缓冲区及小规模切插入排序等优化。

基数排序特别适合定长字符串的字典序重排，关键在于把每个字符看作“一位数字”，用LSD或MSD方式逐位稳定排序。它不比较字符串整体，只按位置处理，所以比快排、归并等快得多，尤其在编码长度固定、字符集有限时，能稳定达到线性时间复杂度。

明确字符串结构与字符映射规则

定长编码（如8位订单号 ORD2024A7、6位工单ID TK0089）必须统一长度，且每位取值范围清晰。例如：前3位是大写字母（A–Z），后5位是数字（0–9），共8位。这时可定义字符到整数的映射：

• A→0, B→1, …, Z→25；0→26, 1→27, …, 9→35 —— 总共36个可能值，即基数 k = 36
• 若含小写、下划线或更多符号，需扩展映射表，但要保证映射唯一、有序（字典序对应数值序）
• 映射必须全程一致，不可在某轮排序中改变规则

选用MSD策略更贴合业务语义

字符串字典序本质是“从左到右逐位判别”，高位字符权重更高。比如 ABC123 一定排在 ABD000 前，哪怕后面数字更大。因此MSD（最高位优先）比LSD更自然、更易理解、也更利于提前剪枝：

• 先按第1位分桶（如所有以'A'开头的进桶0，'B'进桶1……）
• 对每个非空桶，递归按第2位再分桶；空桶跳过，减少无效操作
• 当桶内只剩1个字符串，或已处理到末位，直接收集结果
• 相比LSD需固定执行8轮，MSD常能早停，实际轮次更少

用计数排序做子过程，避免链表开销

每一轮按某一位排序时，不用真正建10+个动态桶（如ArrayList[]），而是用计数排序的思路提升缓存友好性：

• 申请长度为k的计数数组（如k=36），遍历全部字符串，统计该位各字符出现频次
• 做前缀和，得到每个字符在输出数组中的起始索引
• 倒序遍历原数组，根据当前位字符查索引，放入output[]，索引自减
• 最后将output[]拷回原数组 —— 整个过程无指针跳转、内存连续、CPU缓存命中高

实战优化点：预分配+复用+短路判断

面向高频业务重排（如日均百万级编码刷新），可在基础算法上叠加工程优化：

• 字符串对象尽量用char[]或byte[]底层表示，避免String.substring()创建新对象
• 计数数组、输出缓冲区在首次调用后缓存复用，避免反复new int[k]和char[n][]
• 若发现某一轮所有字符串该位全相同（如全是'P'），跳过后续同位处理，直接进下一位
• 当剩余待排字符串数≤64时，切回插入排序——小规模时它比计数排序更快