插入排序

6.1 插入排序的定义

插入排序 (Insertion Sort) 是一种排序算法，它通过一次处理一个元素来构建一个有序数组（或列表）。它从未排序部分中取出每个元素，然后将其插入到已排序部分的正确位置。

工作原理：

1. 从数组的第二个元素开始（第一个元素被认为是已排序的）。
2. 将当前元素与前面的元素进行比较，并向左移动它，直到找到正确的位置。
3. 对数组的所有元素重复此过程，将每个新元素插入到已排序部分的正确位置。

插入排序的时间和空间复杂度

时间复杂度：

• 最坏情况: O(n^2) - 当元素最初按相反顺序排列时发生。
• 平均情况: O(n^2) - 发生在元素随机排列时。
• 最好情况: O(n) - 当元素已经排序时发生。

空间复杂度：

O(1) - 因为算法只使用常量数量的额外内存（仅用于存储临时值的几个变量）。

6.2 算法工作过程解析

在算法的每一步，我们有如下情况：

• 当前有索引为 i 的元素。
• 它左边的所有元素已按从小到大的顺序排列。
• 我们尝试将当前元素插入到数组的已排序部分中，以保持排序顺序不变。

尝试将元素插入到已排序部分的过程如下：

1. 变量 j 在循环中取值从 i - 1 到 0。
2. 如果当前的第 i 个元素小于第 j 个元素，我们将第 j 个元素的值右移 1。

示例：当前情况：

• 绿色表示已排序的元素。
• 粉色表示尚未排序的元素。
• 当前索引为 5 的元素以棕色标记。

我们试图在已排序部分中为当前元素找到正确的位置。

步骤 1 — 将当前元素的值存储到变量key中。

步骤 2 — 元素 No4 比 key 大吗？（10 大于 5？）那么将元素 No4 向右移动：

步骤 3 — 元素 No3 比 key 大吗？（8 大于 5？）那么将元素 No3 向右移动：

步骤 4 — 元素 No2 比 key 大吗？（6 大于 5？）那么将元素 No2 向右移动：

步骤 5 — 元素 No1 比 key 大吗？（4 大于 5？）不。那么将元素key保存到原来No2的位置。

把元素No5插入到合适位置后，我们转到元素No6，尝试在已排序部分中为其找到位置：

然后我们拿第七个元素：

然后是第 8 个：

6.3 插入排序算法的实现

以下是此算法在 Python 中的实现：

def insertion_sort(arr):
    # 遍历数组的所有元素，从第二个开始
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # 将大于key的arr[0..i - 1]元素向后移动一位
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # 将key插入到正确的位置
    return arr  # 返回已排序的数组

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

解释:

• 将当前元素存到 key 中
• 将已排序部分的所有元素向右移动
• 将我们的元素插入到合适的位置

算法示例

我们用一个数组示例：[12, 11, 13, 5, 6]

1. 第一次循环 (i = 1):

• 比较 11 和 12，将 12 右移。
• 数组: [11, 12, 13, 5, 6]

2. 第二次循环 (i = 2):

• 13 已经在正确的位置。
• 数组: [11, 12, 13, 5, 6]

3. 第三次循环 (i = 3):

• 比较 5 和 13, 12 和 11，将所有元素右移。
• 数组: [5, 11, 12, 13, 6]

4. 第四次循环 (i = 4):

• 比较 6 和 13, 12 和 11，将所有元素右移。
• 数组: [5, 6, 11, 12, 13]

算法完成，因为所有元素都已排序。