Сортировка подсчета имеет временную сложность: O(n+k) n-> размер ввода k-> абс. диф. ч/б минимальное и максимальное значение. В некоторых случаях сортировка подсчетом лучше, чем алгоритм сортировки на основе сравнения. Присутствует ли он в std: sort в STL? если нет, есть ли причина? Также есть какая-либо функция для сортировки подсчета, доступная в STL?
Присутствует ли сортировка подсчетом в std: sort в STL?
Ответы (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).
person
mtk
schedule
26.04.2020
std::sortобнаруживать (довольно узкие и специализированные) условия, благоприятствующие сортировке подсчетом, и использовать их вместо алгоритма сортировки общего назначения. Я не знаю ни одной реализации, которая действительно делает это; если бы мне пришлось догадываться, почему, я бы подозревал, что это просто не стоит усилий - ситуации, когда применима сортировка подсчетом, на практике встречаются редко. Если вы знаете, что ваш алгоритм выиграет от этого, не стесняйтесь реализовать его или найдите существующую стороннюю реализацию. - person Igor Tandetnik schedule 06.05.2018