封面画师：Nengoro(ネんごろぅ) 封面ID：78236624

本文参考视频：小马哥教育(SEEMYGO) 2019年恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化 Data Structure Visualizations

排序结果：本文统一以升序为例。

1. 范型的引入

在上文【排序算法】冒泡、选择和堆排序中的末尾部分提出了一个问题：编写的排序算法只能够对整型数据进行排序，无法做到对浮点型、自定义类型的序列进行排序。为此可以引入范型，增加编写的排序算法的适用性。

1.1 父类的修改

在【排序算法】冒泡、选择和堆排序一文中抽取了父类 Sort，在编写排序算法时都继承这个父类，以达到代码复用，提高代码的整洁度。

要引入范型，需要从源头开始修改，因此先修改父类。

修改父类很简单，给父类添加范型，然后将成员变量 array 数组的类型也改成范型，同时将代码中涉及到 array 数组的变量类型都改为范型。

数组类型修改为范型后，会发现比较方法、交换方法出现了问题。

交换方法的修改很简单，将 tmp 的类型修改为范型即可。但对于比较方法就不适用了，因为引入了范型，不知道数据的具体类型是什么，可能是默认有比较性的数据，比如整型、浮点型等，也有可能是自定义类型，而这些类型默认没有比较性，无法直接使用减法运算进行比较。

可以 规定进行排序的数据必须具有可比较性， 换句话说，范型必须实现 Comparable 接口，然后在比较方法中，直接调用 Comparable 接口的 compareTo 方法进行比较即可。

最终，修改完的父类 Sort 如下：

/**
 * @author 默烦
 * @date 2020/8/11
 */
public abstract class Sort<E extends Comparable<E>> implements Comparable<Sort<E>> {
    protected E[] array;
    // 省略其他成员变量
    // --smip--

    public void sort(E[] array) {
        if (array == null || array.length < 2) return;
        this.array = array;
        long begin = System.currentTimeMillis();
        sort();
        time = System.currentTimeMillis() - begin;
    }

    protected abstract void sort();

    @Override
    public int compareTo(Sort<E> o) {
        int result = (int) (time - o.time);
        if (result != 0) return result;
        result = cmpCount - o.cmpCount;
        if (result != 0) return result;
        return swapCount - o.swapCount;
    }

    /**
     * 返回值等于0，代表array[i1] == array[i2]
     * 返回值小于0，代表array[i1] < array[i2]
     * 返回值大于0，代表array[i1] > array[i2]
     */
    protected int cmp(int i1, int i2) {
        cmpCount++;
        return array[i1].compareTo(array[i2]);
    }

    protected int cmp(E v1, E v2) {
        cmpCount++;
        return v1.compareTo(v2);
    }

    protected void swap(int i1, int i2) {
        swapCount++;
        E tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }
    
    // 省略未修改的方法
    // --snip--

}

1.2 子类的调整

编写的子类也需要引入范型。

未优化的冒泡排序

public class BubbleSort1<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                }
            }
        }
    }
}

冒泡排序优化一

public class BubbleSort2<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            boolean sorted = true;
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    sorted = false;
                }
            }
            if (sorted) break;
        }
    }
}

冒泡排序优化二

public class BubbleSort3<E extends Comparable<E>> extends Sort<E>{
    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            // sortedIndex的初始值在数组完全有序的时候有用
            int sortedIndex = 1;
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
    }
}

选择排序

public class SelectionSort<E extends Comparable<E>> extends Sort<E>{

    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            int maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
                //  if (array[maxIndex] < array[begin]) {
                if (cmp(maxIndex,begin) < 0){
                    maxIndex = begin;
                }
            }
            swap(maxIndex, end);
        }
    }
}

堆排序

public class HeapSort<E extends Comparable<E>> extends Sort<E> {
    private int heapSize;

    @Override
    protected void sort() {
        // 原地建堆 批量建堆
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
        while (heapSize > 1) {
            // 交换堆顶和尾部元素
            swap(0, --heapSize);
            // 对0位置元素进行下滤（恢复堆的性质）
            siftDown(0);
        }
    }

