在日常生活中，我们整理扑克牌时，通常会将新摸到的牌插入到手中已有牌的正确位置，使手中的牌始终保持有序。这种”逐个插入到有序部分”的思路，正是插入排序算法的核心思想。
插入排序的基本思路¶
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是：将数组中的元素逐个插入到已排序的子数组中，最终使整个数组达到有序状态。具体步骤如下：
- 初始状态：默认数组的第一个元素已经是”有序的”（只有一个元素的数组自然有序）。
- 逐个处理后续元素：从数组的第二个元素（索引1）开始，将每个元素视为”待插入元素”。
- 寻找插入位置：将待插入元素与已排序子数组中的元素从后往前比较，找到合适的位置后插入，确保插入后子数组仍然有序。
- 重复过程：直到所有元素都被插入到正确位置，排序完成。
算法实现步骤¶
以数组 [5, 2, 9, 1, 5, 6] 为例，详细说明插入排序的过程：
- 外层循环：从第二个元素（索引1）开始遍历数组，每次取出待插入元素
temp = arr[i]。 - 内层循环：从当前元素的前一个位置（
j = i-1）开始，与temp比较：
- 如果已排序子数组中的元素arr[j] > temp，则将arr[j]后移一位（arr[j+1] = arr[j]）。
- 继续向前比较（j -= 1），直到找到arr[j] <= temp或j < 0（所有元素都比temp大）。 - 插入元素：将
temp插入到j+1的位置（确保插入后子数组有序）。
Python代码实现¶
def insertion_sort(arr):
# 外层循环：从第二个元素开始（索引1）
for i in range(1, len(arr)):
temp = arr[i] # 保存当前待插入的元素
j = i - 1 # 从已排序子数组的末尾开始比较
# 内层循环：寻找插入位置，同时后移元素
while j >= 0 and arr[j] > temp:
arr[j + 1] = arr[j] # 当前元素后移一位
j -= 1 # 继续比较前一个元素
arr[j + 1] = temp # 插入temp到正确位置
return arr
# 测试代码
if __name__ == "__main__":
test_arr = [5, 2, 9, 1, 5, 6]
print("排序前：", test_arr)
sorted_arr = insertion_sort(test_arr)
print("排序后：", sorted_arr)
代码执行示例¶
以 [5, 2, 9, 1, 5, 6] 为例，逐步拆解排序过程：
-
i=1（待插入元素=2）：
-temp=2，j=0，arr[0]=5>2→arr[1]=5（数组变为[5,5,9,1,5,6]），j=-1。
- 插入temp到j+1=0→ 数组变为[2,5,9,1,5,6]。 -
i=2（待插入元素=9）：
-temp=9，j=1，arr[1]=5<=9→ 循环终止，插入位置j+1=2，数组不变。 -
i=3（待插入元素=1）：
-temp=1，j=2，arr[2]=9>1→arr[3]=9（数组变为[2,5,9,9,5,6]），j=1。
-arr[1]=5>1→arr[2]=5（数组变为[2,5,5,9,5,6]），j=0。
-arr[0]=2>1→arr[1]=2（数组变为[2,2,5,9,5,6]），j=-1。
- 插入temp到j+1=0→ 数组变为[1,2,5,9,5,6]。 -
后续步骤：继续处理剩余元素（5和6），最终数组变为
[1,2,5,5,6,9]。
复杂度分析¶
- 时间复杂度：
- 最好情况（数组已排序）：O(n)（每个元素只需比较一次）。
- 最坏情况（数组逆序）：O(n²)（每个元素需比较n次）。
- 空间复杂度：O(1)（仅需一个临时变量
temp，原地排序）。
插入排序适用于小规模数据或基本有序的数据，实现简单且稳定。通过理解”逐个插入”的核心思想，你能轻松掌握这一经典排序算法的实现逻辑。