单链表的快速排序与归并排序

单链表的快速排序与归并排序

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

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

第一部分 单链表的快速排序

首先，很容易想到的是：

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

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

    void quick_sort_link(Node *start, Node *end=NULL);
1

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

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

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

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

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

核心代码就是

    int t = start->data;  // 基准值
    while (p2 != end) {
        if (p2->data < t) {
            p1 = p1->next;
            swap(p1->data, p2->data);
        }
        p2 = p2->next; 
    }
    swap(start->data, p1->data); 
1
2
3
4
5
6
7
8
9

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

这个时候可以举几个例子来验证了！（这是白板编程时的重要方法！）
比如：
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
验证成功！

完整的代码是：

    #include <iostream>
    using namespace std;

    // int array[] = {34, 54, 23, 12, 23, 99, 45, 89, 99, 13, 14, 100};  // 12, 13, 14, 23, 34, 45, 54, 89, 99, 100
    int array[] = {10, 2, 50, 3, 20};

    struct Node {
        int data;
        struct Node* next; 
        Node(int d):data(d), next(NULL){}
    };
    
    void print_list(Node* head)
    {
        while (head != NULL && head->next != NULL) {
            cout << head->data << "->";
            head = head->next;
        }
        if (head && head->next == NULL) {
            cout << head->data << endl;
        }
    }
    
    Node* create_list(int* array, int size)
    {
        if (size == 0) return NULL;
        
        int i = 0;
        Node* head = new Node(array[i++]);
        Node* p = head;        
        while (i < size) {
            p->next = new Node(array[i++]);
            p = p->next;
        }
        return head;
    }

    /*
        基准值是start->data;
        将原链表看作2个链表：左链表和右链表，左链表最后一个节点就是基准值
        p1是左链表的最后一个节点，p2是右链表的最后一个节点
        因此，当遇到大于基准值的时候，p2一直右移；
        当遇到小于基准值的时候，p1右移一个，再交换p1和p2的值，相当于维持了p1和p2的定义
        一轮循环的最后，p2到达了end的位置，此时，应该交换p1和start节点的值，这时才是真正的一轮处理的结束
        下一轮，就递归调用 qs(start, p1) 和 qs(p1->next, end) 了。
    */
    void quick_sort_list(Node* start, Node* end=NULL)
    {
        if (start == NULL || start == end) return;
        
        Node* p1 = start;
        Node* p2 = start->next; 
        
        while (p2 != end) {
            if (p2->data < start->data) {
                p1 = p1->next;
                swap(p1->data, p2->data);
            }
            p2 = p2->next;
        }
        swap(p1->data, start->data);
        
        quick_sort_list(start, p1);
        quick_sort_list(p1->next, end);
    }

    int main()
    {
        int size = sizeof(array)/sizeof(int);
        Node* head = create_list(array, size);
        print_list(head);
        
        quick_sort_list(head);
        print_list(head);
        
        return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

第二部分 单链表的归并排序

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

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

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr && l2 == nullptr) return nullptr;
        if (l1 && l2 == nullptr) return l1;
        if (l1 == nullptr && l2) return l2;
        
        ListNode * head = nullptr;
        ListNode * p = nullptr;
        
        while(l1 && l2) {
            if (l1->val > l2->val) swap(l1, l2);
                
            if (head) {
                p->next = l1; 
                p = p->next;
                l1 = l1->next; 
            }
            else {  // head is nullptr 
                head = l1;
                p = head;
                l1 = l1->next;
            }
        }
        
        if (l1) p->next = l1;
        else p->next = l2;
        
        return head;
    }

    ListNode * _sort(ListNode * beg, ListNode * end) {
        if (beg == nullptr || beg == end || beg->next == nullptr) return beg;
        
        ListNode * p1 = beg; 
        ListNode * p2 = beg->next;  // note here, a skill
        
        // find out the middle node of current list
        while (p2!=end) {
            p1 = p1->next; 
            p2 = p2->next; 
            if (p2 == end) break;
            p2 = p2->next; 
        }
        
        // p1 is the middle node, p1->next is the start node of the second list
        ListNode * secondStart = p1->next; 
        p1->next = nullptr;
        
        ListNode * h1 = _sort(beg, p1);
        ListNode * h2 = _sort(secondStart, end);
        ListNode * h = mergeTwoLists(h1, h2);
        return h;
    }

    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;    
        return _sort(head, nullptr);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

第三部分 再论单链表的快速排序

第三种方法的原理是：

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

具体代码如下：

#include <iostream>
using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void print_list(ListNode * head)
{
    if (head == nullptr) return;
    do {
        cout << head->val << " ";
        head = head->next;
    } while(head);
    cout << endl;
}

ListNode* sortList(ListNode* head) 
{
    if (head == nullptr || head->next == nullptr) return head;
    
    ListNode * targetNodePtr = head;
    head = head->next; 
    targetNodePtr->next = nullptr;
    
    ListNode tmpLeftHead;
    ListNode tmpRightHead;
    ListNode * pLeft  = &tmpLeftHead;
    ListNode * pRight = &tmpRightHead;
    
    ListNode * p = head;
    ListNode * tmpNext = nullptr;

    // Split the rest part of the list to 2 lists 
    while (p != nullptr) {
        tmpNext = p->next;
        
        if (p->val < targetNodePtr->val) {
            pLeft->next = p;
            pLeft = pLeft->next;
            pLeft->next = nullptr;
        }
        else {  // p->val >= targetNodePtr->val
            pRight->next = p;
            pRight = pRight->next;
            pRight->next = nullptr;
        }
        p = tmpNext;
    }
    
    // Process the 2 lists recursively 
    ListNode * leftHead  = nullptr;
    ListNode * rightHead = nullptr;
    if (tmpLeftHead.next) leftHead  = sortList(tmpLeftHead.next);
    if (tmpRightHead.next)    rightHead = sortList(tmpRightHead.next);
    
    ListNode * leftListEnd = leftHead;
    while(leftListEnd) {
        if (leftListEnd->next == nullptr) break;
        leftListEnd = leftListEnd->next;
    }
    
    ListNode * finalHead = nullptr;
    
    // merge the 2 lists and the original head node 
    if (leftListEnd) {
        leftListEnd->next = targetNodePtr;
        targetNodePtr->next = rightHead;
        finalHead = leftHead;
    }
    else {
        targetNodePtr->next = rightHead;
        finalHead = targetNodePtr;
    }
    return finalHead;
}

int main()
{
    ListNode n1(1), n2(4), n3(3), n4(2), n5(5), n6(2);
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = &n6;
    
    print_list(&n1);
    ListNode * pn = sortList(&n1);
    print_list(pn);
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

比较上述三种方法

第一种方法（快速排序）

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

第二种方法（归并排序）

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

第三种方法（快速排序）

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

性能比较

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

// way-1
quick_sort_list() took 1.17135 seconds.
quick_sort_list() took 1171351 microseconds.

// way-2 
mergeSortList() took 0.00188763 seconds.
mergeSortList() took 1887 microseconds.

// way-3
sortList() took 2.44667 seconds.
sortList() took 2446665 microseconds.
1
2
3
4
5
6
7
8
9
10
11

由上可见，

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

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

结论

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

（完）