    /**
     * 让索引为 index 的元素进行下滤
     *
     * @param index
     */
    private void siftDown(int index) {
        E element = array[index];
        int half = heapSize >> 1;
        // 第一个叶子节点的索引 = 非叶子节点的数量
        while (index < half) { // 必须保证index位置是非叶子节点
            /**
             * index 位置的节点的子节点有两种情况
             * 1. 只有左子节点
             * 2. 同时有左子节点、右子节点
             */
            // 默认为左子节点的索引
            int childIndex = (index << 1) + 1;
            E child = array[childIndex];

            // 右子节点索引
            int rightIndex = childIndex + 1;
            // 选出最大的子节点
            if (rightIndex < heapSize && cmp(array[rightIndex], child) > 0) {
                // childIndex = rightIndex;
                child = array[childIndex = rightIndex];
            }

            if (cmp(element, child) >= 0) break;
            // 将子节点存放到index位置
            array[index] = child;
            // 重新设置index
            index = childIndex;
        }
        array[index] = element;
    }
}

1.3 测试的调整

public static void main(String[] args) {

    Integer[] array = Integers.random(10000, 1, 20000);
    testSorts(array,
              new BubbleSort1<Integer>(),
              new BubbleSort2<Integer>(),
              new SelectionSort<Integer>(),
              new HeapSort<Integer>(),
              new BubbleSort3<Integer>());
}

@SafeVarargs // 消除警告
static void testSorts(Integer[] array, Sort<Integer>... sorts) {
    for (Sort<Integer> sort : sorts) {
        // 将原数据拷贝一份
        Integer[] newArray = Integers.copy(array);
        sort.sort(newArray);
        // 验证排序是否正确 结果是否升序
        Asserts.test(Integers.isAscOrder(newArray));
    }
    // 结果排序
    Arrays.sort(sorts);
    // 打印结果
    for (Sort<Integer> sort : sorts) {
        System.out.println(sort);
    }
}

工具类 Integers 和断言工具类 Asserts 没有发生变化，不必进行修改。

引入范型后，编写的几个排序算法就可以应用在不同的类型中了。

2. 稳定性评估

【排序算法】冒泡、选择和堆排序中对三种算法都进行了稳定性评估，但那种稳定性评估是思考后得出的结论，并不是经过计算后得到的。

为了更有说服力，可以给算法增加一个评估稳定性的方法。由于每个排序算法都需要评估稳点性，因此可以将评估稳定性的方法放在父类 Sort 中。

排序的稳定性是指：如果相等的两个元素，在排序前后的相对位置保持不变，那么这就是稳定的排序算法。

新建一个实体类 Student 测试算法的稳定性：

public class Student implements Comparable<Student> {
    /**
     * 为了测试，我们将访问修饰符设置为public
     * 正常开发中应该是私有的，具备封装性
     * 然后使用Get/Set方法来进行修改
     */
    public int score;
    public int age;

    public Student(int score, int age) {
        this.score = score;
        this.age = age;
    }

    @Override
    public int compareTo(Student o) {
        return age - o.age;
    }
}

在创建 Student 对象时，每个 Student 对象中的 age 值都相等，但 score 逐渐增长，之后对这些对象进行排序，查看排序后序列中每个 Student 对象的位置有没有发生改变，如果发生了变化，就证明使用的排序算法是不稳定的。

重写 Sort 类中的 toString() 方法：

@Override
public String toString() {
    String timeStr = "耗时：" + (time / 1000.0) + "s(" + time + "ms)";
    String compareCountStr = "比较：" + numberString(cmpCount);
    String swapCountStr = "交换：" + numberString(swapCount);
    /**
     * 注意这里是将isStable()方法放在最后来计算的
     * 因为调用isStable()方法时会进行排序
     * 排序的时候就会对cmpCount、swapCount的值产生影响
     * cmpCount、swapCount会在前面进行拼接
     * 等到拼接完，再调用isStable()就不会打印出变化了的比较、交换次数了
     */
    String stableStr = "稳定性：" + isStable();
    return "【" + getClass().getSimpleName() + "】\n"
            + stableStr + " \t"
            + timeStr + " \t"
            + compareCountStr + "\t "
            + swapCountStr + "\n"
            + "------------------------------------------------------------------";
}

