单向链表排序：快速排序和归并排序

作者：空白诗007 | 2024-08-20 11:46:44

踩

单向链表排序

对单向链表的排序有2种形式，只改变节点的值 和 只改变链接

// 节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v, ListNode* n = NULL) {
        val = v;
        next = n;
    }
};1
2
3
4
5
6
7
8
9

本文链接：单向链表排序：快速排序和归并排序

参考资料链接：
链表排序（冒泡、选择、插入、快排、归并、希尔、堆排序）：

1. 归并排序（改变链接）

归并排序是最适合单链表排序的算法，因为两个链表的归并比较简单，和数组的归并过程思路相同。
需要注意的是：如何找到链表的中点？
通过2个快慢指针，快指针每一步走2个节点，慢指针每一步走1个节点，当快指针到达链表尾部时，慢指针到达链表的中间节点。

class MergeSort {
public:
    static ListNode* ListMergeSort(ListNode* pHead) {
        if (pHead == NULL || pHead->next == NULL)
            return pHead;
        ListNode* pFast = pHead;
        ListNode* pSlow = pHead;
        // 找到位于中间的节点，快慢指针，快的到结尾，慢的到中点
        while (pFast != NULL && pFast->next == NULL) {
            pFast = pFast->next->next;
            pSlow = pSlow->next;
        }
        pFast = pSlow;
        pSlow = pSlow->next; // 分割成2段
        pFast->next = NULL;
        pHead = ListMergeSort(pHead);
        pSlow = ListMergeSort(pSlow);
        pHead = merge(pHead, pSlow);
        return pHead;
    };
private:
    static ListNode* merge(ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == NULL || pHead2 == NULL) {
            return pHead1 == NULL ? pHead2 : pHead1;
        }
        // 找出合并后的链表头
        ListNode* pHead = NULL;
        if (pHead1->val > pHead2->val) {
            pHead = pHead2;
            pHead2 = pHead2->next;
        } else {
            pHead = pHead1;
            pHead1 = pHead1->next;
        }
        // 将2个链表中值较小的节点依次链接到结果链表中
        ListNode* pHead_orgin = pHead;
        while (pHead1 != NULL && pHead2 != NULL) {
            if (pHead1->val > pHead2->val) {
                pHead->next = pHead2;
                pHead2 = pHead2->next;
            } else {
                pHead->next = pHead1;
                pHead1 = pHead1->next;
            }
            pHead = pHead->next;
        }
        if (pHead1 == NULL)
            pHead->next = pHead2;
        else
            pHead->next = pHead1;
        return pHead_orgin;
    };
};
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

2. 快速排序（改变链接）

只改变链接的指向。
将比基元（第一个节点）小的值，链接到一个左链表中；比基元大的值，链接到一个右链表中；
将左链表，基元，右链表链接起来。

对一段链表执行划分过程时，头节点可能发生改变以及终止节点可能是非空的，因此对一段链表的划分过程需要给出：
前驱节点（指向头节点）和终止节点（标志结束）。
故对传入划分函数的一次链表划分处理是不包括第一个节点和最后一个节点的。（双开区间）

class QuickSort {
public:
    static ListNode* ListQuickSort(ListNode* pHead) {
        if (pHead == NULL || pHead->next == NULL)
            return pHead;
        ListNode headPrev(0, pHead); // pHead 的前驱节点
        ListQuickSort(&headPrev, pHead, NULL);
        return headPrev.next;
    }
private:
    static void ListQuickSort(ListNode* pHeadPrev, ListNode* pHead, ListNode* pTail) {
        // 处理过程不涉及 pHeadPrev 和 pTail
        if (pHead == pTail || pHead->next == pTail)
            return;
        ListNode* pMid = Partation(pHeadPrev, pHead, pTail);
        ListQuickSort(pHeadPrev, pHeadPrev->next, pMid);
        ListQuickSort(pMid, pMid->next, pTail);
    };

