插入排序详解

什么是插入排序？

插入排序是一种简单直观的比较排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤

1. 初始化：将第一个元素视为已排序序列。
2. 遍历数组：从第二个元素开始，假设当前元素未排好序。
3. 比较与插入：在已排序的序列中逆序查找，直到找到比该元素小的位置，或到达序列起始位置。然后将该元素插到正确的位置。

具体步骤展示

1. 初始化

假设有以下数组：

[5, 2, 4, 6, 1, 3]

第一个元素 5 被视为已排序序列 [5]。

2. 遍历与比较

从第二个元素开始遍历：

• 第二个元素是 2，在已排序序列中逆序查找插入位置，发现 5 > 2。将 5 向后移动，插入 2 的位置。

[2, 5, 4, 6, 1, 3]

• 第三个元素是 4，在已排序序列中逆序查找插入位置，发现 5 > 4、2 > 4。将 5 和 2 向后移动，插入 4 的位置。

[2, 4, 5, 6, 1, 3]

• 第四个元素是 6，在已排序序列中逆序查找插入位置，发现 6 > 5、6 > 4、6 > 2。未找到比它小的数，直接插入到末尾。

[2, 4, 5, 6, 6, 1, 3]

• 第五个元素是 1，在已排序序列中逆序查找插入位置，发现 6 > 1、5 > 1、4 > 1、2 > 1。将所有元素向后移动，插入 1 的位置。

[1, 2, 4, 5, 6, 6, 3]

• 第六个元素是 3，在已排序序列中逆序查找插入位置，发现 6 > 3、6 > 3。将所有比它大的元素向后移动，插入 3 的位置。

[1, 2, 3, 4, 5, 6, 6]

时间复杂度

• 最佳情况：数组已经排序，时间复杂度为 (O(n))。
• 平均和最坏情况：时间复杂度均为 (O(n^2))，空间复杂度为 (O(1))。

实现代码

以下是 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

# 示例数组
arr = [5, 2, 4, 6, 1, 3]
insertion_sort(arr)
print("排序后的数组:", arr)

总结

插入排序是一种简单且直观的排序算法，尤其适用于小规模数据或者部分有序的数据。尽管其时间复杂度较高，在最坏情况下为 (O(n^2))，但在某些场景下仍是高效的。通过逐步构建已排序序列的方法，插入排序能够逐渐将无序数组转变为有序数组。

希望这篇文章能帮助你更好地理解插入排序的工作原理和应用方式！