我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

经典的十大排序算法！

前言

请==务必==看一下这个：排序算法前置知识+代码环境准备。

当上面的内容都准备好以后，那就开始插入排序吧！

插入排序

插入排序非常类似于扑克牌的排序，将后面的牌一张张插入到前面，使得前面有序的牌逐渐变多，直到完全有序。

执行流程

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

头部是已经排好序的，尾部是待排序的

• ② 从头开始扫描每一个元素

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

插入排序实现

/**
 * 插入排序
 */
public class InsertionSort1 <T extends Comparable<T>> extends Sort<T>{

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

}

生成 20000 个取值在[1, 10000] 的随机数进行排序：

插入排序-逆序对

什么是逆序对？

• 数组 <2, 3, 8, 6, 1> 的逆序对为：

< 2,1 > < 3,1> <8,1> <8,6> <6,1>，共5个逆序对

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

• 逆序对的数量越多，插入排序的时间复杂度越高

很明显，下图从上至下，插入排序的效率是逐渐提高的。

插入排序 – 优化

思路是将【交换】转为【挪动】

执行流程：

• ① 先将待插入的元素备份
• ② 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
• ③ 将待插入元素放到最终的合适位置

/**
 * 插入排序-优化
 * 交换  -> 挪动
 */
public class InsertionSort2 <T extends Comparable<T>> extends Sort<T>{

    @Override
    protected void sort() {
        for(int begin = 1; begin < array.length; begin++){
            int cur = begin; 
            T v = array[begin]; // 将待插入元素备份
            while(cur > 0 && cmp(v, array[cur-1]) < 0){
                // 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
                array[cur] = array[cur - 1]; 
                cur--;
            }
            array[cur] = v; // 将待插入元素放到最终的合适位置
        }
    }

}    

生成 20000 个取值在[1, 10000] 的随机数进行排序：可以发现，交换次数变为了0

复杂度与稳定性

• 最坏、平均时间复杂度：O(n^2^)
• 最好时间复杂度：O(n)
• 空间复杂度：O(1)
• 属于稳定排序
• 当逆序对的数量极少时，插入排序的效率特别高
  甚至速度比 O(nlog^n^) 级别的快速排序还要快

数据量不是特别大的时候，插入排序的效率也是非常好的。

二分搜索

如何确定一个元素在数组中的位置？（假设数组里面全都是整数）

• 如果是无序数组，从第 0 个位置开始遍历搜索，平均时间复杂度：O(n)
  
• 如果是有序数组，可以使用二分搜索，最坏时间复杂度：O(log^n^)
  

二分搜索-思路

• 假设在 [begin, end) 范围内搜索某个元素 v，mid == (begin + end) / 2
• 如果 v < m，去 [begin, mid) 范围内二分搜索
• 如果 v > m，去 [mid + 1, end) 范围内二分搜索
• 如果 v == m，直接返回 mid

二分搜索-实现

/**
 * 二分搜索
 */
public static int search(int[] array, int v){
    if(array == null || array.length < 1) return -1;
    int begin = 0;
    int end = array.length;
    while(begin < end){
        int mid = (begin + end) >> 1;
        if(v < array[mid]){
            end = mid;
        }else if(v > array[mid]){
            begin = mid + 1;
        }else{
            return mid;
        }
    }
    return -1;
}

如果存在多个重复的值，返回是哪一个？

• 不确定

插入排序-二分搜索优化

在元素 v 的插入过程中，可以先二分搜索出合适的插入位置，再将元素 v 插入

假设有如下序列：

要求二分搜索返回的插入位置：第1个大于 v 的元素位置

• 如果 v 是 5，返回 2
• 如果 v 是 1，返回 0
• 如果 v 是 15，返回 7
• 如果 v 是 8，返回 5

插入排序-二分搜索优化-思路

• 假设在 [begin, end) 范围内搜索某个元素 v，mid == (begin + end) / 2
• 如果 v < m，去 [begin, mid) 范围内二分搜索
• 如果 v ≥ m，去 [mid + 1, end) 范围内二分搜索

插入排序-二分搜索优化-实例

插入排序-二分搜索优化-实现

/**
 * 插入排序-优化2
 * 二分搜索进行优化
 */
public class InsertionSort3 <T extends Comparable<T>> extends Sort<T>{

    @Override
    protected void sort() {
        for(int begin = 1; begin < array.length; begin++){
            // 将遍历到的元素插入到前面已经排好序的序列中
            insert(begin, search(begin)); //search() 查找到要插入的位置
        }
    }
    
    /**
     * 将source位置的元素插入到dest位置
     */
    private void insert(int source, int dest){
        T v = array[source]; // 备份要插入的元素
        // 将 [insertIndex, begin)范围内的元素往右边挪动一个单位
        for(int i = source; i > dest; i--){
            array[i] = array[i - 1];
        }
        array[dest] = v;
    }
    
    /**
     * 利用二分搜索找到index位置元素的待插入位置
     * 已经排好序数组的区间范围是[0，index）
     */
    private int search(int index){
        int begin = 0;
        int end = index;
        while(begin < end){
            int mid = (begin + end) >> 1;
            if(cmp(array[index], array[mid]) < 0){
                end = mid;
            }else{
                begin = mid + 1;
            }
        }
        return begin;
    }
    
}

生成 20000 个取值在[1, 10000] 的随机数进行排序：

复杂度与稳定性

使用了二分搜索后，只是减少了比较次数，但插入排序的平均时间复杂度依然是 O(n^2^)

• 最坏、平均时间复杂度：O(n^2^)
• 最好时间复杂度：O(n)
• 空间复杂度：O(1)
• 属于稳定排序