首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >计数排序是否存在于std中:在STL中进行排序?

问计数排序是否存在于std中:在STL中进行排序?
EN

Stack Overflow用户
提问于 2018-05-06 11:44:43
回答 1查看 1.3K关注 0票数 1

计数排序具有时间复杂度: O(n+k) n->输入k-> abs的大小。迪夫。b/w最小值和最大值。在某些情况下,计数排序优于基于比较的排序算法,它是否存在于std: STL中的排序?如果没有,有什么理由吗?还有任何在STL中可用的计数排序的功能吗?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-04-26 07:39:27

计数排序是否存在于std中:在STL中进行排序?

不,它不存在。sort函数基于快速排序和其他启发式方法。

如果没有,有什么理由吗?

可能是因为它很容易实现。检查psuedocode

代码语言:javascript
复制
count = array of k+1 zeros
for x in input do
    count[key(x)] += 1

total = 0
for i in 0, 1, ... k do
    count[i], total = total, count[i] + total

output = array of the same length as input
for x in input do
    output[count[key(x)]] = x
    count[key(x)] += 1 

return output

还有任何在STL中可用的计数排序的功能吗?

C++ STL提供了基本的拟合数据结构-数组和向量,可用于实现计数排序。

map也可以用来实现计数排序,但是它不再是O(n)了,因为映射操作是O(logn)复杂性。

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/50199307

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档