Python中链表的快速排序（Quick Sort）实现

2023-04-11 00:00:00 排序链表快速

链表的快速排序是一种高效的排序算法，它的思想是先选定一个值（通常为第一个节点），然后将链表分成两部分，左边部分是小于等于该值的节点，右边部分是大于该值的节点。然后分别对左右部分进行递归排序，再将排好序的部分拼接在一起。

下面是Python中链表快速排序的实现代码：

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

def quick_sort(head):
    if not head or not head.next:
        return head

    pivot = head.val
    left = ListNode()
    right = ListNode()
    p1 = left
    p2 = right

    p = head.next
    while p:
        if p.val <= pivot:
            p1.next = p
            p1 = p1.next
        else:
            p2.next = p
            p2 = p2.next
        p = p.next

    p1.next = None
    p2.next = None

    left = quick_sort(left.next)
    right = quick_sort(right.next)
    return merge(left, right, pivot)

def merge(left, right, pivot):
    dummy = ListNode()
    p = dummy

    p1 = left
    while p1:
        p.next = ListNode(p1.val)
        p = p.next
        p1 = p1.next

    p.next = ListNode(pivot)
    p = p.next

    p2 = right
    while p2:
        p.next = ListNode(p2.val)
        p = p.next
        p2 = p2.next

    return dummy.next

我们首先定义了一个链表节点类ListNode，它包含了一个val属性和一个next属性，分别表示当前节点的值和下一个节点的指针。quick_sort函数接收一个链表头节点作为参数，实现了链表的快速排序。这个函数中的第一个判断语句if not head or not head.next用于判断链表是否为空或只包含一个节点，这两种情况下链表已经排好序，所以直接返回。接下来选定一个值作为基准值（通常为链表的第一个节点），然后将链表分成两部分，左边部分是小于等于该值的节点，右边部分是大于该值的节点。我们使用left和right两个链表分别保存左右两边的节点，然后逐个遍历链表的其余节点，如果节点的值小于等于基准值，则将它挂在left链表的末尾，否则挂在right链表的末尾。最后，将left和right分别递归调用quick_sort函数，返回排好序的左右两个部分，再将基准值插入到左右两个部分的中间即可。

最后一个函数merge用于将排好序的左右两个链表拼接到一起。我们创建一个dummy节点用于辅助插入操作，然后按顺序将left、基准值、right的值逐个插入到新的链表中，最后返回新链表的头节点即可。

相关文章