Мне нужно отсортировать дважды Связанный список, используя что-либо, кроме вставки, которое также работает в лучшем случае, тогда O (n^2). Я думал об использовании quicksort, но имел проблемы с пониманием алгоритма. Не могли бы вы указать мне на любую легко понятную документацию, которая могла бы помочь мне начать?Внедрение быстрой сортировки связанного списка?
Я бы рекомендовал merge sort. Похоже, что это имеет больше смысла с дважды связанным списком, и у него есть время выполнения O (n log n). В принципе, вы находите середину и разбиваете список пополам, сортируете каждую половину сами по себе, а затем объединяете два в линейное время.
Существует нить here, которая имеет довольно хорошую рабочую реализацию на C++, которая может быть нелегкой для чтения, если вы изучаете Java, но может быть хорошей отправной точкой.
Существует также превосходное описание высокого уровня алгоритма на this site.
Важным моментом является то, что время выполнения * наихудшего случая * также является «O (n * log n)», в отличие от quicksort. Кроме того, его легко реализовать :) –
[видео визуализации Quicksort используя Hungerian народный танец] (http://www.youtube.com/watch?v=ywWBy6J5gz8). –
Вам разрешено извлекать его в другую структуру данных, чтобы сортировать его, или вам нужно сортировать его на месте? Извлечение в массив, выполнение быстрого сортировки и возврат в связанный список должно быть чем-то вроде 2n + nlogn, которое по-прежнему меньше квадрата n. – captncraig
Нет, я не могу использовать любую другую структуру данных для хранения узлов. –