插入排序

 

思路

  • 前2个元素排序:把第2个元素放到“前1个元素组成的有序数组”中。
  • 前3个元素排序:把第3个元素放到“前2个元素组成的有序数组”中。
  • 前4个元素排序:把第4个元素放到“前3个元素组成的有序数组”中。
  • ……
  • 前n个元素排序:……

平均时间复杂度:O(n2)

实现

void insert_sort(const int* a, int length){
    for(int i = 1; i < length; i++){
        int k = a[i];
        for(int j = i-1; j >= 0; j--){
            if(a[j] > a[i]){
                a[j+1] = a[j];
            }else {
                break; 
            }
        }
        a[j] = k;
    }
}

关键点注释

与冒泡相似。区别只在内遍历的范围:是从i + 1到0.