【数据结构与算法】系列二十四 - 插入排序

在了解插入排序之前，先简单认识一下什么是二分搜索。

一、二分搜索

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

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

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

1.1. 思路

假设在[begin, end)范围内搜索某个元素v，mid(中间索引) == (begin + end) / 2，m是最中间的元素。

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

1.2. 实例

示例一（搜索10）：

找到中间位置(0 + 7) / 2 = 3，索引3对应的元素是8，由于8 < 10，所以在索引3的右边继续二分搜索；
中间位置是(4 + 7) / 2 = 5，索引5对应的元素是12，由于12 > 10，所以在索引5的左边继续二分搜索；
中间位置是(4 + 5) / 2 = 4，索引4对应的元素是10，由于10 == 10，最终找到索引4的位置就是要搜索的结果。

示例二（搜索3）：

搜索方法同上面的示例一，只是到最后一步时发现中间位置(0 + 1) / 2 = 0，索引0对应的元素是2，由于2 < 3，所以需要到索引0的右边继续二分搜索。但是索引0右边没有元素了，最终没有找到要搜索的元素（begin是上一次搜索的mid，因为是向右查找，end保持不变，所以begin == end。如果是往左查找，begin保持不变，end等于mid，也是begin == end。所以当begin == end条件成立时，就无法搜索到对应结果，可以停止搜索。）。

1.3. 代码实现

// 查找某个元素在数组中是否存在
// 如果存在 返回对应位置索引
// 如果不在 返回-1
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 if (v > array[mid]) { // 往右查找
      begin = mid + 1;
    } else { // 找到目标
      return mid;
    }
  }
  return -1;
}

思考：如果存在多个重复的值，返回的是哪一个？这是不确定的。

二、插入排序

插入排序（Insertion Sort）非常类似于扑克牌的排序。每次从牌池中拿到牌插入到手中，使其变成有序的牌（手上的牌是有序的）。

2.1. 实现思路

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

2.2. 代码实现

public void insertionSort(Integer[] array) {
  for (int begin = 1; begin < array.length; begin++) {
    int cur = begin;
    while (cur > 0 && array[cur] < array[cur - 1]) {
      int tmp = array[cur];
      array[cur] = array[cur - 1];
      array[cur - 1] = tmp;
      cur--;
    }
  }
}

上面的代码还可以从插入时机进一步优化，优化前我们先了解一下什么是逆序对。

2.3. 逆序对

什么是逆序对（Inversion）？例如数组<2,3,8,6,1> 的逆序对为<2,1> <3,1> <8,1> <8,6> <6,1>共5个逆序对（一般情况下数组从左到右看，从小到大是正序，而逆序就是从大到小）。

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

如下图，逆序对达到最大值，每次拿到一个元素进行插入排序，都是插入到数组的最前面（即最远距离）。绿色区域就是排序所消耗的时间（时间复杂度 = 三角形面积 = n^2）。

最坏、平均时间复杂度：O(n^2)（原数据的逆序对达到最大值），最好时间复杂度：O(n)（原数据是升序的，只需要和前面的值进行比较），空间复杂度：O(1)，属于稳定排序。

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

2.4. 优化一

优化思路：将【交换】转为【挪动】

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

如下图，红色块是待插入元素，从红色块位置开始向左进行比较，只要发现比红色块值大的元素就让这个元素往右边进行挪动（同时记录当前挪动的位置），直到发现小于或等于红色块值的元素时，把元素插入到上次记录的位置。

public void insertionSort(Integer[] array) {
  for (int begin = 1; begin < array.length; begin++) {
    int cur = begin;
    // 待插入元素备份
    int v = array[cur];
    while (cur > 0 && array[cur] < array[cur - 1]) {
      // 挪动
      array[cur] = array[cur - 1];
      cur--;

    }
    array[cur - 1] = v;
  }
}

上面的优化在逆序对比较多的情况下效率越明显。但是需要和已排序好的每个元素进行比较，因为是和有序数据进行比较，所以使用二分搜索就能使比较效率提高不少。

2.5. 优化二

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

如上图，要求二分搜索返回插入位置的特点：第1个大于v的元素位置（保证了相等元素的数据稳定性）。

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

优化思路：

假设在[begin, end)范围内搜索某个元素v，mid(中间索引) == (begin + end) / 2，m是最中间的元素。

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

public class InsertionSort {
  public 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) {
    int v = array[source];
    for (int i = source; i > dest; i--) {
      array[i] = array[i - 1];
    }
    array[dest] = 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 (array[index] < array[mid]) { // 往左查找
        end = mid;
      } else { // 往右查找
        begin = mid + 1;
      }
    }
    return begin;
  }
}

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