Лучший алгоритм сортировки - Частично отсортирован связанный список

Question

Проблемно Учитывая отсортированный двукратно список ссылок и два числа C и K. Вы должны уменьшить данные узла с данными K по C и вставить новый узел, образованный на его правильное чтобы список оставался отсортированным.

Я бы думать о вставки рода для такой проблемы, потому что, сортировка вставкой в ​​любом случае выглядит, как показано кучу карт,

, которые частично отсортированных. Для сортировки вставки количество свопов эквивалентно числу инверсий. Количество сравнений равно количеству обменов + (N-1).

Итак, в заданной задаче (выше), если узел с данными K уменьшается на C, то отсортированный связанный список частично сортируется. Сортировка вставки наилучшим образом подходит.

Другим моментом является выбор алгоритма сортировки, если логика сортировки, применяемая для представления данных в массиве, наилучшим образом подходит, то такая же логика сортировки должна наилучшим образом соответствовать представленному представлению одинаковых данных.

Для решения этой проблемы, правильно ли мой метод рассмотрения при выборе сортировки вставки?

Answer 1

Возможно, вы имеете в виду что-то другое, но сортировка вставки не лучший алгоритм, потому что вам действительно не нужно ничего сортировать. Если есть только один элемент со значением K, то это не имеет большого значения, но в противном случае.

Так что я хотел бы предложить следующий алгоритм O (п), не обращая внимания крайние случаи для простоты:

1. Перейти вперед в списке, пока значение текущего узла> K - C.
2. Сохранить этот узел, все восстановленные узлы будут вставлены перед этим.
3. Продолжайте движение вперед, пока значение текущего узла равно < K
4. Пока значение текущего узла равно K, удалите узел, установите значение K - C и вставьте его перед сохраненным узлом. Это может быть оптимизировано дополнительно, так что вы только удаляете и вставляете операцию всего подсписного списка узлов, которые имеют значение K.

Answer 2

Если эти операции уменьшения могут быть собраны до того, как отсортированный список должен быть доступен, тогда вы можете просто удалить все уменьшенные узлы из списка. Затем сортируйте их и выполните двухстороннее слияние в список.

Если список должен поддерживаться в порядке после того, как каждый узел уменьшится, то выбора нет, но удалить узел с уменьшенным значением и снова вставить в порядок.

Выполнение этого с помощью линейного поиска колоды карт, вероятно, приемлемо, если только вы не используете какое-то чудовищное моделирование с использованием Монте-Карло, которое работает в течение нескольких часов или дня, поэтому оптимизация рассчитывается.

В противном случае мы будем иметь дело с необходимостью поддержания порядка в использовании упорядоченной структуры данных последовательности: сбалансированное двоичное дерево (красно-черное, splay) или список пропусков. Выньте узел из структуры, настройте значение, заново вставьте: O (log N).