初识插入排序
插入排序也是较为简单的一种排序算法。它的思想是，先将数组第一个元素，作为一个已经排好序的序列，然后将数组中剩下的元素，从左到右，每次取一个元素，插入到左侧的有序序列中的合适位置，不断扩大左侧有序序列的长度，直到整个数组有序。
图解如下
假设准备对如下数组进行插入排序
首先将第一个元素加入到有序序列中
然后取未排序部分的第一个元素，将该元素插入到左侧有序序列中合适的位置
未排序部分的第一个元素是3，发现3应该插入到9的前面
那么第一轮插入的结果如下
继续下一轮，取未排序部分的第一个元素，6
将6插入到左侧有序序列中的合适位置，即3和9之间
继续下一轮，取数组未排序部分第一个元素1，发现1应该插入到3的左侧
继续下一轮，4被插入到3和6之间
下一轮，2被插入到1和3之间
...... 最终，整个数组有序
注意：将一个数，插入到有序序列中的合适位置，这个过程可以有多种实现。最简单的一种是采用类似冒泡的过程，不断地比较和交换相邻2个数，一直把待插入元素交换到合适的位置。根据这个思路，插入排序的代码如下
public void insertSort(int[] array) {
/*不断地将数字插入到合适的位置，扩大有序序列的边界 */
for (int sortedSize = 1; sortedSize < array.length; sortedSize++) {
for (int i = sortedSize - 1; i >= 0 ; i--) {
if (array[i + 1] < array[i]) {
swap(array, i + 1, i);
} else {
break;
}
}
}
}
优化思路
思路一
将比较和交换，改为单向赋值
上述的插入排序，实际还有可优化的空间。因为每一轮排序，实际只要找到一个合适的位置即可。而上面的实现，找到合适的插入位置，这个过程，是通过不断地进行元素交换来完成的。而每次发生2个数的交换，需要3次赋值的操作。换一种思路，我们其实可以把待插入的元素先暂存起来，然后将待插入元素和有序序列中的元素从右到左依次做比较，只要有序序列中的元素比待插入元素大的，就将其在有序序列中的位置右移一位，这样，原先每次需要交换的地方，改为了单向赋值，就只需要一次赋值操作。最后找到合适位置后，将暂存的待插入元素直接赋值即可。图解如下
假设插入排序过程中某个时刻的数组状态如下
下一个待插入的元素为5，将其暂存起来，然后从有序序列最右侧的元素开始，依次和5做比较，发现9比5大，则将9单向往右赋值，覆盖掉了5，逻辑上讲，原先9的位置其实就没用了，因为9已经被右移了一位，而由于我们暂存了5，所以不用担心丢失。没用的元素，下图用紫色做了标记
然后往左，看有序序列中的下一个元素，8
比较8和5，发现8比5大，则8也向右赋值，覆盖掉紫色的9
继续往左，
比较2和5，发现2小于5，说明找到了合适的插入位置，将之前暂存的5，单向赋值给紫色元素的位置
就完成了这一轮的插入排序
逻辑上讲，相当于将有序序列中较大的元素，依次往右挪一个位置，留出一个空位给待插入元素，由于是单向赋值，所以和前面的比较交换的方式相比，少了很多次的赋值操作，所以性能会提高一些。但是需要一个额外的空间，来暂存待插入元素。根据这个思路，写成代码如下
public void insertSortV1(int[] array) {
for (int sortedSize = 1; sortedSize < array.length; sortedSize++) {
int temp = array[sortedSize];
int i = sortedSize;
while (i > 0 && array[i - 1] > temp) {
array[i] = array[i - 1];
i--;
}
array[i] = temp;
}
}
思路二
将线性查找，改为二分查找
由于每一轮插入排序，关键的地方在于找到合适的插入位置，这其实是一个查找的过程。上面的实现，使用的都是线性查找，即从有序序列的最右端，依次往左比较，直到找到合适位置。这种查找的时间复杂度是线性的，即O(n)。我们可以针对这个查找的过程进行优化，将线性查找替换为二分查找，二分查找是跳跃式的查找，每次取待查找序列的中间位置，与目标值做比较，若小于目标值，则继续在右半边部分进行查找，若大于目标值，则继续在左半边部分进行查找。二分查找每次能缩小一半的查找空间，其时间复杂度为O(log(n))
使用二分查找优化后的代码如下
/**
* 二分查找
* @param left 左边界(inclusive)
* @param right 有边界(inclusive)
* */
private int binarySearch(int[] array, int left, int right, int target) {
while (left <= right) {
/* 取中间位置 */
int mid = (left + right) >> 1;
/*
* 临界情况有2种
* 1. 待查找区间还剩2个数 -> 此时 right = left + 1 , mid = left
* 1.1 若判断 arr[mid] > target, 则该查找左半部分，此时应该插入的位置是mid，也就是left
* 1.2 若判断 arr[mid] < target, 则该查找右半部分，此时应该插入的位置是mid + 1，也就是更新后的left
* 2. 待查找区间还剩3个数 -> 此时 right = left + 2 , mid = left + 1
* 2.1 若判断 arr[mid] > target, 则查找左半部分，回到情况1
* 2.2 若判断 arr[mid] < target，则查找右半部分，更新完后下一轮循环 left = right = mid，
* 若arr[mid] > target，则应插入的位置是left，若arr[mid] < target，则更新完后的left是应插入的位置
* */
if (array[mid] > target) {
/* 往左半边查找 */
right = mid - 1;
} else if (array[mid] < target) {
/* 往右半边查找 */
left = mid + 1;
} else {
/* 相等了，返回待插入位置为 mid + 1 */
return mid + 1;
}
}
return left;
}
@Override
public void insertSortBinarySearch(int[] array) {
for (int sortedSize = 1; sortedSize < array.length; sortedSize++) {
int temp = array[sortedSize];
/* 获得待插入的位置 */
int insertPos = binarySearch(array, 0, sortedSize - 1, temp);
/* 将待插入位置之后的有序序列，全部往后移一位 */
for (int i = sortedSize; i > insertPos ; i--) {
array[i] = array[i - 1];
}
array[insertPos] = temp;
}
}
思路三
希尔排序
希尔排序是插入排序的变种，其核心思想是引入了一个步长的概念，希尔排序使用步长将数组切分成很多个小数组，在每个小数组中利用插入排序，然后逐渐缩小步长，最后步长缩小到一，步长为一的希尔排序，就是上面的简单插入排序。相比简单插入排序，希尔排序的好处在于可以跨越多个位置来移动元素，而原先的简单插入排序，必须挨个挨个的比较以便找到合适的插入位置。
希尔排序的图解如下，初始步长一般设为数组长度的一半
上述数组就按照gap=4被划分成了4组元素。位置间隔等于gap的元素被分为了同一个组。第一组是[1,5,9]，（5和1间隔了4个位置，9和5又间隔了4个位置...）被标注为了浅蓝色，第二组是[4,7]，被标注为了淡黄色，第三组是[2,6]，被标注为了浅紫色，第四组为[8,3]，被标注为了橘色。对每组元素，分别进行简单插入排序，随后缩小gap的值，继续对每组进行插入排序，直到gap被缩小为1，最后一轮相当于进行了一次简单插入排序。由于插入排序在数组基本有序的情况下，能够取得很高的效率，而希尔排序，引入了步长的概念，能够让元素跨越多个位置进行插入排序，而不必挨个挨个的进行操作。每一轮希尔排序后，整个数组都变得更加整体有序（可以理解为，一轮希尔排序后，排在整个数组前面位置的元素，都是每个分组中最小的元素，而排到后面的元素，都是每个分组中较大的元素）
第一轮希尔排序后，数组状态如下（只交换了3和8的位置）
第二轮希尔排序，gap缩小一半，变为2
分别对2组元素进行插入排序，结果如下（第1组，浅蓝色标注，没有任何变化；第2组，橙色标注，只交换了3和4的位置）
最后，gap=1，进行最后一轮希尔排序（此时相当于进行一次简单插入排序）
肉眼观察可知，最后这轮只需要交换2和3，6和7。两次交换，即完成排序
上述数组经过希尔排序，共执行了4次交换操作即完成排序，非常高效，而若采用简单插入排序，交换操作的次数是要大于4的。由此可见希尔排序的强大。根据上述内容，也可更好地理解希尔排序又被称为缩小增量排序的含义。步长，增量，gap都是同一个东西。增量序列的选择也会影响到希尔排序的效率，通常选择初始增量为数组长度一半，然后每次减半的增量序列即可。
希尔排序的代码实现如下
public void shellSort(int[] array) {
for (int gap = array.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {
int j = i;
int temp = array[i];
/* 这里没有采用二分查找，直接使用的线性查找 */
while (j - gap >= 0 && array[j - gap] > temp) {
array[j] = array[j - gap];
j -= gap;
}
array[j] = temp;
}
}
}
注意代码实现中，是直接从gap之后的位置，遍历到数组最后一个元素，对每个元素，以gap为增量，向前进行直接插入排序。这与图解中分别对每组元素进行插入排序的描述，有一些差别。这样写的好处是，整个希尔排序的代码只需要3层循环，并且比较容易理解。若按照图解的描述，每次以一组元素的插入排序作为一个循环，则写出的代码需要4层循环，不易理解。有兴趣的读者，可以参考下面的代码
public void shellSort(int[] array) {
int gap = array.length / 2;
while (gap >= 1) {
for (int i = 0; i < gap; i++) {
/* 这一层循环就是对每一组元素进行插入排序 */
for (int j = i; j + gap < array.length; j += gap) {
int pos = j + gap;
while (pos - gap >= 0) {
if (array[pos] < array[pos - gap]) {
swap(array, pos, pos - gap);
pos -= gap;
} else {
break;
}
}
}
}
gap /= 2;
}
}
性能测试
使用规模从1万到50万的随机数组，对各个插入排序的算法进行了性能测试，绘制成折线图如下
可见，希尔排序的性能完爆其他几个版本，使用了二分查找进行优化的次之，使用单向赋值优化的再次之，未优化的性能最差。
