Почему бы нам не использовать быструю сортировку в связанном списке?

Алгоритм быстрой сортировки можно разделить на следующие шаги

1. Определить опору.

2. Разделите связанный список на основе сводки.

3. Разделите связанный список рекурсивно на 2 части.

Теперь, если я всегда выбираю последний элемент как сводный, то для идентификации сводного элемента (1-й шаг) требуется $\mathcal O(n)$ времени.

После определения сводного элемента мы можем сохранить его данные и сравнить их со всеми остальными элементами, чтобы определить правильную точку разбиения (2-й шаг). Каждое сравнение будет занимать $\mathcal O(1)$ время, поскольку мы храним сводные данные, а каждый обмен занимает время. Таким образом, в общей сложности требуется время для элементов.$\mathcal O(1)$$\mathcal O(n)$$n$

Таким образом, отношение повторения:

$T(n) = 2T(n/2) + n$ что такое же, как в сортировке слиянием со связанным списком.$\mathcal O(n \log n)$

Так почему сортировка слиянием предпочтительнее быстрой сортировки для связанных списков?

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

Из-за этого быстрая сортировка не является естественным выбором для связанного списка, в то время как сортировка слиянием имеет большое преимущество.

Обозначения Ландау могут (более или менее, потому что быстрая сортировка по-прежнему равна ), но константа намного выше.$\mathcal O(n^2)$

В среднем случае оба алгоритма находятся в поэтому асимптотический случай один и тот же, но предпочтение строго обусловлено скрытой константой, и иногда возникает проблема стабильности (быстрая сортировка по своей природе нестабильна, mergsort стабильна).$\mathcal O(n\log n)$

Вы можете быстро отсортировать связанные списки, однако вы будете очень ограничены с точки зрения выбора сводки, ограничивая вас сводками рядом с передней частью списка, что плохо для почти отсортированных входных данных, если только вы не хотите перебирать каждый сегмент дважды (один раз для сводки и один раз за раздел). И вам нужно будет сохранить стек границ разделов для списков, которые вам еще нужно отсортировать. Этот стек может вырасти до когда выбор оси вращения плох, а сложность времени возрастает до O ( n 2 ) .$O(n)$$O(n^2)$

$O(1)$

$2^{64}$$O(1)$

head = list.head;
head_array = array of 64 nulls

while head is not null
    current = head;
    head = head.next;
    current.next = null;
    for(i from 0 to 64)
        if head_array[i] is null
            head_array[i] = current;
            break from for loop;
        end if
        current = merge_lists(current, array[i]);
        head_array[i] = null;
     end for
end while

current = null;
for(i from 0 to 64)
    if head_array[i] is not null
        if current is not null
            current = merge_lists(current, head_array[i]);
        else
            current = head_array[i];
        end if
     end if
 end for

 list.head = current;

Это алгоритм, который ядро ​​Linux использует для сортировки связанных списков. Хотя с некоторыми дополнительными оптимизациями, такими как игнорирование previousуказателя во время всего, кроме последней операции слияния.

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

program untitled;


type TData = longint;
     PNode = ^TNode;
     TNode = record
                data:TData;
                prev:PNode;
                next:PNode;
             end;

procedure ListInit(var head:PNode);
begin
  head := NIL;
end;

function ListIsEmpty(head:PNode):boolean;
begin
  ListIsEmpty := head = NIL;
end;

function ListSearch(var head:PNode;k:TData):PNode;
var x:PNode;
begin
  x := head;
  while (x <> NIL)and(x^.data <> k)do
     x := x^.next;
  ListSearch := x;
end;

procedure ListInsert(var head:PNode;k:TData);
var x:PNode;
begin
  new(x);
  x^.data := k;
  x^.next := head;
  if head <> NIL then
     head^.prev := x;
   head := x;
   x^.prev := NIL;
end;

