Реализация быстрой сортировки связанного списка?

Question

Мне нужно отсортировать дважды связанный список, используя что-либо, кроме сортировки вставкой, которая также выполняется в лучшее время, чем O (n ^ 2).Я думал об использовании быстрой сортировки, но у меня были проблемы с пониманием алгоритма.Не могли бы вы указать мне любую легкую для понимания документацию, которая могла бы помочь мне начать?

Answer 1

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

Здесь есть нить , которая имеет довольно хорошую работающую реализацию на c ++, которая может быть не самой легкой для чтения, если вы изучаете Java, но может быть хорошей отправной точкой.

На сайте также имеется превосходное описание алгоритма высокого уровня.