Linkedlist排序詳解

一、排序演算法簡介

排序演算法常見的有冒泡排序、插入排序、選擇排序、快速排序、歸併排序等。

冒泡排序：依次比較相鄰的兩個元素，如果滿足交換條件就交換，直到整個列表有序

插入排序：將數組分為有序和無序兩個區間，對於每個無序區間中的元素，將其插入到有序區間中的合適位置

選擇排序：依次選擇未排序的最小值，與已排序區間的下一個元素交換，直到整個列表有序

快速排序：隨機選取一個基準值，將小於基準值的數放在左邊，將大於基準值的數放在右邊，然後遞歸處理左邊和右邊的數列

歸併排序：將數組分為兩個有序區間，然後使用歸併演算法將這兩個有序區間合併成一個有序區間

二、冒泡排序

def bubble_sort(self):
    if not self.head:
        return 
    cur = self.head 
    while cur:
        cmp = cur.next 
        while cmp:
            if cur.value > cmp.value:
                cur.value, cmp.value = cmp.value, cur.value 
            cmp = cmp.next 
        cur = cur.next 

冒泡排序的時間複雜度為O(n^2)，空間複雜度為O(1)

三、插入排序

def insert_sort(self):
    if not self.head:
        return 
    dummy = ListNode(0)
    dummy.next = self.head  
    cur = self.head 
    while cur.next:
        if cur.value <= cur.next.value:
            cur = cur.next 
        else:
            temp = cur.next 
            cur.next = temp.next
            pre = dummy 
            while pre.next.value <= temp.value:
                pre = pre.next 
            temp.next = pre.next 
            pre.next = temp 
    self.head = dummy.next 

插入排序的時間複雜度為O(n^2)，空間複雜度為O(1)

四、選擇排序

def select_sort(self):
    if not self.head:
        return 
    cur = self.head 
    while cur:
        min_node = cur 
        cmp = cur.next 
        while cmp:
            if cmp.value < min_node.value:
                min_node = cmp 
            cmp = cmp.next 
        cur.value, min_node.value = min_node.value, cur.value 
        cur = cur.next 

選擇排序的時間複雜度為O(n^2)，空間複雜度為O(1)

五、快速排序

def quick_sort(self, head, tail):
    if not head or head == tail:
        return head 
    pivot = head.value 
    slow = fast = head 
    while fast != tail:
        if fast.value < pivot:
            slow = slow.next 
            slow.value, fast.value = fast.value, slow.value 
        fast = fast.next 
    slow.value, head.value = head.value, slow.value 
    self.quick_sort(head, slow)
    self.quick_sort(slow.next, tail)

快速排序的時間複雜度為O(nlogn)，空間複雜度為O(logn)

六、歸併排序

def merge(self, l1, l2):
    dummy = ListNode(0)
    tail = dummy 
    while l1 and l2:
        if l1.value <= l2.value:
            tail.next, l1 = l1, l1.next 
        else:
            tail.next, l2 = l2, l2.next 
        tail = tail.next 
    if l1:
        tail.next = l1 
    else:
        tail.next = l2 
    return dummy.next 

def merge_sort(self, head, tail):
    if not head:
        return head 
    if head.next == tail:
        head.next = None 
        return head 
    slow = fast = head 
    while fast != tail:
        slow = slow.next 
        fast = fast.next 
        if fast != tail:
            fast = fast.next 
    mid = slow 
    return self.merge(self.merge_sort(head, mid), self.merge_sort(mid, tail))

歸併排序的時間複雜度為O(nlogn)，空間複雜度為O(logn)