十大排序算法之插入排序

• 插入排序非常类似扑克牌的排序
  

  image.png

• 执行流程

1. 在执行过程中，插入排序会将序列分为2个部分。（头部是已经排好序的，尾部是待排序的）

2. 从头扫描每一个元素。每当扫描一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序。

   
   image.png

• 实现

for (int begin = 1; begin < array.length; begin++) {
    int cur = begin;
    while (cur > 0 && cmp(cur, cur - 1) < 0) {
        swap(cur, cur - 1);
        cur--;
    }
}

逆序对

数组 <2,3,8,6,1> 的逆序对为：<2,1> <3,1> <8,1> <8,6> <6,1>，共5个逆序对

• 插入排序的时间复杂度与逆序对的数量成正比关系
  逆序对的数量越多，插入排序的时间复杂度越高

  
  image.png

◼ 最坏、平均时间复杂度：O(n2)
◼ 最好时间复杂度：O(n)
◼ 空间复杂度：O(1)
◼ 属于稳定排序
◼ 当逆序对的数量极少时，插入排序的效率特别高

甚至速度比 O nlogn 级别的快速排序还要快
◼ 数据量不是特别大的时候，插入排序的效率也非常好

优化

• 思路是将【交换】转为【挪动】
  1，先将待插入的元素备份
  2，头部有序数据中有比待插入的元素大的，都朝尾部方向挪动一个位置
  3， 将带插入的元素放到最终合适的位置

  
  image.png

for (int begin = 0; begin < array.length; begin++) {
    int cur = begin;
    T v = (T) array[cur];
    while (cur > 0 && cmp(v, array[cur - 1]) < 0) {
        array[cur] = array[cur - 1];
        cur--;
    }
    array[cur] = v;
            
}