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