当前位置:   article > 正文

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

单链表的快速排序

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

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

结论

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

(完)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/1006928
推荐阅读
相关标签
  

闽ICP备14008679号