Отсортируйте единственный связанный список
Как Вы отсортировали бы единственный связанный список. (проблемой вот является единственное свойство +, использование LinkedList для сортировки более трудно, чем массив), я имел, любят видеть псевдо код..
попытайтесь сделать это эффективным как возможное в течение обоих времени и пространства.
Спасибо!
5 ответов
Слияние-сортировка включает всего несколько простых шагов:
Проверьте, пуст ли список или содержит один элемент. Если да, верните список без изменений.
Разделите список пополам. Отсортируйте обе части.
Объедините списки, многократно убирая меньший элемент из обоих списков. Поскольку списки частей уже отсортированы, это просто вопрос просмотра первых элементов в обоих списках и выбора меньшего.
Возвращаем объединенный список.
В результате вы получите связный список, отсортированный в порядке наименьшего элемента.
Пример кода на языке 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
Я думал об этом немного больше, и я думаю, что вы достигнете O (n log (n)) времени и O (1) пробела с помощью сортировки Merge.
Давайте посмотрим ...
Возьмите список:
3 -> 2 -> 1 -> 5 -> 6 -> 4
Первый проход:
Установите указатель для 1-го, 2-го и 3-го терминов
Установите меньший член между 1-м и вторым указателями, чтобы он указывал на больший член.
Установите последний из двух терминов так, чтобы он указывал на остальную часть исходного списка.
Повторяйте до конца списка.
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)
Сортировка вставкой и быстрая сортировка могут быть выполнены на односвязном списке с той же эффективностью, что и на массиве.
Поскольку связанный список - это просто количество элементов, на которые указывают другие элементы, вы можете построить массив указателей с временем O (n) и пространством O (n), отсортировать его, используя любой из отличных алгоритмов сортировки с O (n log n) времени и O (1) пространства, затем реконструируйте связанный список с нуля с O (n) временем и O (1) пространством.
В целом, это O (n log n) времени и O (n) пространства.
Я считаю, что вы можете сделать это с помощью in-place Quick sort.
Я ошибся. Это не работает с односвязным списком, потому что для этого нужно иметь возможность делать шаг назад по списку.
Поэтому главный вопрос заключается в том, как сделать быструю сортировку на месте.
Начнем...
1) Возьмем указатель на первый, второй и последний члены связанного списка.
2) Проведите второй указатель по списку, пока не попадется терм, который больше первого.
3) Переместите третий указатель назад по списку, пока не встретите терм, который меньше первого. Этот шаг не работает с односвязным списком.
4) Поменяйте местами значения второго и третьего указателей.
5) Повторяйте шаги с 2) по 5), пока второй и третий указатели не станут равны друг другу.
6) Вставьте первый терм после второго указателя
- В этот момент связный список разделен на:
[члены меньше x] x [члены больше x]
7) Повторяйте шаги с 2) по 7) для [терминов меньше x] и [терминов больше x], пока размер блока [терминов ________ больше x] не станет равным единице.
Пространство: 3 указателя на слой.
O(log(n))
Время: То же, что и Quick sort
O(n log(n)) в общем
O(n * n) в худшем случае (если список либо уже отсортирован, либо в обратном порядке)
Отредактировано для форматирования и глупости