Intereting Posts
C – лучший способ замены Почему в первый раз программа C работает, она работает на 10x медленнее Как улучшить определение размера буфера для печати различных целых типов? Есть ли способ принудительно сохранить переменную в кеше в C? Настроить указатели на динамическую матрицу Шаг ссылки не может найти символы (компилятор XC8) как найти второй самый большой элемент с помощью программы c без использования массива Что произойдет, если мой указатель пересечет границы массива? Последовательная связь Ubuntu: считывает сбой, а затем приходит сразу Выполнение кода перед main () Ошибка компилятора C – инициализатор не постоянный с использованием parsingки сбоев сегментации pi2-python (non root) для GPIO Передавать детям ребенка родителям stdin Как я могу узнать, какой тип информации об отладке находится в объектном файле ELF? Эквиваленты для _countof MSVC в других компиляторах?

Сортировка связанных списков в C

Мне было предложено написать функцию, которая принимает 3 несортированных связанных списков и возвращает один отдельный отсортированный список, который объединяет все три списка. Каков наилучший способ, о котором вы можете думать?

У меня нет ограничений памяти, но что бы вы сделали с ограничениями памяти без ограничений?

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

В отличие от большинства алгоритмов сортировки O (n log n), сортировка слияния может эффективно работать в связанных списках. На высоком уровне интуиция за сортировкой слияния в связанном списке выглядит следующим образом:

  1. В базовом случае, если список имеет нуль или один элемент, он уже отсортирован.
  2. Иначе:
    1. Разделите список на два списка примерно равного размера, возможно, переместив нечетные элементы в один список и даже элементы в другой.
    2. Рекурсивно используйте сортировку слияния для сортировки этих списков.
    3. Примените шаг слияния, чтобы объединить эти списки в один отсортированный список.

Алгоритм слияния в связанных списках действительно красив. Псевдокод работает примерно так:

  1. Инициализируйте пустой связанный список, содержащий результат.
  2. Пока оба списка не пустые:
    1. Если первый элемент первого списка меньше первого элемента второго списка, переместите его в конец списка результатов.
    2. В противном случае переместите первый элемент второго списка в конец списка результатов.
  3. Теперь, когда ровно один список пуст, переместите все элементы из второго списка в конец списка результатов.

Это можно сделать для выполнения в O (n) времени, поэтому общая сложность сортировки слияния – O (n log n).

После того, как вы отсортировали все три списка самостоятельно, вы можете применить алгоритм слияния, чтобы объединить три списка в один окончательный отсортированный список. В качестве альтернативы вы можете рассмотреть вопрос о объединении всех трех связанных списков, а затем использовать гигантский сортимент сортировки слияния для сортировки всех списков одновременно. Для этого нет четкого «правильного пути»; это действительно зависит от вас.

Вышеупомянутый алгоритм работает в Θ (n log n) времени. Он также использует только память Θ (log n), поскольку он не выделяет никаких новых связанных ячеек списка и просто нуждается в пространстве в каждом кадре стека для хранения указателей в разных списках. Поскольку глубина рекурсии равна Θ (log n), использование памяти также равно Θ (log n).


Другая сортировка O (n log n), которую вы можете реализовать в связанных списках, представляет собой модификацию quicksort . Хотя версия quicksort со связанными списками быстро (ожидается ожидаемый O (n log n)), это не так быстро, как версия на месте, которая работает на массивах из-за отсутствия локальных эффектов из элементов массива, которые хранятся смежно , Тем не менее, это очень красивый алгоритм применительно к спискам.

Интуиция за быстрой сортировкой выглядит следующим образом:

  1. Если у вас есть нулевой или одноэлементный список, список сортируется.
  2. Иначе:
    1. Выберите элемент списка, который будет использоваться в качестве точки опоры.
    2. Разделите список на три группы – элементы меньше, чем точка поворота, элементы, равные оси, и элементы, которые больше, чем точка поворота.
    3. Рекурсивно сортировать меньшие и большие элементы.
    4. Сконцентрируйте три списка как меньше, затем равны, а затем больше, чтобы вернуть общий отсортированный список.

Одним из приятных аспектов версии quicksort с связанным списком является то, что шаг разбиения значительно проще, чем в случае с массивом. После того, как вы выбрали точку поворота (подробности немного позже), вы можете сделать шаг разбиения, создав три пустых списка для списков с меньшим, чем равным и большим, а затем выполнив линейное сканирование по исходному связанному список. Затем вы можете добавить / добавить каждый узел связанного списка в связанный список, соответствующий исходному ведру.

