什么是计数排序？

计数排序不是基于比拟的排序算法，其外围在于将输出的数据值转化为键存储在额定开拓的数组空间中。作为一种线性工夫复杂度的排序，计数排序要求输出的数据必须是有确定范畴的整数

计数排序最重要的一点，确定范畴的整数，比如说范畴 0-10，那么数组外面的值就要在 0-10 之间

栗子

序列：9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9，7，9

首先确定序列的范畴是 0-10，并且列出范畴的序列，如图 1

比方第一个整数是 9，那么数组下标为 9 的元素加 1

<img src=”https://noxussj.top:3000/28/1.png”></img>

图 1

第二个整数是 3，那么数组下标为 3 的元素加 1，如图 2

<img src=”https://noxussj.top:3000/28/2.png”></img>

图 2

以此类推反复遍历 …

最终遍历实现后状态如下，如图 3

<img src=”https://noxussj.top:3000/28/3.png”></img>

图 3

数组每一个下标地位的值，代表了在序列中对应整数呈现的次数

有了这个“统计后果”，排序就很简略了。间接遍历数组，输入数组元素的下标值，元素的值是几，就输入几次

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

最初输入的序列曾经是排好序的

<img src=”https://noxussj.top:3000/28/4.gif”></img>

这个时候可能会有人问，如果序列的最小值不是从 0 开始呢？

这个时候就要计算偏移量

如何计算偏移量？

以序列的最小值作为偏移量。比方最小值是 90，那么整数 95 对应的统计数组下标就是 95-90 = 5

<img src=”https://noxussj.top:3000/28/5.png”></img>

参考资料
值得珍藏的十大经典排序算法
漫画：什么是计数排序？

附加

• 此文章通过自媒体多平台公布，公布后不再进行保护，如对内容有任何异议能够到下方的 GitHub 中进行探讨
• 【继续保护 / 更新 500+ 前端面试题 / 笔记】https://github.com/noxussj/In…
• 【利用 THREE.JS 实现 3D 城市建模（珠海市）】https://3d.noxussj.top/