概念
插入排序(Straight Insertion Sort)：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,
原理
将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
例子为从小到大的排序
ggg.jpeg
算法描述（C语言）
void insert_sort(int *a, int len) {
for (int i = 1; i < len; i++) {
int temp = a[i]; //保存当前位置的值
int j;
for (j = i - 1; j >= 0 && temp < a[j]; j--) {
a[j + 1] = a[j]; //后移一位
}
a[j + 1] = temp;//插入到合适的位置
}
}
int main() {
int a[] = {3, 2, 7, 1, 0, 3};
int len = sizeof(a)/sizeof(int);
insert_sort(a, len);
for (int i = 0; i < len; i++) {
printf("%d\n", a[i]);
}
return 0;
}
算法稳定性
两个相等的元素排序结束后位置都不会发生交换，所以插入排序是稳定的。
算法分析
时间复杂度：O(n²)
