277
правок
Изменения
м
<!-- Переписать первый абзац -->
Нет описания правки
Здесь <tex>A</tex> и <tex>B</tex> {{---}} массивы структур размера <tex>n</tex>, с индексами от <tex>0</tex> до <tex>n-1</tex>.
<tex>P</tex> {{---}} целочисленный массив размера <tex>k</tex>, с индексами от <tex>0</tex> до <tex>k-1</tex>, где <tex>k</tex> {{---}} количество различных ключей.
<code>
ComplexCountingSort
for i = 0 to k - 1
B[P[A[i].key]] = A[i];
P[A[i].key] = P[A[i].key] + 1;
</code>
Здесь шаги 3 и 4 из описания объединены в один цикл.
Обратите внимание, что в последнем цикле инструкцией
== Анализ ==
В первом алгоритме первые два цикла работают за <tex>\Theta(k)</tex> и <tex>\Theta(n)</tex>, соответственно; двойной цикл за <tex>\Theta(n + k)</tex>. Алгоритм имеет линейную временную трудоёмкость <tex>\Theta(n + k)</tex>. Используемая дополнительная память равна <tex>\Theta(k)</tex>.
== Источники ==
* [http://ru.wikipedia.org/wiki/Сортировка_подсчётом Википедия Сортировка подсчетом {{---}} Сортировка подсчетомВикипедия]* [http://en.wikipedia.org/wiki/Counting_sort Wikipedia Counting sort {{---}} Counting sortWikipedia]
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224{{---}}226.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
