8.5.3 计数排序

教材导航 · 第8章

原书定位

印刷页P373起,对应PDF第385页。下文为目视整理的知识提要;完整内容见原书对照。

适用于范围较小的整数关键字。先统计频次数组 C[x],再求前缀和,使 C[x] 表示不大于 xx 的记录数;从输入尾部向前,将记录放到 B[C[x]-1],再将 C[x] 减 1。

该回填方式稳定,时间 O(n+k)O(n+k),含输出缓冲的辅助空间 O(n+k)O(n+k),其中 kk 为值域大小。含负数可用最小值作偏移;值域过大会浪费空间。

习题另有对每对元素比较来统计名次的方法,需 n(n−1)/2n(n-1)/2 次比较,属于 O(n2)O(n^2),不是上述按值域计频次的线性计数法;相等时的计数分配规则还决定稳定性。

计数、前缀和及稳定回填过程

计数、前缀和及稳定回填过程,原书P374。

对应练习

8.5 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P373,PDF第385页

原书对照,原书P374,PDF第386页