原始数组：a=[8,6,2,3,7,9,1]； 要求升序。
step1：因为8是第一个，所以8固定不动，让6和8比，因为6小于8，所以，6和8交换位子，数组变为6,8,2,3,7,9,1。这1轮比较完毕。
step2：将2与它的前一个，也就是8比，因为2小于8，所以2和8交换位子，数组变为6,2,8,3,7,9,1。
再将2与6比，比完之后2与6交换位子，数组变为2,6,8,3,7,9,1。这一轮比较完毕。
step3：将3与8比，所以3与8交换位子，数组变为2,6,3,8,7,9,1。
将3与6比，所以3和6交换位子，得到2,3,6,8,7,9,1。
将3与2比，因为3不比2小，所以位子不变，跳出循环，跳出这一轮比较。
step4：以此类推……
代码为
1 for（int i=1;i<n;i++） { //外层循环 ,整个过程其实就是在为a[i]寻找合适的插入位子 2 for(int j=i,j>0;j--) { //内层循环，因为是倒回去比较，所以是减减 3 if(a[i]<a[j]) 4 swap(a[i],a[j]); //swap函数的作用就是交换位子 5 else break 6 } 7 }
如果想把代码的行数写少点，可以把上述代码修改一下，
1 for（int i=1;i<n;i++） { //外层循环 ,整个过程其实就是在为a[i]寻找合适的插入位子 2 for(int j=i,j>0&&a[i]<a[j];j--) { //内层循环，因为是倒回去比较，所以是减减 3 swap(a[i],a[j]); //swap函数的作用就是交换位子 4 } 5 }
由第一处代码可以看出，插入排序是可以提前结束第二层循环的。
上述两处的代码，运用的swap这个交换位子的函数，太耗时间了，所以下面进行改进，
1 for(int i=1,i<n,i++){ //整体思路就是寻找a[i]的适合的插入位子 2 int e=a[i]; 3 int j; //j用于保存元素e应该插入的位子 4 for(j=i,j>0&&a[j-1]>e,j--){ 5 a[j]=a[j-1]; 6 } 7 a[j]=e; 8 }
由此可见，改进思路就是把1次又1次的赋值，变成了“比较后，只做1次赋值”。
而原本使用的swap函数里，使用1次swap就是1次交换，而1次交换，就是3次赋值（高中讲过）。
原文：https://www.cnblogs.com/zf007/p/11487698.html