排序:插入排序

标签: 排序

时间复杂度
最好情况:数组本身有序,只需进行比较O(n)
最坏情况:数组逆序,O(n^2)
这里写图片描述
思想:将一个待排序的数组插入到已排序的数组中

开始时,数组第一个元素为有序数组,剩下为待排序数组
若待排序数组的第一个a[i]小于有序数组的最后一个a[i-1]
则将待排序数组的第一个元素插入到有序数组中
插入步骤:
将有序数组依次(j=i-1~0)与待排序数组第一个元素a[i]进行比较
若有序数组中的元素大于a[i]则有序数组元素后移a[j+1]=a[j],否则退出遍历
a[i]插入到有序数组j+1位置

vector<int> charu(vector<int> &a){
     if(a.size()==1)
         return a;
     for(int i=1;i<a.size();i++){
         if(a[i]<a[i-1]){
             int temp=a[i];
             int j;
             //插入到有序数组中
             for(j=i-1;j>=0;j--){
                 if(a[j]>temp)
                     a[j+1]=a[j];
                 else
                     break;
             }
             a[j+1]=temp;
         }
     }
     return a;

}
原文链接:加载失败,请重新获取