355
правок
Изменения
Нет описания правки
Иногда надо отсортировать набор каких либо "сложных" данных, например, структур, в которых несколько полей, и сортировать надо по одному из полейних.В данном случае для [[Сортировка подсчетом|сортировки подсчетом]] предполагается, что величины, хранящиеся в данных ключах, позволяют сортировать подсчетомявляются целыми числами от 0 до k - 1.
Мы будем использовать все тот же алгоритм, что и для обыкновенных целых чисел, но с небольшой модификацией. Она необходима для разрешения следующей проблемы: разные структуры могут иметь одинаковые ключи. Нам надо каким-либо образом это учитывать.
Избавиться от этих недостатков можно следующим образом.
[[Файл:massA.png|400px800px|]]
* Подсчитаем количество разных ключей в списке (пусть их будет k), а также количество ключей каждого вида. Пусть массив Р[i] содержит количество ключей, равных i. Очевидно, что это делается за О(n).
* Пусть для определенности P[1], P[2], ..., P[k] не равны нулю. Тогда разобьем массив А на k блоков, длина каждого из которых равна соотв. P[1], P[2], ..., P[k], и поставим над первым элементом каждого блока по указателю point_i, который в дальнейшем будет указывать на первый свободный элемент в своем блоке i.