    static ListNode* Partation(ListNode* pHeadPrev, ListNode* pHead, ListNode* pTail) {
        int key = pHead->val; // 选第一个节点为基元
        ListNode nodeL(0), nodeR(0);
        ListNode* pLeftPrev = &nodeL; // 小于基元的链表
        ListNode* pRightPrev = &nodeR; // 大于等于基元的链表
        for (ListNode* pNode = pHead->next; pNode != pTail; pNode = pNode->next) {
            if (pNode->val < key) {
                pLeftPrev->next = pNode;
                pLeftPrev = pNode;
            } else {
                pRightPrev->next = pNode;
                pRightPrev = pNode;
            }
        }
        pRightPrev->next = pTail; // 保证子链表继续和后面的相连
        pLeftPrev->next = pHead; // 基元节点链接
        pHead->next = nodeR.next;
        pHeadPrev->next = nodeL.next; // 链表头节点
        return pHead;
    };
};
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

3. 快速排序（改变节点值）

由于链表只能顺序索引，故不能使用数组划分的方法。
将比基元小的节点的值，依次和基元后的节点的值交换。
如 5->3->6->4->7->2
则 5 为基元
3 < 5: swap(3, 3) ，(起始交换位置为基元的下一个节点，即第2个节点)
6 > 5: continue;
4 < 5: swap(6, 4) （交换位置后移，交换4和第3个节点的值）
7 > 5: continue
2 < 5: swap(4, 2) （交换位置后移，交换2和第4个节点的值）

循环结束 swap(5, 2) （交换基元值和第4个节点的值）

最后得到：2->3->4->5->6->7

class QuickSortValue {
public:
    static void QuickSort(ListNode* pHead) {
        if (pHead == NULL || pHead->next == NULL)
            return;
        QuickSort(pHead, NULL);
    }
private:
    static void QuickSort(ListNode* pHead, ListNode* pTail) {
        if (pHead == pTail || pHead->next == pTail)
            return;
        ListNode* pMid = Partation(pHead, pTail);
        QuickSort(pHead, pMid);
        QuickSort(pMid->next, pTail);
    }
    static ListNode* Partation(ListNode* pHead, ListNode* pTail) {
        if (pHead == pTail || pHead->next == pTail)
            return pHead;
        ListNode* pPivot = pHead; // 基元
        int key = pHead->val;
        for (ListNode* pNode = pHead->next; pNode != pTail; pNode = pNode->next) {
            if (pNode->val < key) {
                pPivot = pPivot->next; // 将比基元小的值，依次交换到前面
                swap(pNode, pPivot);
            }
        }
        swap(pHead, pPivot);
        return pPivot;
    }
    static void swap(ListNode* pA, ListNode* pB) {
        int temp = pA->val; pA->val = pB->val; pB->val = temp;
    }
};
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

4. 所有源码和测试函数

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v, ListNode* n = NULL) {
        val = v;
        next = n;
    }
};
void PrintList(ListNode* pHead) {
    while (pHead != NULL) {
        cout << pHead->val << " ";
        pHead = pHead->next;
    }
    cout << endl;
    return;
}
class MergeSort {
public:
    static ListNode* ListMergeSort(ListNode* pHead) {
        if (pHead == NULL || pHead->next == NULL)
            return pHead;
        ListNode* pFast = pHead;
        ListNode* pSlow = pHead;
        // 找到位于中间的节点，快慢指针，快的到结尾，慢的到中点
        while (pFast != NULL && pFast->next == NULL) {
            pFast = pFast->next->next;
            pSlow = pSlow->next;
        }
        pFast = pSlow;
        pSlow = pSlow->next; // 分割成2段
        pFast->next = NULL;
        pHead = ListMergeSort(pHead);
        pSlow = ListMergeSort(pSlow);
        pHead = merge(pHead, pSlow);
        return pHead;
    };
private:
    static ListNode* merge(ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == NULL || pHead2 == NULL) {
            return pHead1 == NULL ? pHead2 : pHead1;
        }
        // 找出合并后的链表头
        ListNode* pHead = NULL;
        if (pHead1->val > pHead2->val) {
            pHead = pHead2;
            pHead2 = pHead2->next;
        } else {
            pHead = pHead1;
            pHead1 = pHead1->next;
        }
        ListNode* pHead_orgin = pHead;
        while (pHead1 != NULL && pHead2 != NULL) {
            if (pHead1->val > pHead2->val) {
                pHead->next = pHead2;
                pHead2 = pHead2->next;
            } else {
                pHead->next = pHead1;
                pHead1 = pHead1->next;
            }
            pHead = pHead->next;
        }
        if (pHead1 == NULL)
            pHead->next = pHead2;
        else
            pHead->next = pHead1;
        return pHead_orgin;
    };
};

