小白向-python实现插入排序算法
插入排序
一、插入排序的定义
插入排序（Insertion Sort）是一种稳定的排序算法，通过构建有序序列，逐步将新元素插入到正确位置，最终完成排序。
二、插入排序的发展历史
插入排序是一种古老且直观的排序算法，灵感来源于扑克牌整理，常用于小规模数据集或部分有序的数组。
三、插入排序的排序过程
- 设定初始有序序列（通常是第一个元素）；
- 遍历剩余元素，将其插入到正确位置；
- 反复执行，直到所有元素有序。
四、插入排序的基本原理
插入排序通过向前插入的方式，将新元素插入到前面已排序序列中的正确位置，实现排序。
五、插入排序的特点
- 稳定性：不会改变相等元素的相对顺序；
- 适用于小规模数据：对小型数据排序效果较好。
六、插入排序的优点
- 适用于部分有序数据：当数据基本有序时，插入排序的时间复杂度接近 O(n)；
- 空间占用小：只需要 O(1) 额外空间。
七、插入排序的缺点
- 时间复杂度高：最坏情况下仍为 O(n²)；
- 不适合大规模数据：在数据量较大时，插入排序效率较低。
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]))
实验结果
