知识卡片
前缀计数给每个值分配位置
把出现次数转成累计数量后,某值累计数减一指向该值最后可放的位置。倒序扫描原输入,放到这个位置再把计数减一,便为同键元素从后向前分配槽位。
倒序输入配合末位置递减,保留同键先后,因此可推广到带键记录。原书代码仍是[]int,“可排序对象”说明的是这种位置方法,并未真的给出对象容器;只重写数值数量不能保留原对象身份。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
倒序遍历原数组 nums 每个元素num ,在每轮迭代中执行以下两步。 1. 将num 填入数组res 的索引prefix[num] - 1 处。 2. 令前缀和prefix[num] 减小 ,从而得到下次放置num 的
参考来源
- 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[4817,4927))
- 结论依据:实际完整countingSort前缀/倒序/写res代码,稳定性来自具体方向配合。
- 原始内容:倒序遍历原数组 nums 每个元素num ,在每轮迭代中执行以下两步。 1. 将num 填入数组res 的索引prefix[num] - 1 处。 2. 令前缀和prefix[num] 减小 ,从而得到下次放置num 的