链表插入排序：用 Swift 简单算法实现高效排序

好事发生

文章推荐：HarmonyOS 应用跨团队 Debug 协作

文章链接：https://cloud.tencent.com/developer/article/2471407

文章简介：当问题涉及多个团队（如前端、后端、运维），低效的沟通可能拖延修复进度并影响用户体验。本文结合实际案例，分享在 HarmonyOS 应用开发中如何通过高效协作排查跨团队 Bug。感兴趣的同学可以看看！

前言

本题由于没有合适答案为以往遗留问题，最近有时间将以往遗留问题一一完善。

147. 对链表进行插入排序

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

摘要

在本篇文章中，我们将探讨如何使用插入排序算法对单链表进行排序。插入排序是一种简单的排序算法，它的基本思想是：通过将未排序的元素逐步插入到已排序的部分，最终形成一个有序的序列。我们将结合Swift代码实现单链表的插入排序，并通过示例测试展示如何应用该算法。

描述

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

示例 1：

输入: head = [4,2,1,3]
输出: [1,2,3,4]

示例 2：

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

提示：

• 列表中的节点数在 [1, 5000]范围内
• -5000 <= Node.val <= 5000

题解答案

插入排序的实现步骤：

1. 定义辅助节点：创建一个虚拟节点dummy，作为已排序部分的头节点，便于插入操作。
2. 遍历链表：对于链表中的每一个元素，遍历已排序部分，找到合适的位置插入。
3. 调整指针：在适当位置插入当前节点时，调整节点指针，保持链表的结构。

Swift实现

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func insertionSortList(_ head: ListNode?) -> ListNode? {
    // 创建虚拟头节点
    let dummy = ListNode(0)
    var current = head  // 当前待排序节点
    while current != nil {
        var prev = dummy  // prev指向已排序部分的最后一个节点
        // 在已排序部分找到合适的插入位置
        while let nextNode = prev.next, nextNode.val < current!.val {
            prev = nextNode
        }
        
        let nextTemp = current!.next  // 保存当前节点的下一个节点
        // 插入当前节点
        current!.next = prev.next
        prev.next = current
        current = nextTemp  // 移动到下一个待排序节点
    }
    return dummy.next  // 返回排序后的链表头
}

题解代码分析

1. 创建虚拟头节点：我们通过创建一个虚拟的头节点dummy来简化插入操作。虚拟头节点的作用是避免在链表头部插入时需要特殊处理。
2. 插入操作：
   • prev指针用于找到已排序部分中小于current节点的最大节点（即找到current应该插入的位置）。
   • 然后，我们将current节点插入到prev.next的位置，调整链表指针来实现插入操作。
3. 遍历链表：每次遍历链表，都会将一个待排序节点插入到已排序部分。操作直到链表全部排序。
4. 时间复杂度：每次插入操作都需要遍历已排序部分，最多需要插入n个节点，因此时间复杂度是O(n^2)，其中n是链表的节点数量。
5. 空间复杂度：插入排序算法只需要常数级的额外空间，因此空间复杂度是O(1)。

示例测试及结果

示例 1

let head1 = ListNode(4)
head1.next = ListNode(2)
head1.next?.next = ListNode(1)
head1.next?.next?.next = ListNode(3)

let sortedList1 = insertionSortList(head1)
printList(sortedList1)  // 输出：[1, 2, 3, 4]

示例 2

let head2 = ListNode(-1)
head2.next = ListNode(5)
head2.next?.next = ListNode(3)
head2.next?.next?.next = ListNode(4)
head2.next?.next?.next?.next = ListNode(0)

let sortedList2 = insertionSortList(head2)
printList(sortedList2)  // 输出：[-1, 0, 3, 4, 5]

辅助函数：打印链表

func printList(_ head: ListNode?) {
    var current = head
    while current != nil {
        print(current!.val, terminator: " ")
        current = current?.next
    }
    print()
}

时间复杂度

• 时间复杂度：由于每次插入一个节点需要遍历已排序部分，因此总时间复杂度为O(n^2)，其中n是链表节点数。
• 空间复杂度：插入排序只用了常数级的额外空间，因此空间复杂度为O(1)。

总结

插入排序是一种简单且易于实现的排序算法，尤其适用于链表的排序。在这篇文章中，我们演示了如何通过插入排序算法对链表进行排序，并通过Swift代码实现了该算法。虽然插入排序的时间复杂度为O(n^2)，它的空间复杂度是O(1)，因此对于较小的链表，插入排序是一种不错的选择。

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。