深入单链表的快速排序详解

深入单链表的快速排序详解

单链表的快速排序是一种对于链表进行排序的高效算法，本文将详细讲解如何实现快速排序算法，并逐步解释每一步的原理和代码实现。

快速排序算法的基本原理

快速排序是一种采用分治策略的排序算法，基本原理为选取一个基准元素，并将小于基准元素和大于基准元素的部分分别递归排序，最终得到排序的结果。在单链表快速排序中，通常使用头节点作为基准节点。

具体实现思路如下：

1. 遍历链表，找到头节点，并记录尾节点为null。
2. 将链表分为小于头节点和大于头节点两个部分，并分别递归排序。
3. 合并两个部分，返回排好序的链表。

快速排序算法的实现

下面是单链表快速排序算法的完整实现：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        mid = self.getMid(head)
        left, right = self.partition(head, mid)
        left = self.sortList(left)
        right = self.sortList(right)
        return self.merge(left, right)

    def getMid(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        return mid

    def partition(self, head: ListNode, mid: ListNode) -> tuple:
        left = ListNode(None)
        right = ListNode(None)
        p = left
        q = right
        while head:
            if head.val < mid.val:
                p.next = head
                p = p.next
            else:
                q.next = head
                q = q.next
            head = head.next
        q.next = None
        p.next = mid
        return left.next, right.next

    def merge(self, h1: ListNode, h2: ListNode) -> ListNode:
        dummy = ListNode(None)
        tail = dummy
        while h1 and h2:
            if h1.val < h2.val:
                tail.next = h1
                h1 = h1.next
            else:
                tail.next = h2
                h2 = h2.next
            tail = tail.next
        if h1:
            tail.next = h1
        else:
            tail.next = h2
        return dummy.next

在上面的代码中，getMid方法用于实现快排算法中的查找中间值的操作；partition方法用于实现链表的分割操作；merge方法用于将两个子链表合并。

示例说明

下面是两个例子，分别对应于链表长度为奇数和长度为偶数的情况。

示例一：

假设链表为[4,3,1,5,2]，则经过排序后，链表应该变为[1,2,3,4,5]。

代码实现如下：

if __name__ == "__main__":
    head = ListNode(4)
    head.next = ListNode(3)
    head.next.next = ListNode(1)
    head.next.next.next = ListNode(5)
    head.next.next.next.next = ListNode(2)
    s = Solution()
    res = s.sortList(head)
    while res:
        print(res.val, end=" ")
        res = res.next

输出结果为：

1 2 3 4 5 

示例二：

假设链表为[5,2,3,4,1,6]，则经过排序后，链表应该变为[1,2,3,4,5,6]。

代码实现如下：

if __name__ == "__main__":
    head = ListNode(5)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(1)
    head.next.next.next.next.next = ListNode(6)
    s = Solution()
    res = s.sortList(head)
    while res:
        print(res.val, end=" ")
        res = res.next

输出结果为：

1 2 3 4 5 6 

以上就是单链表快速排序算法的详细讲解和示例说明。