class QuickSort {
public:
    static ListNode* ListQuickSort(ListNode* pHead) {
        if (pHead == NULL || pHead->next == NULL)
            return pHead;
        ListNode headPrev(0, pHead); // pHead 的前驱节点
        ListQuickSort(&headPrev, pHead, NULL);
        return headPrev.next;
    }
private:
    static void ListQuickSort(ListNode* pHeadPrev, ListNode* pHead, ListNode* pTail) {
        if (pHead == pTail || pHead->next == pTail)
            return;
        ListNode* pMid = Partation(pHeadPrev, pHead, pTail);
        ListQuickSort(pHeadPrev, pHeadPrev->next, pMid);
        ListQuickSort(pMid, pMid->next, pTail);
    };

    static ListNode* Partation(ListNode* pHeadPrev, ListNode* pHead, ListNode* pTail) {
        int key = pHead->val; // 选第一个节点为基元
        ListNode nodeL(0), nodeR(0);
        ListNode* pLeftPrev = &nodeL;
        ListNode* pRightPrev = &nodeR;
        for (ListNode* pNode = pHead->next; pNode != pTail; pNode = pNode->next) {
            if (pNode->val < key) {
                pLeftPrev->next = pNode;
                pLeftPrev = pNode;
            } else {
                pRightPrev->next = pNode;
                pRightPrev = pNode;
            }
        }
        pRightPrev->next = pTail; // 保证子链表继续和后面的相连
        pLeftPrev->next = pHead; // 基元节点链接
        pHead->next = nodeR.next;
        pHeadPrev->next = nodeL.next;
        return pHead;
    };
};

class QuickSortValue {
public:
    static void QuickSort(ListNode* pHead) {
        if (pHead == NULL || pHead->next == NULL)
            return;
        QuickSort(pHead, NULL);
    }
private:
    static void QuickSort(ListNode* pHead, ListNode* pTail) {
        if (pHead == pTail || pHead->next == pTail)
            return;
        ListNode* pMid = Partation(pHead, pTail);
        QuickSort(pHead, pMid);
        QuickSort(pMid->next, pTail);
    }
    static ListNode* Partation(ListNode* pHead, ListNode* pTail) {
        if (pHead == pTail || pHead->next == pTail)
            return pHead;
        ListNode* pPivot = pHead; // 基元
        int key = pHead->val;
        for (ListNode* pNode = pHead->next; pNode != pTail; pNode = pNode->next) {
            if (pNode->val < key) {
                pPivot = pPivot->next; // 将比基元小的值，依次交换到前面
                swap(pNode, pPivot);
            }
        }
        swap(pHead, pPivot);
        return pPivot;
    }
    static void swap(ListNode* pA, ListNode* pB) {
        int temp = pA->val; pA->val = pB->val; pB->val = temp;
    }
};

int main() 
{
    srand(time(0));
    const int N = 30;
    ListNode* pHead = NULL;
    for (int i = 0; i < N; i++) {
        if (pHead == NULL) {
            pHead = new ListNode(rand() % 100 + 1, NULL);
        }
        else {
            ListNode* tempNode = new ListNode(rand() % 100 + 1, pHead);
            pHead = tempNode;
        }
    }
    PrintList(pHead);
    pHead = MergeSort::ListMergeSort(pHead); // merge-sort
   // pHead = QuickSort::ListQuickSort(pHead); // quick-sort-swap-node
   //QuickSortValue::QuickSort(pHead); // quick-sort-swap-value
    PrintList(pHead);
}
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】