将第一待排序序列第一个元素看做一个有序序列,
把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
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; // 找到位置再之后插入当前数据
}
}