是否在std中存在排序：在STL中排序？

Question

计数排序具有时间复杂度：O（n + k）n->输入k->绝对大小。差异黑白最小值和最大值。在某些情况下，计数排序优于基于比较的排序算法它是否存在于std：sort in STL中？如果没有，那有什么原因吗？还有STL中可用的计数排序功能吗？

Answer 1

是否在std中存在排序：在STL中排序？

不，它不存在。 sort功能基于快速排序和其他启发式。

如果否，有什么原因吗？

可能是因为它易于实现。检查sort

psuedocode

还有STL中可用的计数排序功能吗？

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

[

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

也可以用于实现计数排序，但是它将不再是O（n），因为映射操作具有O（logn）复杂性。