std 中是否存在计数排序：STL 中的排序？

Question

计数排序的时间复杂度：O(n+k) n-> 输入大小 k-> abs。差异。 b/w 最小值和最大值。在某些情况下，计数排序优于基于比较的排序算法它存在于 std: STL 中吗？如果没有，有什么理由吗？ STL 中还有任何用于计数排序的函数吗？

Answer 1

Is counting sort present in std: sort in STL?

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

if no, Is there any reason?

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

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

Also any function for counting sort available in STL?

C++ STL提供了最基本的数据结构——数组和向量，可以用来实现计数排序。

map也可以用来实现计数排序，但不会是O(n)了，因为map操作是O(logn)复杂度。

std 中是否存在计数排序：STL 中的排序？

Is counting sort present in std: sort in STL?

sorting

stl

counting-sort