Рассмотренный метод можно обобщить следующим образом. Пусть по-прежнему ключи могут иметь значения только от 1 до n, но во входном наборе каждое значение может повторяться любое число раз, в том числе и ноль. Пусть исходный массив содержит m элементов, причем m>n. В этом случае с одним и тем же ключом может быть связано несколько элементов, и их нельзя поместить в одну ячейку результирующего массива.
Очевидным решением является использование вспомогательных списков для хранения элементов с одинаковыми ключами. Тем самым, приходим к использованию комбинированной структуры данных, а именно – массиву списков. Каждая ячейка массива соответствует одному конкретному значению ключа в диапазоне от 1 до n и хранит указатель на связанный список одноключевых элементов.
Тогда прежде всего надо распределить элементы входного набора по ячейкам результирующего массива в соответствии со значениями ключей, создавая и дополняя при необходимости вспомогательные списки. После этого, если требуется получить общий результирующий отсортированный набор данных, можно объединить все списки, добавляя в конец одного списка начало другого. Это легко реализуется, если в каждой ячейке результирующего массива хранить не только адрес первого элемента списка, но и адрес последнего элемента.
Пример. Пусть задан следующий входной набор из 15 элементов с диапазоном изменения ключей от 1 до 5 (в скобках указан ключ элемента):
Для программной реализации необходимо объявить массив указателей и ссылочный тип для поддержки списков. Дополнительные затраты памяти связаны в первую очередь с реализацией дополнительных списков, т.к. общее число элементов в этих списках равно m, а кроме того для каждого элемента надо 4 байта для адресных полей. Трудоемкость данного метода оценивается соотношением O(m+n), а при m>>n становится пропорциональной числу элементов m.
конец
конец
