8.5.3 计数排序
原书定位
印刷页P373起,对应PDF第385页。下文为目视整理的知识提要;完整内容见原书对照。
适用于范围较小的整数关键字。先统计频次数组 C[x],再求前缀和,使 C[x] 表示不大于 的记录数;从输入尾部向前,将记录放到 B[C[x]-1],再将 C[x] 减 1。
该回填方式稳定,时间 ,含输出缓冲的辅助空间 ,其中 为值域大小。含负数可用最小值作偏移;值域过大会浪费空间。
习题另有对每对元素比较来统计名次的方法,需 次比较,属于 ,不是上述按值域计频次的线性计数法;相等时的计数分配规则还决定稳定性。

计数、前缀和及稳定回填过程,原书P374。
对应练习
关联知识
原书对照
展开原书对照截图

