插入排序（Insertion Sort）

题目描述
给定一个长度为 n 的整数数组 nums，请实现插入排序算法对该数组进行原地升序排序。插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。请解释算法步骤，分析其时间复杂度和空间复杂度，并讨论其适用场景。

解题过程循序渐进讲解

1. 核心思想
插入排序模拟了我们整理扑克牌的过程：左手持已排序的牌，右手从桌上摸一张新牌，然后将新牌插入左手已排序牌中的正确位置。对于数组，我们可以将第一个元素视为已排序序列（初始长度为1），然后依次将后续元素插入到已排序序列的合适位置，直到整个数组有序。

2. 算法步骤详述
假设数组 nums 的下标从 0 到 n-1。

• 步骤1：初始时，我们认为 nums[0] 是已排序序列（长度为1）。i 从 1 开始遍历到 n-1，i 指向当前待插入的元素。
• 步骤2：将当前待插入元素 nums[i] 保存在一个临时变量 key 中（避免后续移动元素时被覆盖）。
• 步骤3：设置指针 j = i - 1，从已排序序列的末尾（即 i-1 位置）开始向前扫描。
• 步骤4：在扫描过程中，比较 key 与 nums[j]。如果 nums[j] > key，说明 nums[j] 应该位于 key 之后，因此将 nums[j] 向后移动一位（赋值给 nums[j+1]）。然后 j 减1，继续向前比较。
• 步骤5：当遇到以下两种情况之一时，停止向前扫描并插入 key：
  a) 找到一个位置 j，使得 nums[j] <= key（此时 key 应插入到 j+1 位置）。
  b) j 减到 -1（即已扫描完整个已排序序列，key 是当前最小元素，应插入到开头）。
• 步骤6：将 key 插入到位置 j+1（即 nums[j+1] = key）。
• 步骤7：重复步骤2~6，直到 i 遍历完整个数组。

3. 示例说明
以数组 nums = [5, 2, 4, 6, 1, 3] 为例，展示其逐步排序过程。

初始状态：[5, 2, 4, 6, 1, 3]

• i=1: key=2。j从0开始，5>2，所以5右移得[5,5,4,6,1,3]，j=-1停止，插入key到j+1=0，得[2,5,4,6,1,3]。
• i=2: key=4。j=1，5>4，5右移得[2,5,5,6,1,3]；j=0，2<=4，停止，插入key到j+1=1，得[2,4,5,6,1,3]。
• i=3: key=6。j=2，5<=6，停止，插入key到j+1=3，得[2,4,5,6,1,3]（位置不变）。
• i=4: key=1。j=3，6>1，右移得[2,4,5,6,6,3]；j=2，5>1，右移得[2,4,5,5,6,3]；j=1，4>1，右移得[2,4,4,5,6,3]；j=0，2>1，右移得[2,2,4,5,6,3]；j=-1，停止，插入key到0，得[1,2,4,5,6,3]。
• i=5: key=3。j=4，6>3，右移得[1,2,4,5,6,6]；j=3，5>3，右移得[1,2,4,5,5,6]；j=2，4>3，右移得[1,2,4,4,5,6]；j=1，2<=3，停止，插入key到j+1=2，得[1,2,3,4,5,6]。
  排序完成。

4. 代码实现（Python）

def insertion_sort(nums):
    n = len(nums)
    for i in range(1, n):
        key = nums[i]          # 待插入元素
        j = i - 1
        # 从后向前扫描已排序序列，移动比 key 大的元素
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key     # 插入 key
    return nums

5. 复杂度分析

• 时间复杂度：
  • 最好情况：数组已完全有序，内层 while 循环每次只比较一次就退出，总比较次数为 n-1，移动次数为0，时间复杂度为 O(n)。
  • 最坏情况：数组完全逆序，每个元素都需要移动到最前面。第 i 个元素需要比较 i 次、移动 i 次，总比较和移动次数约为 n(n-1)/2，时间复杂度为 O(n²)。
  • 平均情况：时间复杂度为 O(n²)。
• 空间复杂度：只使用了常数个临时变量（如 key, i, j），是原地排序，空间复杂度为 O(1)。
• 稳定性：当遇到相等元素时（nums[j] > key 的条件是严格大于，等于时不移动），不会改变相等元素的相对顺序，因此是稳定排序。

6. 特点与适用场景

• 优点：
  • 实现简单，代码紧凑。
  • 对小规模数据或基本有序数据效率很高（接近 O(n)）。
  • 原地、稳定排序。
  • 在线算法：可以逐个接收数据并实时排序。
• 缺点：对大规模乱序数据效率低，O(n²) 的时间复杂度在大数据下不实用。
• 适用场景：
  • 小规模数组排序（如 n ≤ 20）。
  • 部分有序数组的排序（如日志按时间插入）。
  • 作为高级排序算法的子过程（例如，在快速排序或归并排序中，当递归到小规模子问题时，切换到插入排序可提升性能）。
• 实际应用举例：在标准库的混合排序算法（如 Timsort）中，当分段长度较小时常用插入排序处理。