单向链表归并排序（单链表实现排序）

大家好，我是讯享网，很高兴认识大家。

 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p>单链表的快速排序与归并排序</p>

讯享网

[2024-03-10: 今天试着重写了单链表的快速排序。觉今是而昨非。
下文的第一部分虽然代码很短（20行），但严格讲，不算是单链表的快速排序；而下文的第三部分，虽然算是单链表快速排序了，也很好理解，可是代码有近60行！且递归的函数中用了2个额外的局部变量，造成了内存的浪费。
而今天重写的这个版本，也还算好理解，代码行数减少到39行左右（其实还能减，不过为了可读性，先不减了），也没有了额外的局部变量。鉴于当前文章已经很长，就不贴在这里了，另开一贴《重写单链表的快速排序》。

[2022-04-04:
本文再次更新。至此，本文结构如下：
第一部分：介绍一种单链表的快速排序方法，缺点是略难理解和记忆，优点是短小精悍；（写于2018年）
第二部分：介绍一种单链表的归并排序方法，也略难实现，优点是性能远高于其他2种方法；（写于2021-11）
第三部分：介绍的是另一种单链表的快速排序，优点是很好理解与实现。（写于2022-04）
第四部分：比较上述三种方法。（写于2022-04）
]

首先，很容易想到的是：

要做一轮基准值定位，怎么做？
要做左子链表和右子链表的递归，怎么做？

第二个问题比较好回答，只要知道子链表的首尾节点，就可以做递归了。伪代码是：

讯享网

第一个问题才是要解决的难题。思路如下：
假设第一轮基准值定位做完了，我们需要有什么才能继续进行？
很显然，需要有左子链表和右子链表的各自的首尾节点。那么，左链表的首节点和右链表的尾节点，这2个一开始就有了。所以，需要有的是：左子链表的尾节点，和右子链表的首节点。而这2个节点分别位于基准值节点的左边和右边。

这个时候，有一个思路是：使用2个辅助指针 p1 和 p2.

讯享网

p1 是左子链表的最后一个节点，负责维护左子链表；
p2 是右子链表的最后一个节点，负责维护右子链表：它不断右移；其实，相当于p2在不断扩充右子链表，而待探索区不断缩小

当p2在探索区发现大值的时候，只需右移即可，将其纳入右子链表的范围；
当p2发现小值的时候，就要把p1右移一个（相当于扩大左子链表的范围），然后交换p1和p2的值（把小值和原来右子链表的最后一个节点交换），然后p2继续右移。

最后，还需要交换基准值和p1的值，因为，基准值从来没有动过，还在第一个节点的位置，而p1最终已经指向左子链表的最后一个位置，因此需要交换它们2个。

核心代码就是

问题是：按上面的算法，初始状态也是正确的吗？

这个时候可以举几个例子来验证了！（这是白板编程时的重要方法！）
比如：
15 -> 1 -> 20, *p1=15, *p2=1,
15 -> 1 -> 20, *p1=1, *p2=20,
15 -> 1 -> 20, *p1=1, *p2=NULL
此时，需交换start和p1的值，即：
1-> 15 -> 20
验证成功！

完整的代码是：

讯享网

以上内容基本是多年前写的；但是程序仍有一个比较大的缺陷，就是上面是用swap交换的节点内容，而不是交换节点。接下来介绍单链表的归并排序。
算法是：将一条链表，先找到中间节点，分成2个链表，然后不断递归地细分下去，直到“一节点即为一链表”为止；最后一路合并回最终的一条链表。

说来简单，中间还是有一些小的技巧和边界条件的考虑的。程序如下（注：LeetCode第148题）

第三种方法的原理是：

将单链表的头节点拿出来，作为一个基准节点；
遍历此单链表剩下的所有节点，将这些节点归类放到2个单链表中，一个存放所有比基准节点小的节点，另一个存放所有大于等于基准节点的节点；
递归处理第二步中的2个链表；
将递归处理好的这2个链表（此时已有序）和基准节点，再拼接成一个完整的单链表

具体代码如下：

讯享网

优点：短小精悍，核心代码只有10行左右；
缺点-1：使用的是交换节点内容的方法，并不是交换节点本身；
缺点-2：略难理解和记忆，不过真正理解了，也不难写；

优点：速度极快，比另外两方法的速度快3个数量级！
缺点：没有明显的缺点，理解也还算好理解，一定要说缺点，就是代码行数略多，但也就60行不到。

优点：很容易理解，实现也不难（虽也有小技巧）
缺点：当合并2个链表时，遍历了整个左子链表，导致其速度是三种方法中最慢的；但若此处做优化，则程序会更加冗余复杂；

下面看一下具体的执行时间。给定5万个乱序节点：

由上可见，

2种单链表的快速排序，对于5万乱序节点，速度都是在秒级；
第二种更好理解的单链表快速排序更慢一些，原因就是很多时候要对左链表全遍历以找到尾部节点；
归并排序的速度极快，只有1.8ms，相对于秒级，少了3个数量级！

为什么归并排序这么快呢？
从算法的角度来分析，归并排序和快速排序都是 , 并无差别，怎么会差3个数量级呢？
笔者仔细看了一下代码，觉得奥秘就在于这个归并算法的实现里全是指针操作。笔者猜测，这些指针应该都是存储在寄存器或临近CPU的cache里，因此操作起来极快；
相反，第一种单链表的快速排序需要交换节点的值，这需要对间接访问的内存进行读写，而第二种单链表快速排序可能因为涉及到临时节点的存取，也会涉及到对内存的读写，因此很可能也就影响到了速度。
如此看来，这个归并算法的实现还是蛮切合计算机体系结构的。

若考虑性能，推荐使用第二种方法；
若强制使用快速排序，仍推荐第一种方法
第三种方法鉴于其易理解性，值得了解

（完）

单向链表归并排序（单链表实现排序）

相关推荐