LSD基数排序是否需要对最右位列执行排序操作？

结论 #

完全不能跳过最右位列（最低有效位）的排序，直接从倒数第二列开始处理一定会出现排序错误。

具体原因 #

• LSD（最低有效位优先）基数排序的正确性，核心依赖从低位到高位依次执行稳定排序的逻辑：每一轮仅针对当前位的数值做稳定排序，当前位数值相同的元素，会完整保留上一轮（更低一位）排序得到的相对顺序，所有位迭代完成后，整个数组自然有序。
• 你产生“下一轮会重新排序所以低位可以跳过”的误解，本质是没搞懂稳定排序的作用：LSD每一轮的排序不是完全打乱所有元素重排，高位排序只会调整不同高位数值元素的顺序，高位相同的元素的相对顺序完全继承低位的排序结果，所以低位的排序结果是后续所有高位排序的基础，根本没办法跳过。
• 用一个简单的反例就能验证：假设待排序数组是[23, 12, 11]，如果直接跳过个位从十位开始排序：
  1. 提取所有元素的十位数值，分别是2、1、1
  2. 按十位做稳定排序后，十位为1的12和11会保留原有的先后顺序，最终得到排序结果[12, 11, 23]
  3. 这个结果显然错误，而这个错误从跳过个位排序的那一刻就已经注定，后续没有任何更高位的排序可以修正12和11的相对顺序。

内容的提问来源于stack exchange，提问作者JohnShallow