Разница между способами сортировки связанных списков C++

Question

Я думал о способах сортировки связанного списка, и я придумал два разных способа (используя BubbleSort, потому что я относительно новичок в программировании, и это самый простой алгоритм для меня) , Пример структура:

struct node { 
    int value; 
    node *next; 
}; 

два различных метода:

• Переупорядочивание элементы списка
• делать что-то вроде swap(root->value, root->next->value)

Я сделал некоторые Google поиск по этому вопросу, и от По его мнению, первый способ кажется более популярным. По моему опыту, таким образом, что переупорядочение списка сложнее, чем просто замена фактических значений узлов. Есть ли какая-либо польза в перегруппировке всего списка, и если да, то что это?

Answer 1

я могу думать о двух преимуществ:

1) могут существовать другие указатели, указывающие на узлы в этом списке. Если вы измените список, эти указатели будут по-прежнему указывать на те же значения, на которые они указывали до сортировки; если вы меняете значения, они не будут. (Какой из этих двух вариантов лучше зависит от деталей вашего проекта, но есть проекты, в которых лучше, если они остаются указывать на одни и те же значения.)

2) Это не имеет большого значения для списка из простых ints, но в конечном итоге вы можете сортировать список более сложных вещей, так что обмен значениями очень дорог или даже невозможно.

Answer 2

Как ответили Beta, лучше переставить узлы (через следующие указатели), чем для обмена данными узла.

Если на самом деле используется сортировка пузырьков или любой вид, который «свопирует» узлы с помощью указателей, замените следующие (или головные) указатели на два узла, которые должны быть заменены сначала, а затем замените эти два узла следующими указателями. Это обрабатывает как случай соседнего узла, где вращаются 3 указателя, так и обычный случай, когда две пары указателей меняются местами.

Еще один простой способ - создать новый пустой список (node ​​* pNew = NULL;) для отсортированного списка. Удалите узел из первоначального списка по одному и вставьте этот узел в отсортированный список по порядку или сканируйте исходный список для самого большого узла, удалите этот узел и добавьте отсортированный список с этим узлом.

Если список большой и скорость важна, то более ранние сортировки слияний намного быстрее.