Одной из проблем при получении этой работы является выбор хорошего элемента поворота. Хорошо известно, что quicksort может выродиться до O (n 2 ) времени, если выбор стержня является плохим, но также известно, что если вы произвольно выбираете элемент поворота, время выполнения O (n log n) с большой вероятностью. В массиве это легко (просто выберите индекс случайных массивов), но в связанном списке дело сложнее. Самый простой способ сделать это – выбрать случайное число между 0 и длиной списка, а затем выбрать этот элемент списка в O (n) времени. Кроме того, есть несколько довольно classных методов для выбора элемента случайным образом из связанного списка; описан один такой алгоритм .


Если вам нужен более простой алгоритм, который нуждается только в пространстве O (1), вы также можете рассмотреть возможность сортировки связанных списков. Хотя сортировка вставки проще реализовать, она работает в O (n 2 ) раз в худшем случае (хотя она также имеет наилучшее поведение O (n)), поэтому, вероятно, это не очень хороший выбор, если вы специально не хотите слияния Сортировать.

Идея алгоритма сортировки вставки следующая:

  1. Инициализируйте пустой связанный список, содержащий результат.
  2. Для каждого из трех связанных списков:
    1. Хотя этот связанный список не пуст:
      1. Просмотрите список результатов, чтобы найти место, где принадлежит первый элемент этого связанного списка.
      2. Вставьте элемент в это место.

Другой алгоритм сортировки O (n 2 ), который может быть адаптирован для связанных списков, – это сортировка . Это можно реализовать очень легко (при условии, что у вас есть дважды связанный список), используя этот алгоритм:

  1. Инициализируйте пустой список, содержащий результат.
  2. Хотя список ввода не пуст:
    1. Сканирование через связанный список, который ищет самый маленький оставшийся элемент.
    2. Удалите этот элемент из связанного списка.
    3. Добавьте этот элемент в список результатов.

Это также работает в O (n 2 ) времени и использует только O (1) пространство, но на практике оно медленнее, чем сортировка вставки; в частности, он всегда работает в Θ (n 2 ) времени.


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

В качестве простого примера давайте посмотрим, как мы можем реализовать сортировку дерева с помощью связанных связанных ячеек. Идея такова. Когда ячейки связанного списка хранятся в связанном списке, следующий и предыдущий указатели имеют свое первоначальное значение. Однако наша цель будет заключаться в том, чтобы итеративно вытащить связанные ячейки списка из связанного списка, а затем переинтерпретировать их как узлы a в двоичном дереве поиска, где следующий указатель означает «правое поддерево», а предыдущий указатель означает «левое поддерево». Если вам разрешено это сделать, вот действительно classный способ реализовать сортировку дерева:

  1. Создайте новый указатель на связанную ячейку списка, которая будет служить указателем на корень дерева.
  2. Для каждого элемента двусвязного списка:
    1. Удалите эту ячейку из связанного списка.
    2. Рассмотрев эту ячейку как узел BST, вставьте узел в двоичное дерево поиска.
  3. Сделайте прогулку в BST. Всякий раз, когда вы посещаете узел, удалите его из BST и вставьте его обратно в двусвязный список.

Это выполняется в наилучшем случае O (n log n) и в худшем случае O (n 2 ). Что касается использования памяти, первые два шага требуют только O (1) памяти, так как мы перерабатываем пространство с более старых указателей. Последний шаг можно сделать и в O (1) пространстве, используя некоторые особенно умные алгоритмы.

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


Надеюсь это поможет!

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

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

Затем просто создайте четвертый «пустой» список, который по самой природе «пуст» «сортируется», а затем трижды вызывает ваш метод с каждым несортированным списком.

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

Я думал, что вы можете применить быстрый сорт. Это почти то же самое, что и сортировка слияния, только разница в том, что вы сначала разделили, а затем объединили, где whit quicksort вы сначала «сменили», а затем разделили. Если вы выглядите немного по-другому, вы можете объединить quicksort в противоположном направлении

Сортировка слиянием:

split -> recursion -> merge

быстрая сортировка:

umnerge (напротив слияния) -> recursion -> join (напротив split)

Алгоритм mergesort, описанный в популярном сообщении @templatetypedef, не работает в O (n lg n). Поскольку связанный список не является произвольным доступом, шаг 2.1. Split the list into two lists of roughly equal size самом деле означает общий алгоритм O (n ^ 2 log n) для сортировки списка. Подумайте об этом немного.

Вот ссылка, которая использует mergesort для сортировки связанного списка, сначала считывая элементы в массив – http://www.geekviewpoint.com/java/singly_linked_list/sort .

Для связанных списков нет эффективных алгоритмов сортировки. создавать массив, сортировать и перестраивать.