两种链表排序法（快速排序和合并排序）

超、凢脫俗 2022-05-17 04:43 114阅读 0赞

# 链表快速排序
    class nodelist:
        def __init__(self,x):
            self.val = x
            self.next = None
    class Solution:
        def sort(self,phead):
            if phead == None:
                return None
            else:
                self.quicksort(phead,None)
        # 节点的交换
        def swap(self,node1,node2):
            tem = node1.val
            node1.val = node2.val
            node2.val = tem
        # 快速排序函数
        def quicksort(self,head,end):
            # 保证至少有两个节点
            if head != end:
                # 第一个节点值作为快速排序参考值
                key = head.val
                # p为慢节点
                p = head
                # q为快节点
                q = head.next
                # q其实将除了参考值外的节点遍历了一遍
                while q != end:
                    # 出现节点的值小于参考值
                    # p遍历过的节点都是小于参考值的节点
                    if q.val < key:
                        p = p.next# p节点前进1，并赋值p节点
                        self.swap(p,q)# 将p节点和q节点对换
                    q = q.next
                self.swap(head,p)
    #             print p.val
                self.quicksort(head,p)
                self.quicksort(p.next,end)
    a1 = nodelist(4)
    a2 = nodelist(3)
    a3 = nodelist(2)
    a4 = nodelist(5)
    a5 = nodelist(6)
    a6 = nodelist(3)
    a1.next = a2
    a2.next = a3
    a3.next = a4
    a4.next = a5
    a5.next = a6
    S = Solution()
    S.sort(a1)
    print a1.val
    print a1.next.val
    print a1.next.next.val
    print a1.next.next.next.val

# 链表合并排序
    class nodelist:
        def __init__(self,x):
            self.val = x
            self.next = None
    class Solution:
        def sort(self,phead):
            if phead == None:
                return None
            else:
                first = phead
                return self.merge(first)
        def merge(self,first):
            # 确保对两个以上的节点进行操作
            if first != None and first.next != None:
                fast = first
                slow = first
                while fast != None and fast.next != None and fast.next.next != None:
                    fast = fast.next.next
                    slow = slow.next
                # 将慢节点前一部分的节点的最后变为None，慢节点的后一部分从慢节点的下一个开始
                fast = slow
                slow = slow.next
                fast.next = None
                node1 = self.merge(first)
                node2 = self.merge(slow)
                # 融合两个节点列表,注意返回值
                return self.mergesort(node1,node2)
            else:
                return first
        def mergesort(self,first,second):
            if first.val < second.val:
                start = first
                first = first.next
            else:
                start = second
                second = second.next
            node = start
            while first != None and second != None:
                if first.val < second.val:
                    node.next = first
                    first = first.next
                    node = node.next
                else:
                    node.next = second
                    second = second.next
                    node = node.next
            if first != None:
                node.next = first
            if second != None:
                node.next = second
            return start
    a1 = nodelist(3)
    a2 = nodelist(1)
    a3 = nodelist(3)
    a4 = nodelist(5)
    a5 = nodelist(7)
    a1.next = a2
    a2.next = a3
    a3.next = a4
    a4.next = a5
    S = Solution()
    a = S.sort(a1)
    print a.next.next.val