Подсчет сортировки присутствует в std: sort в STL?

Question

Счетная сортировка имеет временную сложность: O(n+k) n-> размер ввода k-> abs. разн. ч / б мин и макс. В некоторых случаях подсчет сортировки лучше, чем алгоритм сортировки на основе сравнения. Он присутствует в std: sort в STL? если нет, есть ли причина? Также любая функция для подсчета сортировки доступна в STL?

Answer 1

Присутствует ли подсчет сортировки в std: sort в STL?

Нет, его нет. В sort функция основана на быстрой сортировке и других эвристиках.

если нет, есть ли причина?

Наверное, потому, что это легко реализовать. Проверить псевдокод

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).