万字长文，链表排序算法——冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序精讲及python实现

1. 链表排序简介

在���组排序中，常见的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。

而对于链表排序而言，因为链表不支持随机访问，访问链表后面的节点只能依靠 next 指针从头部顺序遍历，所以相对于数组排序问题来说，链表排序问题会更加复杂一点。

下面先来总结一下适合链表排序与不适合链表排序的算法：

• 适合链表的排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序。

• 不适合链表的排序算法：希尔排序。

• 可以用于链表排序但不建议使用的排序算法：堆排序。

  希尔排序为什么不适合链表排序？

  希尔排序：希尔排序中经常涉及到对序列中第 i + gap 的元素进行操作，其中 gap 是希尔排序中当前的步长。而链表不支持随机访问的特性，导致这种操作不适合链表，因而希尔排序算法不适合进行链表排序。

  为什么不建议使用堆排序？

  堆排序：堆排序所使用的最大堆 / 最小堆结构本质上是一棵完全二叉树。而完全二叉树适合采用顺序存储结构（数组）。因为数组存储的完全二叉树可以很方便的通过下标序号来确定父亲节点和孩子节点，并且可以极大限度的节省存储空间。

  而链表用在存储完全二叉树的时候，因为不支持随机访问的特性，导致其寻找子节点和父亲节点会比较耗时，如果增加指向父亲节点的变量，又会浪费大量存储空间。所以堆排序算法不适合进行链表排序。

  如果一定要对链表进行堆排序，则可以使用额外的数组空间表示堆结构。然后将链表中各个节点的值依次添加入堆结构中，对数组进行堆排序。排序后，再按照堆中元素顺序，依次建立链表节点，构建新的链表并返回新链表头节点。

  需要用到额外的辅助空间进行排序的算法

  刚才我们说到如果一定要对链表进行堆排序，则需要使用额外的数组空间。除此之外，计数排序、桶排序、基数排序都需要用到额外的数组空间。

  接下来，我们将对适合链表排序的 8 种算法进行一一讲解。当然，这些排序算法不用完全掌握，重点是掌握 「链表插入排序」、「链表归并排序」 这两种排序算法。

  2. 链表冒泡排序

  2.1 链表冒泡排序算法描述

  1. 使用三个指针 node_i、node_j 和 tail。其中 node_i 用于控制外循环次数，循环次数为链节点个数（链表长度）。node_j 和 tail 用于控制内循环次数和循环结束位置。

  2. 排序开始前，将 node_i 、node_j 置于头节点位置。tail 指向链表末尾，即 None。

  3. 比较链表中相邻两个元素 node_j.val 与 node_j.next.val 的值大小，如果 node_j.val > node_j.next.val，则值相互交换。否则不发生交换。然后向右移动 node_j 指针，直到 node_j.next == tail 时停止。

  4. 一次循环之后，将 tail 移动到 node_j 所在位置。相当于 tail 向左移动了一位。此时 tail 节点右侧为链表中最大的链节点。

  5. 然后移动 node_i 节点，并将 node_j 置于头节点位置。然后重复第 3、4 步操作。

  6. 直到 node_i 节点移动到链表末尾停止，排序结束。

  7. 返回链表的头节点 head。

  2.2 链表冒泡排序算法实现代码

  class Solution:    def bubbleSort(self, head: ListNode):        node_i = head        tail = None        # 外层循环次数为 链表节点个数        while node_i:            node_j = head            while node_j and node_j.next != tail:                if node_j.val > node_j.next.val:                    # 交换两个节点的值                    node_j.val, node_j.next.val = node_j.next.val, node_j.val                node_j = node_j.next            # 尾指针向前移动 1 位，此时尾指针右侧为排好序的链表            tail = node_j            node_i = node_i.next                    return head​    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:        return self.bubbleSort(head)

  2.3 链表冒泡排序算法复杂度分析

  • 时间复杂度：$O(n^2)$。

  • 空间复杂度：$O(1)$。

    3. 链表选择排序

    3.1 链表选择排序算法描述

    1. 使用两个指针 node_i、node_j。node_i 既可以用于控制外循环次数，又可以作为当前未排序链表的第一个链节点位置。

    2. 使用 min_node 记录当前未排序链表中值最小的链节点。

    3. 每一趟排序开始时，先令 min_node = node_i（即暂时假设链表中 node_i 节点为值最小的节点，经过比较后再确定最小值节点位置）。

    4. 然后依次比较未排序链表中 node_j.val 与 min_node.val 的值大小。如果 node_j.val

    5. 这一趟排序结束时，未排序链表中最小值节点为 min_node，如果 node_i != min_node，则将 node_i 与 min_node 值进行交换。如果 node_i == min_node，则不用交换。

    6. 排序结束后，继续向右移动 node_i，重复上述步骤，在剩余未排序链表中寻找最小的链节点，并与 node_i 进行比较和交换，直到 node_i == None 或者 node_i.next == None 时，停止排序。

    7. 返回链表的头节点 head。

    3.2 链表选择排序实现代码

    class Solution:    def sectionSort(self, head: ListNode):        node_i = head        # node_i 为当前未排序链表的第一个链节点        while node_i and node_i.next:            # min_node 为未排序链表中的值最小节点            min_node = node_i            node_j = node_i.next            while node_j:                if node_j.val  Optional[ListNode]:        return self.sectionSort(head)

    3.3 链表选择排序算法复杂度分析

    • 时间复杂度：$O(n^2)$。

    • 空间复杂度：$O(1)$。

      4. 链表插入排序

      4.1 链表插入排序算法描述

      1. 先使用哑节点 dummy_head 构造一个指向 head 的指针，使得可以从 head 开始遍历。

      2. 维护 sorted_list 为链表的已排序部分的最后一个节点，初始时，sorted_list = head。

      3. 维护 prev 为插入元素位置的前一个节点，维护 cur 为待插入元素。初始时，prev = head，cur = head.next。

      4. 比较 sorted_list 和 cur 的节点值。

         • 如果 sorted_list.val cur.val，说明 cur 应该插入到 head 与 sorted_list 之间。则使用 prev 从 head 开始遍历，直到找到插入 cur 的位置的前一个节点位置。然后将 cur 插入。

      5. 令 cur = sorted_list.next，此时 cur 为下一个待插入元素。

      6. 重复 4、5 步骤，直到 cur 遍历结束为空。返回 dummy_head 的下一个节点。

      4.2 链表插入排序实现代码

      class Solution:    def insertionSort(self, head: ListNode):        if not head or not head.next:            return head                dummy_head = ListNode(-1)        dummy_head.next = head        sorted_list = head        cur = head.next                 while cur:            if sorted_list.val  Optional[ListNode]:        if not head or not head.next:            return head        return self.quickSort(head, None)

      6.3 链表快速排序算法复杂度分析

      • 时间复杂度：$O(n \times \log_2n)$。

      • 空间复杂度：$O(1)$。

        7. 链表计数排序

        7.1 链表计数排序算法描述

        1. 使用 cur 指针遍历一遍链表。找出链表中最大值 list_max 和最小值 list_min。

        2. 使用数组 counts 存储节点出现次数。

        3. 再次使用 cur 指针遍历一遍链表。将链表中每个值为 cur.val 的节点出现次数，存入数组对应第 cur.val - list_min 项中。

        4. 反向填充目标链表：

           1. 建立一个哑节点 dummy_head，作为链表的头节点。使用 cur 指针指向 dummy_head。

           2. 从小到大遍历一遍数组 counts。对于每个 counts[i] != 0 的元素建立一个链节点，值为 i + list_min，将其插入到 cur.next 上。并向右移动 cur。同时 counts[i] -= 1。直到 counts[i] == 0 后继续向后遍历数组 counts。

        5. 将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为新链表的头节点返回。

        7.2 链表计数排序代码实现

        class Solution:    def countingSort(self, head: ListNode):        if not head:            return head                # 找出链表中最大值 list_max 和最小值 list_min        list_min, list_max = float('inf'), float('-inf')        cur = head        while cur:            if cur.val  list_max:                list_max = cur.val            cur = cur.next                    size = list_max - list_min + 1        counts = [0 for _ in range(size)]                cur = head        while cur:            counts[cur.val - list_min] += 1            cur = cur.next                    dummy_head = ListNode(-1)        cur = dummy_head        for i in range(size):            while counts[i]:                cur.next = ListNode(i + list_min)                counts[i] -= 1                cur = cur.next        return dummy_head.next​    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:        return self.countingSort(head)

        7.3 链表计数排序算法复杂度分析

        • 时间复杂度：$O(n + k)$，其中 $k$ 代表待排序链表中所有元素的值域。

        • 空间复杂度：$O(k)$。

          8. 链表桶排序

          8.1 链表桶排序算法描述

          1. 使用 cur 指针遍历一遍链表。找出链表中最大值 list_max 和最小值 list_min。

          2. 通过 (最大值 - 最小值) / 每个桶的大小 计算出桶的个数，即 bucket_count = (list_max - list_min) // bucket_size + 1 个桶。

          3. 定义数组 buckets 为桶，桶的个数为 bucket_count 个。

          4. 使用 cur 指针再次遍历一遍链表，将每个元素装入对应的桶中。

          5. 对每个桶内的元素单独排序，可以使用链表插入排序、链表归并排序、链表快速排序等算法。

          6. 最后按照顺序将桶内的元素拼成新的链表，并返回。

          8.2 链表桶排序代码实现

          class ListNode:    def __init__(self, val=0, next=None):        self.val = val        self.next = next​class Solution:    # 将链表节点值 val 添加到对应桶 buckets[index] 中    def insertion(self, buckets, index, val):        if not buckets[index]:            buckets[index] = ListNode(val)            return                node = ListNode(val)        node.next = buckets[index]        buckets[index] = node            # 归并环节    def merge(self, left, right):        dummy_head = ListNode(-1)        cur = dummy_head        while left and right:            if left.val  list_max:                list_max = cur.val            cur = cur.next                    # 计算桶的个数，并定义桶        bucket_count = (list_max - list_min) // bucket_size + 1        buckets = [[] for _ in range(bucket_count)]                # 将链表节点值依次添加到对应桶中        cur = head        while cur:            index = (cur.val - list_min) // bucket_size            self.insertion(buckets, index, cur.val)            cur = cur.next                    dummy_head = ListNode(-1)        cur = dummy_head        # 将元素依次出桶，并拼接成有序链表        for bucket_head in buckets:            bucket_cur = self.mergeSort(bucket_head)            while bucket_cur:                cur.next = bucket_cur                cur = cur.next                bucket_cur = bucket_cur.next                        return dummy_head.next        def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:        return self.bucketSort(head)

          8.3 链表桶排序算法复杂度分析

          • 时间复杂度：$O(n)$。

          • 空间复杂度：$O(n + m)$。$m$ 为桶的个数。

            9. 链表基数排序

            9.1 链表基数排序算法描述

            1. 使用 cur 指针遍历链表，获取节点值位数最长的位数 size。

            2. 从个位到高位遍历位数。因为 0 ~ 9 共有 10 位数字，所以建立 10 个桶。

            3. 以每个节点对应位数上的数字为索引，将节点值放入到对应桶中。

            4. 建立一个哑节点 dummy_head，作为链表的头节点。使用 cur 指针指向 dummy_head。

            5. 将桶中元素依次取出，并根据元素值建立链表节点，并插入到新的链表后面。从而生成新的链表。

            6. 之后依次以十位，百位，…，直到最大值元素的最高位处值为索引，放入到对应桶中，并生成新的链表，最终完成排序。

            7. 将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为新链表的头节点返回。

            9.2 链表基数排序代码实现

            class Solution:    def radixSort(self, head: ListNode):               # 计算位数最长的位数        size = 0        cur = head        while cur:            val_len = len(str(cur.val))            if val_len > size:                size = val_len            cur = cur.next                # 从个位到高位遍历位数        for i in range(size):            buckets = [[] for _ in range(10)]            cur = head            while cur:                # 以每个节点对应位数上的数字为索引，将节点值放入到对应桶中                buckets[cur.val // (10 ** i) % 10].append(cur.val)                cur = cur.next                        # 生成新的链表            dummy_head = ListNode(-1)            cur = dummy_head            for bucket in buckets:                for num in bucket:                    cur.next = ListNode(num)                    cur = cur.next            head = dummy_head.next                    return head        def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:        return self.radixSort(head)

            9.3 链表基数排序算法复杂度分析

            • 时间复杂度：$O(n \times k)$。其中 $n$ 是待排序元素的个数，$k$ 是数字位数。$k$ 的大小取决于数字位的选择（十进制位、二进制位）和待排序元素所属数据类型全集的大小。

            • 空间复杂度：$O(n + k)$。