用图说话
插入排序图解
放码过来C++
// 插入排序
void insertionSort(vector<int> array)
{
/*
算法思想：根据插入排序的思想，将数组分成两个部分，一个是有序一个是待插入，
然后拿待插入的每一个元素去跟有序数组的每一个元素比较
ok，这里就有大概的思路了，拿待插入的每一个元素，那我这里得用一个循环来遍历
跟有序数组的每一个元素比较，这里还得一个循环来遍历有序数组
那么我脑海中大概的代码就是酱紫了
for(待插入的数组) {
for(有序数组) {
处理待插入和有序数组的比较的
}
}
ok，有了这个思路后，我们就开始一步一步撸，慢慢调了
*/
// *** 开始撸,对着我做的图来看比较容易理解哦！ ***/
// 遍历待插入数组；
// 之所以i从1开始，是因为默认数组的第一个元素的有序的
for (int i=1; i<array.size(); i++) {
// 取待插入数组的第一个元素
// i表示待插入数组的第一个元素下标
// kmp表示待插入数组的第一个元素
int kmp = array[i];
// i-1 就是有序数组的最后一个元素
int j = i-1; // 为什么要设置这个j呢，因为下面有while() 要把这个j作为循环的终止条件
// 当待插入元素kmp小于有序数组的最后一个元素时，这个有序数组的最后一个元素后移
// kmp即将要插入的值
// 为什么j>=0 因为比如9 3 4 2其中9 3 4 是有序数组，2是即将要插入的值，那么这时候2跟9比较
// 也就是kmp = 2 Array[j] == 9，则j == 0；所以j == 0是要进入循环的，所以j>=0
// 这个while循环的作用就是拿待插入值跟有序数组元素一一比较，然后大于就让有序数组的元素后移，最后将要插入值的位置空出来
while (j>=0 && kmp<array[j]) {
// 后序数组元素后移
array[j+1] = array[j];
j--;
}
// 当比较完之后，将这个即将插入的值kmp，插入到指定的数组位置中
array[j+1] = kmp;
// 为什么是j+1 举个例子
// 比如9 3 4 2其中9 3 4 是有序数组，2是即将要插入的值，那么这时候2跟9比较
// 也就是(kmp == 2) < (array[j==0] == 9) 那么满足条件，进入循环，进入之后，9后移，j--，这时候j--后就等于-1了
// 所以我这个即将要插入的值kmp，应该插入下标为0的位置，但是这时候的j==-1，所以array[j+1] = kmp
}
}
