@rostyslavvvv

Какой алгоритм сортировки односвязного списка?

Какой должен быть алгоритм сортировку односвязного списка, вкратце), спасибо
  • Вопрос задан
  • 79 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Для списка отлично подойдет merge sort. В отличии от массива - для списков не понадобится второй массив для хранения временных результатов (вообще говоря, можно и массив без него сортировать, но получается медленнее и слишком сложный алгоритм).
Ответ написан
gbg
@gbg
Баянист. Тамада. Услуги.
Сначала сделать замечание о том, что в современной практике программирования, связный список не относят к первой линии выбора в качестве хранилища данных из-за его недружественности с кэшами и низкого быстродействия в результате.

Неплохо подойдет сортировка выбором:
-проходим до конца массива, отыскиваем максимум
-обмениваем максимум и первый элемент
-повторяем, но начинаем со второго элемента, потом с третьего и т.д.

Сложность этой сортировки в O-нотации равна N^2.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
DDoS-GUARD Ростов-на-Дону
от 70 000 до 120 000 ₽
OZON Москва
от 180 000 до 270 000 ₽
Softaria Новосибирск
от 100 000 до 150 000 ₽
20 апр. 2021, в 15:17
100000 руб./за проект
20 апр. 2021, в 14:52
10000 руб./за проект