Сортировка одиночного связанного списка

Question

Как бы вы относитесь к одному связанному списку. (проблема здесь есть одно свойство + с помощью LinkedList для сортировки сложнее, чем массив) я имел бы видеть псевдокод ..

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

Спасибо!

Answer 1

Mergesorting включает в себя всего несколько простых шагов:

1. Проверьте, если список пустой или имеет один элемент. Если это так, верните список без изменений.

2. Разделить список пополам. Объединить обе части.

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

4. Возврат объединенного списка.

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

пример кода в Haskell:

import Data.List(splitAt) 

--Mergesorts a list by smallest element first. 
sort :: Ord a => [a] -> [a] 
sort = sortBy (<) 

--Generic sort that can sort in any order. 
sortBy :: (a -> a -> Bool) -> [a] -> [a] 
sortBy _ [] = [] 
sortBy _ [x] = [x] 
sortBy f xs = merge f (sortBy f first) (sortBy f second) 
    where 
     (first,second) = split xs 

--Splits a list in half. 
split :: [a] -> ([a],[a]) 
split xs = splitAt (halfLength xs) xs 

--Returns a lists length divided by two as a whole number (rounded). 
halfLength :: [a] -> Int 
halfLength = round . (/2) . fromIntegral . length 

--Merges two lists in the provided order. 
merge :: (a -> a -> Bool) -> [a] -> [a] -> [a] 
merge _ [] [] = [] 
merge _ [] (y:ys) = y:ys 
merge _ (x:xs) [] = x:xs 
merge f (x:xs) (y:ys) = 
    if f x y 
     then x : merge f xs (y:ys) 
     else y : merge f (x:xs) ys 

Answer 2

Сортировка Insertion и QuickSort могут выполняться в односвязном списке с той же эффективностью, что и на массиве.

Answer 3

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

В целом, это O (n log n) и O (n).

Answer 4

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

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

Здесь мы идем ...

1) Возьмите указатель на первый, второй и последний круг связанного списка.
2) Шаг второй указатель в списке, пока вы не нажмете термин, который больше, чем первый термин.
3) Поверните третий указатель назад по списку, пока не нажмете термин, который меньше первого. Этот шаг не работает с односвязным списком.
4) Поменяйте значения второго и третьего указателей.
5) Повторите шаги 2) - 5), пока второй и третий указатели не станут равными друг другу.
6) Вставьте первый член после второго указателя

-AT этого момента, связанный список разделен на:
[термины меньше, чем X] х [точки больше, чем X]

7) Повторите шаги 2) - 7) для [терминов меньше x] и [терминов больше, чем x], пока размер блока [terms ________ than x] не будет равен единице.

Пространство: 3 указателя на слой.
O (журнал (п))

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

---

отредактирована для форматирования и глупостей

Answer 5

Я думал об этом немного больше, и я думаю, что вы получите O (N журнал (п)) времени и O (1) с условием Merge Сортировать.

Давайте посмотрим ...
Возьмите список:
3 -> 2 -> 1 -> 5 -> 6 -> 4

Первый проход:
Установить указатель на 1-ой, 2-ой долгосрочный и третий термины
Установите меньшее значение между первым и вторым указателем, чтобы указать на более высокий термин.
Установите последний из двух терминов, чтобы указать на остальную часть исходного списка.
Повторяйте до конца списка.
2 -> 3 -> 1 -> 5 -> 4 -> 6

В этот момент упорядочивается каждая пара терминов.

Nth проход:
Установите указатель на 1, (2^(N-1)) е, и (2^(N)) + 1-го условия
Возьмите меньший оцененный узел и увеличиваем его указатель ,
Повторите процесс до тех пор, пока оба списка (длины 2^N) не будут исчерпаны, каждый раз добавляя меньший оцененный узел к предыдущему узлу с меньшими значениями.
Установите указатель на остальную часть исходного списка.
Повторяйте до конца списка.

0th проход: 3 -> 2 -> 1 -> 5 -> 6 -> 4 (каждый блок 1 термина заказан) (тривиальное)
1-й проход: 2 -> 3 -> 1 -> 5 -> 4 -> 6 (каждый блок из 2 членов заказан)
2-й проезд: 1 -> 2 -> 3 -> 5 -> 4 -> 6 (каждый блок из 4-х терминов заказывается)
Третий проход: 1 -> 2 -> 3 -> 4 -> 5 -> 6 (каждый блок из 8 членов упорядочен)

Время: log (n) проходит с n сравнениями для каждого прохода.
O (п журнал (п))

пространства: Pointer и целочисленные переменные
O (1)