procedure ListDelete(var head:PNode;k:TData);
var x:PNode;
begin
   x := ListSearch(head,k);
   if x <> NIL then
   begin
     if x^.prev <> NIL then
        x^.prev^.next := x^.next
      else 
        head := x^.next;
     if x^.next <> NIL then
        x^.next^.prev := x^.prev;
     dispose(x);
   end;
end;

procedure ListPrint(head:PNode);
var x:PNode;
    counter:longint;
begin
  x := head;
  counter := 0;
  while x <> NIL do
  begin
    write(x^.data,' -> ');
    x := x^.next;
    counter := counter + 1;
  end;
  writeln('NIL');
  writeln('Liczba elementow listy : ',counter);
end;

procedure BSTinsert(x:PNode;var t:PNode);
begin
  if t = NIL then
    t := x
  else
    if t^.data = x^.data then
            BSTinsert(x,t^.prev)
        else if t^.data < x^.data then
            BSTinsert(x,t^.next)
        else
            BSTinsert(x,t^.prev);
end;

procedure BSTtoDLL(t:PNode;var L:PNode);
begin
   if t <> NIL then
   begin
     BSTtoDLL(t^.next,L);
     ListInsert(L,t^.data);
     BSTtoDLL(t^.prev,L);
   end;
end;

procedure BSTdispose(t:PNode);
begin
   if t <> NIL then
   begin
    BSTdispose(t^.prev);
    BSTdispose(t^.next);
    dispose(t);
   end; 
end;

procedure BSTsort(var L:PNode);
var T,S:PNode;
    x,xs:PNode;
begin
  T := NIL;
  S := NIL;
  x := L;
  while x <> NIL do
  begin
    xs := x^.next;
    x^.prev := NIL;
    x^.next := NIL;
    BSTinsert(x,t);
    x := xs;
  end;
  BSTtoDLL(T,S);
  BSTdispose(T);
  L := S;
end;

var i : byte;
    head:PNode;
    k:TData;
BEGIN
  ListInit(head);
  repeat
     writeln('0. Wyjscie');
     writeln('1. Wstaw element na poczatek listy');
     writeln('2. Usun element listy');
     writeln('3. Posortuj elementy drzewem binarnym');
     writeln('4. Wypisz elementy  listy');
     readln(i);
     case i of
     0:
     begin
       while not ListIsEmpty(head) do
            ListDelete(head,head^.data);
     end;
     1:
     begin
       writeln('Podaj element jaki chcesz wstawic');
       readln(k);
       ListInsert(head,k);
     end;
     2:
     begin
       writeln('Podaj element jaki chcesz usunac');
       readln(k);
       ListDelete(head,k);
     end;
     3:
     begin
       BSTsort(head);
     end;
     4:
     begin
        ListPrint(head);    
     end
     else
        writeln('Brak operacji podaj inny numer');
     end;
  until i = 0;  
END.

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

Быстрая сортировка
Может быть, я покажу шаги для быстрой сортировки

Если список содержит более одного узла

1. Сводная выборка
   
2. Список разделов на три подсписка.
   Первый подсписок содержит узлы с ключами, меньшими, чем сводный ключ.
   Второй подсписок содержит узлы с ключами, равными сводному ключу.
   Третий подсписок содержит узлы с ключами, превышающими сводный ключ
   
3. Рекурсивные вызовы для списков, которые содержат узлы, не равные узлу сводки
   
4. Объединить отсортированные подсписки в один отсортированный список
   

Объявление 1.
Если мы хотим выбрать pivot fast, выбор ограничен.
Мы можем выбрать головной узел или хвостовой узел.
Наш список должен иметь указатель на узел, если мы хотим, чтобы наш pivot
был быстро доступен, в противном случае мы должны искать узел.

Объявление 2.
Мы можем использовать операции очереди для этого шага.
Сначала мы удаляем узел из исходного связанного списка,
сравниваем его ключ с ключом поворота и ставим в очередь узел с правильным подсписком.
Списки создаются из существующих узлов, и нет необходимости
выделять память для новых узлов.

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