编写isStable()方法，用于测试稳定性：

PS：选择排序不能用这个方式进行评估，选择排序需要特殊处理。

private boolean isStable() {
    // 特殊处理选择排序
    if (this instanceof SelectionSort) return false;
    Student[] students = new Student[20];
    for (int i = 0; i < students.length; i++) {
        // 创建有序的序列
        students[i] = new Student(i * 10, 10);
    }
    sort(((E[]) students));    // 进行排序
    for (int i = 1; i < students.length; i++) {
        int score = students[i].score;
        int prevScore = students[i - 1].score;
        // 检查序列顺序是否发生改变
        if (score != prevScore + 10) return false;
    }
    return true;
}

对编写的三种排序算法进行测试，测试结果如下：

可以清楚地看到，堆排序和选择排序的稳定性是 false，冒泡排序的稳定性是 true，与最初的分析结果一致。

3. 插入排序

3.1 流程与实现

插入排序（Insertion Sort），类似扑克牌的排序。

插入排序升序排序流程：

在执行的过程中，将序列分成两个部分，头部序列是已经排序好的，尾部是待排序的；
从头开始扫描每一个元素，每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序

再详细一点：假设头部序列是已经升序排序好的序列，选取最近的待排序元素，使用此元素与头部序列的末位元素进行比较，如果待排序元素比末位元素小，就交换两者的位置，之后让其依次与前一个元素进行比较，直到待排序元素大于头部序列中的某个元素或无法再继续进行比较。

插入排序 升序排序 初步实现如下（头部已排序好，尾部是待排序的）：

public class InsertionSort<E extends Comparable<E>> extends Sort<E> {
    @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--;
            }
        }
    }
}

与前几种的排序算法进行测试比较：

当然也可以将头部序列看成是待排序的，尾部是已经排序好的，扫描到元素时，将其插入到尾部合适的位置。比如：

稳定性

使用测试方法可知插入排序是 稳定的。简单分析一下：

假设现有一个序列 [10a, 10b, 5, 17, 9]，前两个数是都表示数字 10，加个字母便于区分。

在插入排序中，比较的逻辑是：cmp(cur, cur - 1) < 0，表示前者小于后者时才进行交换。对于给出的序列，10b 等于 10a，而非小于 10a，因此不会进行交换，继续进行插入排序，最后 10a 与 10b 的相对位置不会发生改变，也表示插入排序是一个稳定的排序算法。

3.2 逆序对

逆序对（Inversion），什么是逆序对？

设 $A$ 是一个有 $n$ 个数字的有序集，并且 $n \gt 1$ ，其中所有数字各不相同。

如果存在正整数 $i, j$ 使得 $1 \le i \lt j \le n$ 时 $A[i] \gt A[j]$ ，则有序对 <A[i], A[j]> 称为 A 的一个逆序对，也称作逆序数。

现有一个数组 [2, 3, 8, 6, 1]，那么这个数组的逆序对为：<2,1>，<3,1>，<8,1>，<8,6>，<6,1>，共 5 个逆序对。

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

也就是说：逆序对的数量越多，插入排序的时间复杂度越高。

这是为什么呢？

在上图中，最开始给出了一个待排序序列，要求使用 插入排序 对这个序列 进行升序排序，最终排序结果是最后一行。

待排序序列是 逆序对最多 的一种极端情况，进行插入排序时，每一个插入元素要和左边已经排序好的所有元素依次进行比较，最后把这个插入元素放在左边已排序好序列的首位。

那上述序列使用插入排序进行升序排序的时间复杂度为多少呢？

在第一行中，交换一次；第二行中，交换两次；第三行中，交换三次；第 n 行时，交换 n 次。时间复杂度为交换次数之和，即时间复杂度为 $O(n^2)$ 。（时间复杂度也相当于蓝绿色三角形的面积）

插入排序时间复杂度

最坏、平均时间复杂度： $O(n^2)$

对一个序列使用插入排序进行升序排序时，如果这个序列本来就是升序的，这时插入排序的时间复杂度为 $O(n)$ ，也是插入排序的最好时间复杂度。

