思路
插入排序假设排序中的数组分两段，已排好序的前半部分data[0...i)和未排序的后半部分data[i...data.length)。
循环遍历数组,每次将data[i]插入到已排好序的前半部分，排序部分每次递增1直至全部排序完成。
插入排序的循环不变量是：data[0...i)是已排好序的部分。
假设有如下数组：
image.png
假设排序好了三个元素：
image.png
此时，需要将索引为i处元素2插入到正确的位置：
实现方式就是将2每次都跟前一元素相比较，如果2比它小，那么交换位置，直至碰到比2大的数，或者2已经到索引为0的位置了。
image.png
初步实现
public static <E extends Comparable<E>> void sort(E[] data) {
// 第一重循环，维持循环不变量data[0 ... i)中的元素都是已排好序的
for (int i = 0; i < data.length; i++) {
// 第二重循环，将data[i]中的元素插入到已排好序的正确位置
for (int j = i; j > 0; j--) {
// 每次后面的元素比前面的小，交换位置
if (data[j].compareTo(data[j - 1]) < 0) {
Utils.swap(data, j, j - 1);
}
}
}
}
优化
由于每次交换，相当于做了三次赋值操作，比较耗性能。如果实现保存data[i]，在每次比较的时候，只是将比它大的值向后赋值，那么就只有一次赋值操作：
public static <E extends Comparable<E>> void sort2(E[] data) {
// 第一重循环，维持循环不变量data[0 ... i)中的元素都是已排好序的
for (int i = 0; i < data.length; i++) {
// 第二重循环，将data[i]中的元素插入到已排好序的正确位置，不是合适的位置的元素，都往后挪一个索引
E t = data[i]; // 待插入元素
int j = i; // 待插入位置
for (j = i; j - 1 >= 0 && t.compareTo(data[j - 1]) < 0; j--) { // 该重循环的工作是寻找待插入的正确位置j
data[j] = data[j - 1];
}
data[j] = t;
}
}
另一种实现方式
换种思路，循环不变量为：data[0...i]是未排序的，data(i...data.length)已排序：
for (int i = data.length - 1; i >= 0; i--) {
E t = data[i];
int j;
for (j = i; j + 1 < data.length && t.compareTo(data[j + 1]) > 0; j++) {
data[j] = data[j + 1];
}
data[j] = t;
}
特性
对于插入排序来讲，内层循环的遍历是可以提前结束的，如果数组近乎有序的话，那么内层循环只需执行一次，可极大减少算法运行时间。而选择排序的内层循环，每次都需要遍历所有。
因此可以讲：在数组近乎有序的情况下，插入排序的算法复杂度接近O(n)。这是插入排序的重要特性。
算法复杂度
考虑最坏的情况的话，插入排序的时间复杂度为O(n^2)
算法测试
将插入排序的优化和未优化实现进行比较：
int[] dataSize = {10000, 100000};
for (int n : dataSize) {
Integer[] arr = ArrayGenerator.generateRandomIntArray(n, n);
Integer[] arr2 = Arrays.copyOf(arr, n);
SortTest.test("InsertionSort", arr);
SortTest.test("InsertionSort2", arr2);
}
测试结果如下：
InsertionSort: n = 10000, costTime: 0.158000S
InsertionSort2: n = 10000, costTime: 0.104000S
InsertionSort: n = 100000, costTime: 17.684000S
InsertionSort2: n = 100000, costTime: 9.944000S
可以看到，优化后的结果是要好的。
将插入排序和选择排序进行比较：
int[] dataSize = {10000, 100000};
for (int n : dataSize) {
Integer[] randomArr = ArrayGenerator.generateRandomIntArray(n, n);
Integer[] randomArr2 = Arrays.copyOf(randomArr, n);
SortTest.test("InsertionSort2", randomArr);
SortTest.test("SelectionSort", randomArr2);
Integer[] orderArr = ArrayGenerator.generateOrderIntArray(n);
Integer[] orderArr2 = Arrays.copyOf(orderArr, n);
SortTest.test("InsertionSort2", orderArr);
SortTest.test("SelectionSort", orderArr2);
}
测试结果如下：
InsertionSort2: n = 10000, costTime: 0.122000S
SelectionSort: n = 10000, costTime: 0.094000S
InsertionSort2: n = 10000, costTime: 0.001000S
SelectionSort: n = 10000, costTime: 0.088000S
InsertionSort2: n = 100000, costTime: 9.067000S
SelectionSort: n = 100000, costTime: 8.087000S
InsertionSort2: n = 100000, costTime: 0.000000S
SelectionSort: n = 100000, costTime: 7.137000S
可以看到，在数组有序的情况下，插入排序的运行速度将大幅减少。
