为何我的Count Sort无法将元素放入dst[0]？求Bug定位

问题根源 #

代码中最后一个赋值循环的索引计算逻辑错误，导致所有元素的存储位置整体偏移一位。

在计数排序的累加阶段，ap[tmp]存储的是小于等于tmp + nfs的元素总个数。以测试用例为例，元素0对应的ap[0] = 1，代表有1个元素小于等于0。如果直接用这个值作为dst的索引，会把0放到dst[1]的位置；而正确的索引应该是ap[tmp] - 1（即0），这样才能匹配数组从0开始的索引规则。

修复代码 #

修改倒数第二个循环中的赋值语句：

// 原错误代码
dst[ap[arr[tmp] - nfs]] = arr[tmp];

// 修复后代码
dst[ap[arr[tmp] - nfs] - 1] = arr[tmp];

验证效果 #

修复后，测试用例的输出会变为：

1 2 3 4 5 6 7 8 9 10 
9 5 3 8 0 1 6 4 7 2 
0 1 2 3 4 5 6 7 8 9 

所有元素将正确填充到dst数组的对应位置，偏移问题彻底解决。

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