插入排序

一、插入排序的定义

插入排序（Insertion Sort）是一种稳定的排序算法，通过构建有序序列，逐步将新元素插入到正确位置，最终完成排序。

---

二、插入排序的发展历史

插入排序是一种古老且直观的排序算法，灵感来源于扑克牌整理，常用于小规模数据集或部分有序的数组。

---

三、插入排序的排序过程

1. 设定初始有序序列（通常是第一个元素）；
2. 遍历剩余元素，将其插入到正确位置；
3. 反复执行，直到所有元素有序。

---

四、插入排序的基本原理

插入排序通过向前插入的方式，将新元素插入到前面已排序序列中的正确位置，实现排序。

---

五、插入排序的特点

1. 稳定性：不会改变相等元素的相对顺序；
2. 适用于小规模数据：对小型数据排序效果较好。

---

六、插入排序的优点

1. 适用于部分有序数据：当数据基本有序时，插入排序的时间复杂度接近 O(n)；
2. 空间占用小：只需要 O(1) 额外空间。

---

七、插入排序的缺点

1. 时间复杂度高：最坏情况下仍为 O(n²)；
2. 不适合大规模数据：在数据量较大时，插入排序效率较低。

---

Python 代码实现

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([12, 11, 13, 5, 6]))

实验结果