插入排序（insertion Sort）

• 平均时间复杂度：O(n)
• 最好情况：O(n)
• 最坏情况：O(n)
• 空间复杂度：O(1)
• 排序方式：内部
• 稳定性：稳定

  C++代码实现

  void insertionsort(vector<int>& arr) {
    int len = arr.size();
    for(int i=1;i<len;i++){
        int j,curInsert=arr[i];
        for(j = i-1; j>=0 && curInsert<arr[j]; j--){    //cmp
                arr[j+1]=arr[j];
        }
        arr[j+1]=curInsert;
    }
  }

1. 算法步骤

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

   优化步骤

   ① 在查找插入位置时，可使用二分查找（本篇未实现）

2. 动图演示