排序链表的方式之间的区别c ++

Question

我在考虑对链表进行排序的方法，然后想到了两种不同的方法（使用 BubbleSort，因为我在编程方面相对较新，而且它对我来说是最简单的算法）。示例结构：

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

两种不同的方法：

我搜索了一下Google这个问题，看来第一种方法比较流行。根据我的经验，重新排列列表比简单地交换实际节点值要复杂得多。重新排列整个列表有什么好处吗？如果有，那是什么？

Answer 1

我能想到两个优点：

1) 可能存在其他指针，指向此列表中的节点。如果重新排列列表，这些指针仍将指向它们在排序前指向的相同值；如果你交换价值，他们不会。（这两者中哪一个更好取决于您的设计细节，但有些设计如果它们保持指向相同的值则更好。）

2) 对于纯粹的整数列表并不重要，但最终您可能会对更复杂事物的列表进行排序，因此交换值非常昂贵甚至不可能。

Answer 2

正如 Beta 的回答，重新排列节点（通过下一个指针）比交换节点数据更好。

如果实际使用冒泡排序或通过指针 "swaps" 节点的任何排序，请首先交换指向要交换的两个节点的下一个（或头）指针，然后交换这两个节点的下一个指针。这处理了 3 个指针旋转的相邻节点情况，以及交换 2 对指针的正常情况。

另一个简单的选择是为排序后的列表创建一个新的空列表(node * pNew = NULL;)。一次从原始列表中删除一个节点，然后将该节点按顺序插入到排序列表中，或者扫描原始列表以查找最大节点，删除该节点并在排序列表中添加该节点。

如果列表很大并且速度很重要，那么自下而上的合并排序要快得多。

Difference between ways of sorting linked lists c++