Сортировать один связанный список

Question

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

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

Спасибо!

Answer 1

Слияние объединяет всего несколько простых шагов:

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

Я думал об этом немного больше, и я думаю, что вы достигли условия O (n log (n)) времени и O (1) с помощью сортировки слиянием.

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

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

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

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

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

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

Пробел: указатель и целочисленные переменные
O (1)

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) Вставьте первый член после второго указателя

- В этот момент связанный список делится на:
[условия меньше x] x [слагаемые больше x]

7) Повторите шаги 2) - 7) для [слагаемых меньше x] и [слагаемых больше x] до размера [слагаемых ________ чем x]блок равен единице.

Пробел: 3 указателя на слой.
O (log (n))

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

---

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

Answer 5

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