空间复杂度： $O(1)$

当逆序对的数量极少时，插入排序的效率特别高，甚至速度比 $O(nlogn)$ 级别的快速排序还要快。数据量不是特别大时，插入排序的效率也非常好。

3.3 插入排序优化一

最开始使用插入排序时，使用的是【交换】，可以将【交换】转为【挪动】。

具体步骤是：

先将待插入元素进行备份
从头部有序序列的末位开始，寻找最后一个大于待插入元素的数据，使其与后序数据都朝序列尾部方向挪动 1 个位置
最后将待插入元素放入挪动后空下的位置

那这样为什么能优化呢？其实很简单。😉

对于上图图解来说：

未优化时：索引 5 的元素向前交换三次，交换一次执行三行代码，一共执行九行代码。

优化后：备份索引 5 的元素，执行一行代码；挪动索引 3、4、5 的元素，执行三行代码；插入备份元素，执行一行代码，共执行五行代码。

可以很明显的发现优化后代码执行总行数更少，同时当右边排序好的序列元素数量越多时，提升的效率越高。

public class InsertionSort2<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            E v = array[cur]; // 备份元素
            while (cur > 0 && cmp(v, array[cur  - 1]) < 0) {
                array[cur] = array[cur - 1]; // 元素多动
                cur--;
            }
            // 元素插入
            array[cur] = v;
        }
    }
}

优化后的测试：

优化后的插入排序交换次数为 0 ，因为从交换变成了挪动，并没有进行交换，所以 0 是正确的。将未优化和优化后的插入排序进行对比可以发现，耗时相差并不大，因为只是减少了代码的执行行数。

优化后，减少了 while 循环中执行的代码行数，从原来的三行代码（交换）变成了一行代码（挪动）。

while 循环执行次数越多，能够减少的代码执行行数也越多，优化效果越明显。

从另一方面来说，while 循环执行次数越少，插入排序效率越高。

while 循环执行的次数多，表明交换的次数（未优化前）或挪动的次数（优化后）越多，即数组中的逆序对越多，这时插入排序的效率也越低，这又一次验证了： 逆序对的数量越多，插入排序的时间复杂度越高。

4. 二分搜索

4.1 需求的提出

应该怎么确定一个元素在数组中的位置呢？（假设数组里面全都是整数）

如果是一个无序数组，从第 0 个位置开始遍历搜索，平均时间复杂度为 $O(n)$ ：

如果是有序数组，可以使用二分搜索（Binary Search），它最坏时间复杂度为 $O(logn)$ ：

4.2 思路讲解

对一个升序数组，使用二分搜索：

假设在 [begin, end) 范围内搜索某个元素 v ，mid == (begin + end) / 2

PS： end 表示数组长度，而不是数组的最大下标。

如果 v < m ，去 [begin, mid) 范围内二分搜索
如果 v > m ，去 [mid + 1, end) 范围内二分搜索
如果 v == m ，直接返回 mid

二分搜索示例

在下列升序数组中搜索存在的数字 10 ：

在下列升序数组中搜索不存在的数字 3 ：

在选取 end 的值时，是直接将 数组的长度 赋值给 end 的，而 begin 是数组的第一个索引 0 。

因此， end 一定是大于 begin 的，而当 end 等于 begin 时，表明查找的元素在数组中不存在。😏

为什么要将 end 设置成数组长度，而不是设置成数组的最大索引值呢？

如果想要求得从 begin 到 end 之间有多少个元素，只需要使用 end - begin 即可。如果将 end 设计成数组的最大索引值，那么在求 begin 到 end 之间的元素个数时，就需要 end - begin + 1，这样做岂不是很麻烦？😰

从这里也可以得出一个启发：在设计区间范围时，尽量是 左闭右开 的，这样会让编码变得简单易懂。😝

4.3 代码实现

限定数组类型为 int，在升序数组 array 中搜索 v：

public class BinarySearch {
    public static int indexOf(int[] array, int v){
        if (array == null || array.length == 0) 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;
    }
}

简单的测试：

