1.算法概述
插入排序是一个平均时间复杂度O(n^2)级别的排序算法，它具有稳定性，即排序完成之后各个相同元素的相对顺序保持一致。
插入排序的基本思想：在一个有序的序列中寻找一个合适的位置进行插入
2.算法步骤
- 默认取第二个元素开始与已经排好序的元素序列比较，因为第一个元素已经是有序的
- 取下一个元素如果元素大于当前待插入的元素（动图中红色色块）则移动至下一个位置
- 重复步骤2，直至找到当前待插入的元素小于或者等于比较的元素
- 将当前待插入的元素插入到新的位置
- 重复步骤2~4
3.算法动图演示
插入排序动效
4.代码实现
template <typename T>
void InsertSort(T* arr, int n) {
for (int i = 1; i < n; i++) {
int j;
T tmp = arr[i];
// 向前查找一个合适的插入位置
for (j = i; j > 0 && arr[j - 1] > tmp; --j) {
arr[j] = arr[j - 1];
}
arr[j] = tmp;
}
}
5.插入排序总结
插入排序的平均复杂度虽然是O(n^2)，但是插入排序在小规模数据的中排序效率的表现甚至O(nlogn)级别的排序效率高，因此常常被用来作为大规模排序中的子排序，以提高算法运行效率
