#c #list #sorting
#c #Список #сортировка
Вопрос:
У меня есть связанный список элементов с индексом текстуры. Они не отсортированы. Мне нужно, чтобы они сортировали их так, чтобы индекс текстуры возрастал в порядке возрастания. Я всегда мог бы объявить другой список и ознакомиться с ним, но мне любопытно, как сортировать на месте. У кого-нибудь есть предложение или ссылка на то, с чего мне следует начать / что я должен начать искать, чтобы сделать это? Также я не использую список STL.
Спасибо!
Комментарии:
1. Почему бы не использовать
std::listвместо пользовательского списка? (И, конечно, зачем вообще использовать список? Возможно, это худший контейнер.)2. Сначала вам нужно объяснить, что означает «на месте» применительно к связанному списку. Без создания другого списка? Без повторной привязки элементов существующего списка? Что-то еще?
Ответ №1:
Сортировка связанного списка, вероятно, лучше всего выполняется с помощью mergesort (по-прежнему O(n log n) даже для списка), поскольку у вас нет доступа к случайным элементам. Если вы можете переключиться на std::list list::sort функцию, она позаботится об этом за вас.
Альтернативно используйте контейнер, не содержащий списка, вместо списка, и вы можете использовать любой метод сортировки, который вам нравится.
Ответ №2:
Сортировка связанного списка на месте не так эффективна из-за отсутствия произвольного доступа. Вы всегда можете использовать простой алгоритм, такой как пузырьковая сортировка, если вы знаете, что ваш список не будет очень длинным, или, возможно, если вы можете позволить себе немного дополнительной сложности, сортировка по вставке была бы лучше.
Альтернативный метод, который, вероятно, лучше, чем пытаться отсортировать связанный список, — это просто вставить каждый новый узел в нужное место, чтобы после добавления элемента список был отсортирован.