public static void main(String[] args) {
    int[] array = {2, 4, 6, 8, 10, 12};
    Asserts.test(BinarySearch.indexOf(array, 4) == 1);
    Asserts.test(BinarySearch.indexOf(array, 2) == 0);
    Asserts.test(BinarySearch.indexOf(array, 10) == 4);
    Asserts.test(BinarySearch.indexOf(array, 56) == -1);
}

public class Asserts {
   public static void test(boolean value) {
      try {
         if (!value) throw new Exception("测试未通过");
      } catch (Exception e) {
         e.printStackTrace();
      }
   }
}

如果一个数组中存在多个重复的值 A，使用二分搜索寻找 A 的索引时，返回的索引是不确定的。

4.4 获取插入位置

插入排序优化分析

前文介绍了插入排序和二分搜索，那这两个有什么关系吗？

插入排序对一组乱序数据进行排序，二分搜索是对一组排序好的数据进行查找，怎么看都没关系啊。😟

非也非也。还记得插入排序会把序列分成两部分吗？一部分是已经排序好的，另一部分是待排序的，然后需要从待排序的那一部分中挑选一个元素将其插入到已经排序好的序列中，这时需要确定插入的位置，而这个位置的确定就可以使用二分搜索进行查找。

使用二分搜索对插入排序进行优化时，不能直接使用前面编写的二分搜索代码，主要原因有二：

如果要将一个元素插入到已经排序好的序列中，并且插入元素是不存在于排序好的序列中，使用原本的二分搜索就会返回 -1 ，这显然是憨憨嘛
同时，如果插入一个在已排序好的序列中存在的数据，使用原本的二分搜索会返回这个数据的索引，然后用新数据覆盖旧数据？

那么应该怎么做呢？

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

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

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

获取插入位置思路

假设在 [begin, end) 范围内搜索某个元素 v ，mid == (begin + end) / 2

PS： end 表示数组长度，而不是数组的最大下标。

如果 v < m ，去 [begin, mid) 范围内二分搜索
如果 v >= m ，去 [mid + 1, end) 范围内二分搜索

为了保证插入排序的稳定性，当插入元素与 m 相等时，要 找到第一个大于插入元素的位置，然后将插入元素插到那个位置。

注意与前文二分搜索思路的比较！

获取插入位置实例

搜索数字 5 ：

搜索数字 1：

搜索数字 15：

搜索数字 8：

存在多个相同元素时，搜索数字 8：

获取插入位置的编码实现

/**
 * 查找 v 在有序数组array中的待插入位置
 */
public static int search(int[] array, int v) {
    if (array == null || array.length == 0) return -1;
    int begin = 0;
    int end = array.length;
    while (begin < end) {
        int mid = (begin + end) >> 1;
        if (v < array[mid]) {
            end = mid;
        } else {
            begin = mid + 1;
        }
    }
    return begin;
}

简单的测试：

public static void main(String[] args) {
    int[] array = {2, 4, 8, 8, 8, 12, 14};
    Asserts.test(BinarySearch.search(array, 5) == 2);
    Asserts.test(BinarySearch.search(array, 1) == 0);
    Asserts.test(BinarySearch.search(array, 15) == 7);
    Asserts.test(BinarySearch.search(array, 8) == 5);
}

4.5 二分搜索通用模板

本节参考：二分查找为什么总是写错？- 五点七边

二分搜索逻辑虽然简单，但想要一次性写出符合要求的二分搜索还是有些难度，尤其是在边界值的处理上，总是错了又错。针对这个问题，给出以下二分搜索通用模板，编写合适的 Lambda 表达式即可实现符合要求的二分搜索。

/**
 * 根据指定条件，使用二分搜索获取目标元素的下标
 *
 * @param array       数组
 * @param isBlue      中值判断条件
 * @param returnValue 返回值
 * @param <T>         数组类型
 * @return 目标元素下标
 */
public static <T> int binarySearchTemplate(T[] array,
                                           Predicate<T> isBlue,
                                           BiFunction<Integer, Integer, Integer> returnValue) {
    if (array == null || array.length == 0) return -1;
    int l = -1, r = array.length;
    while (l + 1 != r) {
        int m = (l + r) >> 1;
        if (isBlue.test(array[m])) {
            l = m;
        } else {
            r = m;
        }
    }
    return returnValue.apply(l, r);
}

