插入排序

将第一待排序序列第一个元素看做一个有序序列，
把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

https://www.runoob.com/w3cnote/insertion-sort.html

// 插入排序，a表示数组，n表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int current = a[i];
    int preIndex = i - 1;
    // 查找插入的位置
    for (; preIndex >= 0; --preIndex) {
      if (a[preIndex] > current) {
        a[preIndex+1] = a[preIndex];  // 数据向后移动，继续比较前一个
      } else {
        break;
      }
    }
    a[preIndex+1] = current; // 找到位置再之后插入当前数据
  }
}