插入排序(insertion sort)

10大排序算法.png

• 插入排序是稳定排序
• 插入排序的时间复杂度与逆序对的数量成正比关系，逆序对的数量越多 插入排序的时间复杂度就越高
• 最坏、平均时间复杂度：O(n^2) 最好时间复杂度：O(n) 空间复杂度：O(1)
• 当逆序对的数量极少时，插入排序的效率特别高，甚至速度比O(nlogn)级别的快速排序还要快

插入排序的执行流程：

1. 在执行过程中，插入排序会将序列分为2部分

• 头部是已经排好序的，尾部是待排序的
  2.从头开始扫描每一个元素
  -每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序

插入排序简单实现

for(int begin = 1;begin < list.length;begin++){
   //保留begin
  int curr = begin;
  //cmp: 对比两个元素大小，swap:交换两个元素
  while(curr > 0 && cmp(curr,curr-1) < 0) {
      swap(curr,curr-1);
      curr--;
  }

}

插入排序优化：将交换转为挪动
1.先将待插入的元素备份
2.头部有序数据中比待插入元素大的 都朝尾部方向挪动1个位置
3.将待插入元素放到最终的合适位置

for(int begin = 1;begin < list.length;begin++) {

  int curr = begin;
  //1.先将待插入的元素备份
  int val = list[curr];
  //cmp: 对比两个元素大小
  while(curr > 0 && cmp(val,list[curr-1]) < 0) {
        //2.将头部有序数组比当前大的 都向尾部方向移动一位 
        list[curr] = list[curr-1];
       curr--;
  }

  //3.将待插入元素放到最终的合适位置
  list[curr] = val;

}

插入排序再次优化：在元素val的插入过程中，可以先二分搜索出合适的插入位置，然后再将元素val插入 ；如此就减少了比较次数，但是时间复杂度还是O(n^2)

for(int begin = 1;begin < list.length;begin++) {
    //传入当前元素位置和当前元素合适插入的位置
    insert(begin, findInsetIdx(list, begin));
}

//将source位置元素插入到dest位置
private void insert(int[] list, int source, int dest) {
     //1.先将待插入的元素备份
     int val = list[source];
    //2.将[dest, source)范围内的元素往右挪动一个单位，靠后的先挪动
    for(int i = source ; i > dest ;i-- ) {
          list[i] = list[i-1];
   }
   //3.将val放入合适的位置
   list[dest] = val;
}

//二分查找 要求找到第一个大于val的位置
int findInsetIdx:(int[] list, int index) {
   if(list==null || list.length==0) return -1;
  int val = list[index];
  //左闭右开区间,已经排好序的区间是[0,index)
  int begin = 0;
  int end = index;
  while(begin < end) {
     int mid = (begin + end)>>1;
     if(val < list[mid]) {
         end = mid;
      }else  {//val >= list[mid]
         begin = mid + 1;
      }  
   }
   return begin;
}