怎么使用呢？看一个使用示例：

public static void main(String[] args) {
    Integer[] array = {1, 2, 3, 5, 5, 5, 8, 9};
    // 第一个大于等于 5 的元素 --> 3，注意，返回值是索引
    System.out.println(binarySearchTemplate(array, i -> i < 5, (l, r) -> r));
    // 最后一个小于 5 的元素 --> 2
    System.out.println(binarySearchTemplate(array, i -> i < 5, (l, r) -> l));
    // 第一个大于 5 的元素 --> 6
    System.out.println(binarySearchTemplate(array, i -> i <= 5, (l, r) -> r));
    // 最后一个大于等于 5 的元素 --> 5
    System.out.println(binarySearchTemplate(array, i -> i <= 5, (l, r) -> l));
}

如何理解这个通用模板？又该如何使用？

模板的理解

给出的二分搜索模板与常见的二分搜索实现不太一样，因此要想习得本节精髓，需忘却以前对二分搜索的理解，如果原本就不会二分搜索，那将是极好的。

言归正题，给定一个长度为 $N$ 的有序数组 array，假设第 $K$ 个元素即为所求目标元素。不妨以此为界限，将原数组中的元素进行染色，那么前 $K$ 个元素将被染成蓝色，而后 $N - K$ 个元素被染成红色：

那第 $K$ 个元素在哪里呢？这里有一种朴素算法：

为求得第 $K$ 个元素的位置，可以设置一个蓝色指针，一开始指向 最左边，然后不断向右移动，直到移动到蓝红边界。当然，也可以设置一个红色指针，一开始指向 最右边，然后不断向左移动，直到移动到蓝红边界。

使用这种方式的时间复杂度是 $O(n)$ 。

由于目标数组是有序的，因此在搜索目标元素时，可以使用二分搜索。

在朴素算法中，蓝红指针不断移动的过程，可以理解成蓝、红区域不断拓展的过程。

在最开始，不知道数组中任何元素的颜色，那么此时可以查看整个数组中 最中间 元素的颜色。假设这个元素的颜色是蓝色，那这就意味着这个元素及其之前的所有元素都是蓝色：

此时可以将蓝色区域拓展到这个元素所在的位置：

然后继续这样的操作，查看未确定颜色的子序列中最中间元素的颜色，假设这个元素的颜色是红色，这意味着这个元素及其之后的所有元素都是红色：

此时将红色区域拓展到这个元素所在的位置：

不断重复上述操作，直到找到蓝红边界，找到目标元素：

如果将这个搜索过程用代码编写出来，就可以得到本节开始给出的二分搜索通用模板代码：

初始：l 指向蓝色区域，r 指向红色区域；
循环：l 与 r 快速向蓝红边界逼近，保持 l、r 颜色不改变；
结束：l、r 刚好指向蓝红边界，按需返回 l 或 r。

细节处理

1、为什么 l 的初始值是 -1，r 的初始值是 N？

如果数组中所有元素都是红色，此时 l 不能指向任何元素；如果数组中所有元素都是蓝色，r 也不能指向任何元素。基于这两个原因，l 与 r 的初始值应该是 -1 和 N，即一开始不指向任何元素。

2、l + 1 != r 时才进去循环体，会不会陷入死循环？

当 l + 1 = r 时，此时 l 指向的元素的下一个元素就是 r，会马上退出循环体；
当 l + 2 = r 时，l 指向的元素与 r 指向的元素之间隔了一个元素，继续执行循环体内代码，计算 m 值，m 指向的元素恰好是 l 与 r 中间的那个元素，接下来要么移动 l，要么移动 r，最终会变成第一种情况；
当 l + 3 = r 或其他情况时，总能转换到 l + 1 = r，进而退出循环，因此程序不会陷入死循环。

3、程序中间会判断索引 m 处元素的颜色，那 m 始终处于 $[0, N)$ 以内吗？

已知 $l_{min} = -1$ ，由于 $l + 1 \ne r$ 时才能进入循环体，因此 $r_{min} = 1$ ，当 $l$ 与 $r$ 取最小值时， $m$ 取最小值，此时 $m_{min} = 0$ 。

