插入排序 - 算法原理 - 插入排序的基本思想

插入排序 - 算法原理 - 插入排序的基本思想

在计算机科学的世界里，排序算法就像是一把神奇的梳子，能够将杂乱无章的数据梳理得井井有条。插入排序便是众多排序算法中一种简单且实用的算法，下面我们就来深入探究它的基本思想。

基本思想概述

插入排序的核心思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、长度加一的有序数据。这一过程就如同我们玩扑克牌时整理手中牌的过程。当我们拿到一张新牌时，会将它插入到手中已经排好顺序的牌中的合适位置，使得手中的牌始终保持有序。

具体步骤

插入排序通常从第二个元素开始，依次将每个元素插入到前面已经排好序的子数组中。具体步骤如下：

1. 从数组的第二个元素开始，将其作为当前要插入的元素。
2. 比较当前元素与前面已排序子数组中的元素，从后往前依次比较。
3. 如果当前元素小于已排序子数组中的某个元素，则将该元素后移一位。
4. 重复步骤 3，直到找到一个合适的位置，使得当前元素大于或等于该位置之前的元素。
5. 将当前元素插入到找到的合适位置。
6. 重复步骤 1 - 5，直到整个数组都被排序。

示例演示

为了更直观地理解插入排序的过程，我们来看一个具体的例子。假设有一个数组 [5, 3, 4, 6, 2]，我们将使用插入排序对其进行排序。

第一轮排序

• 当前要插入的元素是 3。
• 比较 3 和前面已排序子数组 [5] 中的元素，从后往前比较。
• 由于 3 < 5，将 5 后移一位，得到 [_, 5]。
• 此时找到合适的位置，将 3 插入到该位置，得到 [3, 5]。

第二轮排序

• 当前要插入的元素是 4。
• 比较 4 和前面已排序子数组 [3, 5] 中的元素，从后往前比较。
• 由于 4 < 5，将 5 后移一位，得到 [3, _, 5]。
• 再比较 4 和 3，由于 4 > 3，找到合适的位置，将 4 插入到该位置，得到 [3, 4, 5]。

第三轮排序

• 当前要插入的元素是 6。
• 比较 6 和前面已排序子数组 [3, 4, 5] 中的元素，从后往前比较。
• 由于 6 > 5，不需要移动元素，直接将 6 插入到 5 后面，得到 [3, 4, 5, 6]。

第四轮排序

• 当前要插入的元素是 2。
• 比较 2 和前面已排序子数组 [3, 4, 5, 6] 中的元素，从后往前比较。
• 由于 2 < 6，将 6 后移一位，得到 [3, 4, 5, _, 6]。
• 由于 2 < 5，将 5 后移一位，得到 [3, 4, _, 5, 6]。
• 由于 2 < 4，将 4 后移一位，得到 [3, _, 4, 5, 6]。
• 由于 2 < 3，将 3 后移一位，得到 [_, 3, 4, 5, 6]。
• 此时找到合适的位置，将 2 插入到该位置，得到 [2, 3, 4, 5, 6]。

整个排序过程结束，数组已经按照升序排列。

下面是用表格总结每一轮排序的结果：
| 轮数 | 已排序子数组 | 待插入元素 | 插入后数组 |
| —— | —— | —— | —— |
| 1 | [5] | 3 | [3, 5] |
| 2 | [3, 5] | 4 | [3, 4, 5] |
| 3 | [3, 4, 5] | 6 | [3, 4, 5, 6] |
| 4 | [3, 4, 5, 6] | 2 | [2, 3, 4, 5, 6] |

代码实现（Python）

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
# 测试代码
arr = [5, 3, 4, 6, 2]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

复杂度分析

• 时间复杂度：在最坏情况下，插入排序的时间复杂度为 $O(n^2)$，其中 $n$ 是数组的长度。这是因为对于每个元素，都需要与前面的元素进行比较和移动。在最好情况下，即数组已经有序时，时间复杂度为 $O(n)$，因为每个元素只需要比较一次。
• 空间复杂度：插入排序只需要常数级的额外空间，因此空间复杂度为 $O(1)$。

总结

插入排序是一种简单易懂的排序算法，它的基本思想是通过不断地将元素插入到已排序的子数组中，最终得到一个有序的数组。虽然插入排序的时间复杂度在最坏情况下较高，但在处理小规模数据或部分有序的数据时，它的性能表现还是比较不错的。同时，插入排序的空间复杂度较低，只需要常数级的额外空间。希望通过本文的介绍，你能对插入排序的基本思想有更深入的理解。