算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）。

动图演示

静图演示

代码实现

void InsertSort(int* a, int n){
          
   
    for(int i = 0; i < n - 1; i++){
          
   //用i来调整end
        int end = i;//已排序序列[0, end]
        int tmp = a[end + 1];//向已排序序列中插入数据a[end + 1]，先将未排序数据a[end + 1]保存到tmp
        while(end >= 0){
          
   //在已排序序列中从后向前扫描，找到合适的插入位置时，退出循环
            if(tmp < a[end]){
          
   //如果tmp<a[end]则a[end]向后移动（升序）
                a[end + 1] = a[end];
                end--;
            }
            else{
          
   
                break;//因为[0,end]是有序序列，如果tmp>=a[end]，则将tmp插入到end+1位置即可
            }
        }
        a[end + 1] = tmp;//退出循环后，将tmp插入找到的合适的位置
    }
}

复杂度、稳定性分析

1. 时间复杂度 设有N个元素待排 假设这N个元素是有序的，只需要遍历一遍每个元素，那么最好情况下的时间复杂度为 O ( N ) O(N) O(N)。 假设这N个元素是无序的，那么插入第N个元素时，最坏需要比较N-1次，总的最坏的比较次数为 1 + 2 + 3 + . . . + ( N − 1 ) 1+2+3+...+(N-1) 1+2+3+...+(N−1)，等差数列求和，结果为 N 2 / 2 N^{2}/2 N2/2，所以最坏情况下的时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)。
2. 空间复杂度 仅仅使用了常数个辅助单元，空间复杂度是O(1);
3. 稳定性 插入排序，不会改变相同元素的相对顺序，所以是稳定的。