python 插入排序（Insertion Sort）

插入排序（Insertion Sort）

插入排序是一种简单的排序算法。它的基本思想是：将数组分为已排序部分和未排序部分，然后逐个将未排序部分的元素插入到已排序部分的正确位置。插入排序类似于整理扑克牌的过程。

插入排序的步骤：

1. 初始化：将第一个元素视为已排序部分。
2. 插入元素：从未排序部分取出一个元素，将其插入到已排序部分的正确位置。
3. 重复过程：重复上述步骤，直到所有元素都被排序。

时间复杂度：

• 最坏情况：O(n²) —— 当数组是逆序的时候。
• 最好情况：O(n) —— 当数组已经有序的时候。
• 平均情况：O(n²)

空间复杂度：

• O(1) —— 插入排序是一种原地排序算法，不需要额外的存储空间。

Python 实现

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]  # 当前需要插入的元素
        j = i - 1
        # 将比 key 大的元素向后移动
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        # 将 key 插入到正确位置
        arr[j + 1] = key
    return arr

# 示例使用
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("排序后的数组:", sorted_arr)

输出结果

排序后的数组: [5, 6, 11, 12, 13]

插入排序的详细过程

以数组 [12, 11, 13, 5, 6] 为例：

1. 第一轮：

   • 已排序部分：[12]
   • 未排序部分：[11, 13, 5, 6]
   • 将 11 插入到已排序部分，数组变为 [11, 12, 13, 5, 6]。

2. 第二轮：

   • 已排序部分：[11, 12]
   • 未排序部分：[13, 5, 6]
   • 将 13 插入到已排序部分，数组变为 [11, 12, 13, 5, 6]。

3. 第三轮：

   • 已排序部分：[11, 12, 13]
   • 未排序部分：[5, 6]
   • 将 5 插入到已排序部分，数组变为 [5, 11, 12, 13, 6]。

4. 第四轮：

   • 已排序部分：[5, 11, 12, 13]
   • 未排序部分：[6]
   • 将 6 插入到已排序部分，数组变为 [5, 6, 11, 12, 13]。

5. 排序完成。

插入排序的优缺点

优点：

• 实现简单，易于理解。
• 对于小规模数据或基本有序的数据，效率较高。
• 是稳定的排序算法（相同元素的相对位置不变）。

缺点：

• 时间复杂度较高，不适合处理大规模数据。
• 对于逆序数据，性能较差。

插入排序的适用场景

• 数据规模较小。
• 数据基本有序。
• 需要稳定排序的场景。