概念

插入排序(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²)