插入排序（Insertion Sort）是一种简单直观的排序算法，它的核心逻辑即将每一个元素插入到其他有序的元素序列中的适当位置。对于每次插入排序的过程，当前元素左边的所有元素都是有序的，但其最终位置还未确定，在后续过程中可能会被移动。这个过程直至索引到达序列的最右侧。
插入排序的过程类似于整理扑克牌的过程，依次将手上的牌插入到已经整理好的牌中。
算法步骤
对于一个数组A[0...n-1]：
- 将第一个元素
A[0]视为有序序列； - 从
A[1]开始，依次在有序序列中找到合适的位置插入当前元素A[i]，使得插入后的序列仍然有序； - 重复步骤2，直到所有元素都被插入到有序序列中。
以数组[5, 2, 9, 1, 5]为例：
- 初始状态：
[5 | 2, 9, 1, 5]（|左侧为有序序列）； - 插入
2：[2, 5 | 9, 1, 5]； - 插入
9：[2, 5, 9 | 1, 5]； - 插入
1：[1, 2, 5, 9 | 5]； - 插入
5：[1, 2, 5, 5, 9]； - 完成排序。
伪代码实现
InsertionSort(A):
for i = 1 to A.length-1:
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j+1] = A[j]
j = j - 1
A[j+1] = key
算法复杂度分析
插入排序在数组已经有序的最好情况下，时间复杂度为$ O(n) $；在数组逆序的最坏情况下，时间复杂度为$ O(n^2) $；其平均时间复杂度为$ O(n^2) $。
插入排序不需要额外的存储空间，所有的操作都是在原数组上完成的，因此空间复杂度为$ O(1) $。
结论
插入排序是一个简单稳定的排序算法。平均$ O(n^2) $的时间复杂度使它在大规模数据的排序中效率较低，但在小规模数据或基本有序的数据场景下表现良好。另外，由于插入排序的实现较为简单，易于初学者理解和掌握。
参考资料
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd Edition
- Sedgewick, Robert, Wayne, Kevin. Algorithms, 4th Edition