已知 $r_{max} = N$ ，由于 $l + 1 \ne r$ 时才能进入循环体，因此 $l_{max} = N - 2$ ，当 $l$ 与 $r$ 取最大值时， $m$ 取最大值，此时 $m_{max} = N - 1$ 。

综上可得： $m \in [0, N)$

4、更新蓝红指针时，能不能写成 l = m + 1 或者 r = m - 1？

不能。假设 m 恰好指向蓝色区域的 最后一个 元素，如果 l = m + 1，此时 l 就会指向第一个红色元素，造成错误；假设 m 恰好指向红色区域的 第一个 元素，如果 r = m - 1，此时 r 就会指向最后一个蓝色元素，造成错误。

使用细节

共两个细节：

根据需求确定蓝红边界，进而确定 isBlue 函数式接口的实现；
确定最终应该返回 l 还是 r。

假设有一个升序排序的数组，需要确定第一个大于 5 的元素的索引：此升序数组中可能存在多个等于 5 的元素，因此 最后一个 等于 5 的元素所在的位置就是蓝红边界，蓝色区域中的元素都 小于等于 5，故：isBlue = i -> i <= 5;。目标元素是第一个大于 5 的元素，这个元素处于红色区域，因此最终应该返回 r。

假设有一个升序排序的数组，需要确定最后一个小于 5 的元素的索引：此升序数组中可能存在多个等于 5 的元素，因此 第一个 等于 5 的元素所在的位置就是蓝红边界，蓝色区域中的元素都 小于 5，故：isBlue = i -> i < 5。目标元素是最后一个小于 5 的元素，这个元素处于蓝色区域，因此最终应该返回 l。

5. 二分搜索优化插入排序

优化后的插入排序流程

扫描数组，记录当前位置的元素
使用二分搜索获取当前位置元素的插入位置
挪动元素，为插入元素（当前元素）腾出位置
将当前元素放在拆入位置

代码实现

/**
 * @author 默烦
 * @date 2020/8/12
 */
public class InsertionSort3<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            E v = array[begin];
            int insertIndex = search(begin);
            // 将[insertIndex, begin)范围内的元素往右边挪动一个单位
            // 以下两种方式都可以，选用第二种可以减少一次减法运算
//            for (int i = begin - 1; i >= insertIndex; i--) {
//                array[i + 1] = array[i];
//            }
            for (int i = begin; i > insertIndex; i--) {
                array[i] = array[i - 1];
            }
            array[insertIndex] = v;
        }
    }

    /**
     * 利用二分搜索找到 index 位置待插入元素的插入位置
     * 已经排好序数组的区间范围是 [0, index)
     * @param index 待插入元素索引
     * @return 插入位置
     */
    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;
    }
}

再次优化后进行的测试：

根据上图可知，使用二分搜索优化后的耗时得到了明显的减少，证明优化效果还是很显著的。

为了让编写的代码逻辑更加清晰，更便于阅读，可以再对其重构一下，主要逻辑不变：

/**
 * @author 默烦
 * @date 2020/8/12
 */
public class InsertionSort3<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            insert(begin, search(begin));
        }
    }

    /**
     * 将source位置的元素插入到dest位置
     * @param source 待插入元素位置
     * @param dest 插入位置
     */
    private void insert(int source, int dest){
        E v = array[source];
        for (int i = source; i > dest; i--) {
            array[i] = array[i - 1];
        }
        array[dest] = v;
    }

    private int search(int index) { // search()方法代码不变
        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;
    }
}

在使用二分搜索来查找元素插入的位置后，插入排序的效率得到了显著提升，但二分搜索只是减少了比较次数，插入排序的平均时间复杂度依然是 $O(n^2)$ 。因为使用二分搜索查找插入元素的位置的时间复杂度为 $O(logn)$ ，但找到插入位置后，还要进行时间复杂度为 $O(n)$ 级别的挪动操作，而这还只是一个元素的插入挪动，如果拥有 $n$ 个元素，最终的平均时间复杂度还是 $O(n^2)$ 。