排序算法之插入排序

1. 插入排序（Insertion Sort）

类似于摸牌时对扑克牌的排序。

• 执行流程：

1. 插入排序会将序列分为两部分：头部是已经排序完毕的，尾部是待排序的状态。
   
2. 从头开始扫描每一个元素，每当扫描一个元素，就将他插入到头部合适的位置，使得头部数据依然保持有序。

/**
 * @Description 插入排序实现
 * @date 2022/5/3 9:33
 */
public class InsertionSort<T extends Comparable<T>> extends Sort<T>  {

    @Override
    protected void sort() {
        for (int begin = 1; begin < arr.length; begin++) {
            int cur = begin;
            while (cur > 0 && cmp(cur,cur - 1) < 0){ // 比较当前位置和前一个位置大小
                swap(cur,cur -1); // 符合就交换
                cur--;
            }
        }
    }
}

1.1 逆序对（Inversion）

逆序对：序列后面值的与前面值的顺序相反即是一对逆序对。
例如：<2,3,5,8,6,1>中：<2,1> 、< 3 ,1>、<5,1>、<8,6>、<8,1>、<6,1>都是逆序对。

插入排序的时间复杂度于逆序对呈正比关系，即逆序对越多时间复杂度越高。
最坏、平均时间复杂度可以达到O( n² )，最好的时间复杂度是O(n)；空间复杂度为O(1)，属于稳定排序；当逆序对的数量极少时，效率特别高，甚至高于 O(nlogn) 级别的快速排序。

1.2 插入排序 - 挪动优化

将交换转为挪动。

1. 将待插入的元素备份；
2. 头部有序数据中比待插入元素大的，都朝尾部方向挪动一个位置；
3. 将待插入元素放到最终的合适位置。

例如：红色待插入元素大于 0 和 1：

挪动：3 、4 、5 ：

将待插入元素放到合适位置：

1.3 二分搜索（Binary Search）

在一个有序的数组中，查找某个元素的位置，使用二分搜索可以达到**O(logn)**的时间复杂度。

• 图示：begin为开始元素（数组下标0），end是元素数量（数组最后一个下标加一），mid为中间值。这种设计的最大优势是：end - begin = 元素数量。
  
• 如果在[beign,end)范围内搜索元素V，中间值：mid = （begin + end）/ 2；

1. 如果 v < m，去[being,mid)范围内再进行二分搜索；
2. 如果v > m，去[mid + 1, end)范围内二分搜索；
3. 如果v == m，直接返回mid。

	/**
     * 二分搜索查找 v 在有序数组中位置
     * @param arr 数组
     * @param v 目标值
     * @return 下标位置
     */
    public static int indexOf(int[] arr, int v){
        if (arr == null || arr.length == 0) return -1;
        // end - begin = 元素数量
        int begin = 0;
        int end = arr.length;
        while (begin < end){ // 保证至少有一个元素
            int mid = (end + begin) >> 1;
            if (v < arr[mid]){
                end = mid;
            }else if (v > arr[mid]){
                begin = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

1.4 插入排序 - 二分搜索优化

在元素 v 的插入过程中，使用二分搜索出合适的插入位置，然后挪动相应元素，将元素v插入。

• 例如：要对元素1使用插入排序。
  
• 使用二分搜索法，查找相应位置：

1. 计算：mid = (0 + 7) / 2 = 3 ，比较：1 < arr[mid]，重新赋值：end = mid；
2. 计算：mid = (0 + 3) / 2 = 1 ，比较：1 < arr[mid]，重新赋值：end = mid；
3. 计算：mid = (0 + 1) / 2 = 0 ，比较：1 < arr[mid]，重新赋值：end = mid；
4. 得出：元素1应该放在索引为0的位置。

• 挪动对应元素之后：重新变为有序序列
  

• 算法设计：返回的插入位置：第一个大于 v 的位置；

1. 在[begin,end)范围内搜索某个元素 v ，mid = (begin + end) / 2；
2. v < m ，去[begin,mid)范围内二分搜索；
3. v ≥ m，去[mid + 1,end)范围内二分搜索。
   
   例如：搜索 5：
   
   搜索 15：
   
   搜索 8：
4. 可以得出结论：当二分搜索执行到end == being他们的值就是我们要找的插入位置。

• 二分搜索方法实现：

    /**
     * 二分搜索 v 在有序队列中的待插入位置
     * @param arr
     * @param v
     * @return
     */
    public static int search(int[] arr, int v){
        if (arr == null || arr.length == 0) return -1;
        int begin = 0;
        int end = arr.length;
        while (begin < end){ // 当 begin 与 end 相等时退出循环
            int mid = (begin + end) >> 1;
            if (v < arr[mid]){
                end = mid;
            }else {
                begin = mid + 1;
            }
        }
        return begin;
    }

• 实现二分搜索版本插入排序：

/**
 * @Description 二分搜索优化插入排序
 * @date 2022/5/3 9:33
 */
public class InsertionSortBinary<T extends Comparable<T>> extends Sort<T>  {

    @Override
    protected void sort() {
        for (int begin = 1; begin < arr.length; begin++) {
            // 备份待插入元素
            T v = arr[begin];
            // 获取插入目标索引
            int insertIndex = search(begin);
            // 往右挪动一位：[insertIndex,begin)
            // 两种挪动方式：
//            for (int i = begin - 1; i >= insertIndex ; i--) {
//                arr[i + 1] = arr[i];
//            }
            for (int i = begin; i > insertIndex ; i--) {
                arr[i] = arr[i - 1];
            }
            arr[insertIndex] = v;
        }
    }

    /**
     * 利用二分搜索找到 index 位置元素的待插入位置
     * 传入索引包含了已经排好序的数组元素为：[0,index)；
     * @param index
     * @return
     */
    private int search(int index){
        T v = arr[index];
        int begin = 0;
        int end = index;
        while (begin < end){ // 当 begin 与 end 相等时退出循环
            int mid = (begin + end) >> 1;
            if (cmp(v,arr[mid]) < 0){
                end = mid;
            }else {
                begin = mid + 1;
            }
        }
        return begin;
    }
}

• 总结：虽然使用了二分搜索减少了比较次数，但是时间复杂度仍然是O( n² ) 级别。

1.5 比较

很明显的可以看出：二分搜索版本插入排序，比较比普通版本的插入排序少了不是一点半点。