链表的快排和归并排序

àì夳堔傛蜴生んèń 2024-04-17 20:39 62阅读 0赞

#### 链表快排 ####

对一个单链表用快排的方式排序

快排的关键在于partition函数，因为单链表是不能倒序遍历的，因此不能通过头尾双指针向内夹的partition函数，而是用都是从头开始的双指针方式，具体的两种partition函数可以参考：[快排的两种partition函数][partition]

这里链表快排和数组快排partition函数中关键的不同点在于：partition函数中遍历结束的方式，和递归结束的方式

# 链表快排
    class Node:
        def __init__(self, val):
            self.val = val
            self.next = None
    
    def bulid_list(data_list):
        head = Node(0)
        cur = head
        for val in data_list:
            cur.next = Node(val)
            cur = cur.next
        return head.next
    
    def print_list(root):
        while root:
            print(root.val)
            root = root.next
    
    def partition(start, end):
        left = start
        right = start
        while right != end:		# 遍历到end为止
            if right.val<start.val:
                left = left.next
                left.val, right.val = right.val, left.val
            right = right.next
        start.val, left.val = left.val, start.val
        return left
    
    def quick_sort(left, right):
        if left!=right:			# 递归的终止条件是左右指针不相等
            index = partition(left, right)
            quick_sort(left, index)			# 这两行也要注意，这里以index结束，前半部分并不会有它
            quick_sort(index.next, right)	# 这里要以index.next开始
    
    array = [1,6,0,-1]
    root = bulid_list(array)
    
    head = root
    print_list(root)
    quick_sort(head, None)
    print_list(head)

#### 链表的归并排序 ####

有两个关键的地方：

1、获取一个单链表的中点位置，用快慢指针的方法

2、根据中点截断一个链表，将中间节点位置的next设置为None，就将链表断开了，这一点还是很巧妙的

其他地方实际上和数组的归并类似

class LinkSort:
        def get_mid_of_list(self, head):
            if not head:
                return head
            p = head.next
            q = head
            while p:
                p = p.next
                if p:
                    p = p.next
                    q = q.next
            return q
    
        def merge_sort(self, head):
            if not head or not head.next:
                return head
            mid = self.get_mid_of_list(head)
            left = head
            right = mid.next
            mid.next = None			# 这一步比较关键
            p = self.merge_sort(left)
            q = self.merge_sort(right)
            pre = Node(-1)
            cur = pre
            while p and q:
                if p.val < q.val:
                    cur.next = p
                    cur = p
                    p = p.next
                else:
                    cur.next = q
                    cur = q
                    q = q.next
            cur.next = p or q		# 返回p和q中的非空值
            return pre.next

[partition]: https://blog.csdn.net/songyunli1111/article/details/100176402