Linkedlist排序详解

小蓝 • 2024-12-12 12:26 • 编程

一、排序算法简介

排序算法常见的有冒泡排序、插入排序、选择排序、快速排序、归并排序等。

冒泡排序：依次比较相邻的两个元素，如果满足交换条件就交换，直到整个列表有序

插入排序：将数组分为有序和无序两个区间，对于每个无序区间中的元素，将其插入到有序区间中的合适位置

选择排序：依次选择未排序的最小值，与已排序区间的下一个元素交换，直到整个列表有序

快速排序：随机选取一个基准值，将小于基准值的数放在左边，将大于基准值的数放在右边，然后递归处理左边和右边的数列

归并排序：将数组分为两个有序区间，然后使用归并算法将这两个有序区间合并成一个有序区间

二、冒泡排序


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)

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/241163.html