插入排序
将一个元素插入到已经有序的数组中的适当位置，使新的数组还是有序。插入排序中，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定（选择排序已确定）。为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达素组的右端时，数组排序就完成了。
插入排序动态图
插入排序
Java代码实现
public class Insertion extends Sort {
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 1; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
public static void main(String[] args) {
String[] a = {"1", "3", "2", "9", "4", "8"};
sort(a);
assert isSorted(a);
show(a); // 1 2 3 4 8 9
}
}
算法分析
对于随机排列的长度为N且主键不重复的素组，平均情况下插入排序需要
~N^2/4次比较以及~N^2/4次交换。最坏情况下需要~N^2/2次比较以及~N^2/2次交换，最好情况需要N-1次比较和0次交换。
最坏情况
最坏情况是指倒序的情况。此时从索引1开始，每一次都需要把当前元素移动到最左端。
比较次数：1 + 2 + 3 + ... + N -1 ~ N^2/2
交换次数：1 + 2 + 3 + ... + N -1 ~ N^2/2
最好情况
最好情况是指数组已经排好序的情况。
比较次数：1 + 1 + 1 ... = N -1（外循环次数）
交换次数：0（当前位置就是正确位置，不需要交换）
倒置
倒置是指数组中的两个顺序颠倒的元素。比如 3 2 1中有对倒置：3-2、3-1、2-1。
插入排序与倒置的关系
插入排序需要交换的次数与数组中倒置的数量相同，需要比较的次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小减一。
插入排序中每一次交换都改变了两个顺序颠倒的元素的位置，相当于减少了一对倒置。当倒置数量为0时排序就完成了。每次交换都对应着一次比较（3 1 2，倒置：2对，比较次数：3，大于2。），且1到N-1之间的每个i都可能需要一次额外的比较。
