基数排序中为何需要计算累积和？

这两步是基数排序实现稳定排序、精准定位元素最终位置的核心操作，拆解来看：

1. 统计数位计数：摸清当前数位的分布 #

第一步遍历数组统计每个数位（0-9）的出现次数，本质是搞清楚当前处理的数位（比如个位、十位）上，0到9每个数字各对应多少个元素。这是后续定位的基础——连每个数字的元素数量都摸不清，根本没法确定它们该放在输出数组的哪个区间。

比如处理数组[12, 22, 11]的个位时，统计后会得到：个位为1的有1个，个位为2的有2个，其余数位都是0。

2. 计算累积和：确定元素的精准位置（稳定排序的关键） #

计算累积和的核心作用，是把「每个数字的出现次数」转换成「每个数字在输出数组中的位置边界」。具体来说，累积后的count[d]代表所有数位≤d的元素总个数，这直接能帮我们确定：

• 数位为d的元素，在输出数组中的最后一个位置是count[d]-1
• 当我们从后往前遍历原数组时，每放置一个数位为d的元素，就把count[d]减1，这样下一个同数位的元素会自动放在前一个元素的前一位——这就保证了相同数位的元素，原数组中的相对顺序不变，也就是基数排序必须的「稳定排序」特性。

还是用刚才的例子：
统计后的count数组是[0,1,2,0,0,0,0,0,0,0]，计算累积和后变成[0,1,3,3,3,3,3,3,3,3]。
从后往前遍历原数组：

• 取11，个位是1，它的位置是count[1]-1=0，放入后count[1]减1变为0；
• 取22，个位是2，位置是count[2]-1=2，放入后count[2]减1变为2；
• 取12，个位是2，位置是count[2]-1=1，放入后count[2]减1变为1；
  最终输出数组是[11,12,22]，完美保留了原数组中12在22前面的顺序，实现了稳定排序。

结合代码理解 #

你的代码里：

• 第一段循环(arr[i] // place) % 10是取出当前元素在place（比如1对应个位，10对应十位）位置上的数字，然后统计每个数字的出现次数；
• 第二段循环从1到9累加count[i] += count[i-1]，就是计算累积和，把次数转换成位置边界。

如果跳过累积和这一步，你根本没法确定每个元素该放在输出数组的哪个位置，更没法保证排序的稳定性——这两步缺一不可。

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