Блог

Я пытаюсь создать функцию сортировки на c , которая сортирует объект связанного списка с помощью сортировки по куче, но я не уверен, с чего начать. Кто-нибудь может подсказать мне, как это сделать? Я даже не уверен, как бы я отсортировал связанный список

Heapsort работает путем создания кучи из данных. Кучу эффективно создавать только тогда, когда у вас есть произвольный доступ к каждому элементу.

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

Последним шагом будет преобразование вашего массива указателей обратно в связанный список.

Лучшим методом сортировки для связанного списка является сортировка по вставке — не в последнюю очередь потому, что вы можете выполнять сортировку как часть insert() функции вашей реализации связанного списка.

Я должен согласиться с ответом Сарнольдса. Устанавливать связанный список в куче крайне неэффективно по ряду причин, но первая заключается в том, что они должны были быть отсортированы при первоначальном размещении. Тем не менее, если бы я собирался попробовать, я бы создал ArrayList<T> links загрузку всех ссылок в него. Затем вы можете собирать это в кучи и сортировать их. Как только вы закончите, просто перезагрузите свой связанный список, начиная с заголовка.

Сортировка по куче хороша по двум причинам —
1 — Это действующий алгоритм.
Двухкратная сложность O (nlogn)

O (nlogn) происходит из-за характера произвольного доступа к массиву, но если вы используете связанный список, то вы не получите преимущества произвольного доступа к массиву. Следовательно, временная сложность станет O (n ^ 2). Это не подходит для сортировки.

Я порекомендую вам использовать алгоритм сортировки слиянием для связанного списка.