计数排序可通过键提取、离散化和前缀和映射实现对象稳定排序:先提取整型键并归一化,再离散化为秩,用计数数组转前缀和确定起始索引,逆序遍历写入保证稳定性。

计数排序本身适用于整数范围有限的场景,它天然不是为对象排序设计的,但可以通过“键提取 + 索引偏移 + 顺序收集”实现对变量对象的稳定排列。关键不在重写计数排序,而在用数组辅助构建稳定映射关系。
提取可计数的整型键并归一化
对象本身不可直接计数,需先定义一个整型排序键(如 age、score、priority 等),并确保其值域可控(例如 0–100)。若原始键有负数或跨度大,需做偏移与压缩:
- 找出最小值 minKey,用 key - minKey 将所有键映射到非负区间
- 若最大值过大(如超过 10⁶),应先离散化:收集所有唯一键 → 排序 → 映射为 0, 1, 2… 的秩(rank)
- 例如:[{name:'A', level:3}, {name:'B', level:-1}, {name:'C', level:3}] → 键集合 {-1,3} → rank{-1→0, 3→1} → 转为 [1, 0, 1]
用计数数组记录频次,再转为前缀和定位起始索引
设离散化后最大秩为 k,则新建长度为 k+1 的计数数组 count[0..k]:
- 遍历对象数组,对每个对象的秩 r 执行 count[r]++
- 将 count 改为前缀和:count[i] = count[0] + … + count[i−1](即秩小于 i 的元素总数)
- 此时 count[r] 表示:所有秩为 r 的元素在结果数组中的**起始下标**(因前缀和性质,天然保持输入顺序)
逆序遍历原数组,按秩写入结果位置(保障稳定性)
从原数组末尾开始向前扫描,对每个对象 obj(秩为 r):
- 取当前 count[r] 作为目标位置 index
- 将 obj 写入结果数组 output[index]
- 执行 count[r]--,为下一个同秩对象腾出前一位
- 逆序遍历是稳定性的核心:后出现的同秩对象被放在更靠后的位置,写入时反而先占高位,从而保持原始相对顺序
封装为通用函数,支持自定义键提取与比较约束
可封装成接受 arr、keyFn(返回整数)、domain?(预设值域)的函数:
- 若传入 domain = [min, max],跳过离散化,直接用 offset = min 做线性映射
- 若未传 domain,自动收集键、去重、排序、构建 rankMap
- 返回新数组,不修改原对象;若需就地排序,可额外提供 output buffer 参数
- 注意:该方法仅当键分布较密集(如 1000 个对象,键值仅取 50 个不同整数)时比快排更优;稀疏时离散化开销可能抵消优势











