-1. 无聊的统计
本文章共计 1 小时 34 分钟, 1761 个字
0. 简介
本人在学校看某算法书学会计数排序后修改逻辑后发明了更简洁的计数排序算法 but 不稳定，将复杂度从 O(3n+k)O(3n+k)O(3n+k) 变成了 O(2n+k)O(2n+k)O(2n+k) 虽然省略常数项后复杂度没变，让运行速度提高了
1.计数排序
1.1 可供快速了解的视频
1.2 可供快速了解的文章
1.2.1 概述
计数排序是一种非比较型排序算法，它的核心思想是通过统计每个元素出现的次数，利用这些计数信息来直接确定每个元素在排序结果中的位置。
它适用于小整数排序（重点！！！），当数据的范围不大时，效率非常高。
1.2.2 算法思想
1. 找出待排序序列中的最大值和最小值
2. 统计每个元素出现的次数，存储在计数数组中
3. 将计数数组进行前缀和处理，使每个位置的值代表“该元素之前有多少个元素”
4. 从原序列的末尾开始遍历，根据计数数组确定每个元素在结果中的正确位置
1.2.3 时间复杂度
项目 复杂度 时间复杂度 O(3n+k)O(3n + k)O(3n+k) 空间复杂度 O(2n+k)O(2n + k)O(2n+k) 稳定性 稳定排序
> 其中，nnn 为待排序元素个数，kkk 为数据范围。
2 自创计数排序变式
2.1 自创计数排序变式思路
在学会计数排序后，我发现其实 “反向遍历 + 前缀和”的步骤虽然保证了稳定性，但也增加了多余的遍历次数。
于是我思考我不在意稳定性的话能否省略前缀和计算，直接利用计数数组构造结果？
答案是可以的，这就产生了下面这个“简洁版计数排序”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.2 我的自创计数排序变式代码（PYTHON）
2.3 算法解析
1. 统计出现次数
首先遍历输入数组 a，每出现一个数，就让计数数组 x 对应下标处加一。
例如输入 [4,2,2,8,3,3,1]，计数后得到：[1,2,2,1,0,0,0,1,0,...]
2. 按顺序生成结果
接着从小到大遍历 x，当 x[i] > 0 时，说明数字 i 出现过，直接将 i 连续填充到结果数组 b 中：
b[j:j+c+1] = [i]*c
这里 j 是当前写入位置，c 是出现次数。
每写完一段，就把 j 往后移动 c 位。
3. 输出
最终 b 就是排序好的数组。
由于省略了“前缀和”和“反向遍历”，实现逻辑更简单，执行速度更快。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.4 时间与空间复杂度
项目 复杂度 时间复杂度 O(2n+k)O(2n + k)O(2n+k) 空间复杂度 O(2n+k)O(2n + k)O(2n+k) 稳定性 不稳定 （如何呢，又能怎）
3.总结
我的自创计数排序变式，通过省略前缀和将复杂度从 O(3n+k)O(3n + k)O(3n+k) 降为 O(2n+k)O(2n + k)O(2n+k)。
虽然牺牲了稳定性，但换来了更高的运行效率和更简洁的代码结构，很赚了好吧。
