插入排序的类比扑克牌的讲解：
插入排序就像是我们打扑克牌一样从小到大排序，在打斗地主的时候，我们每次抽取一张牌，然后把这一张牌放入我们已经排好顺序的牌组中。（这种场景就是我们每次抽牌都是按照从小到大的顺序去排顺序，然后后面抽取到的牌也是按照从小到大的顺序来插入到原有的牌组中）这样的排序思想就是我们初步的插入排序。
所以我们插入排序就是想象出我们拥有一组扑克牌，然后我们将前end个看成有序的，然后看看新来的这张牌是比end大还是小，如果比end小，那么它的位置应该在end前面，这时候就把end往后挪动一下（覆盖掉end+1的位置，每次这样做就都可以保证end的位置是空的，当新牌需要插入end的位置的时候保证原有的数据不会丢失）。可以想象一个场景，我们手里面有1，2，3，4，5，7。这一组牌
这时候我们在扑克牌牌堆里面新抽出来一张6，这时候这张6，它的位置应该在5的后面和7的前面，所以我们一开始拿6和最后一张7来比较，发现6比7小，然后让7把位置让出来，往后走
就像这样（然后在7的前面就会有多出来一个空间，所以新来的6就有空间去插入了）。然后6还会继续和5去比较，如果比5大就放到5的后面，直接覆盖在原数组中，上面的操作已经让7往后挪动一个位置了，所以在原数组中end和end+1位置的元素都会是7，所以end的位置就是一个空的位置，这时候我们的6就可以插入end的位置。
插入排序的代码讲解：
如果用代码来解释：end就是我们手里面的扑克牌最后的一个位置的变量，然后先保存一下end+1位置的值到tmp里面，这时候end+1位置就可以看作是空的，然后tmp就是我们新拿到的值，判断这个值是不是小于end位置的值，如果小于end位置的值，就说明tmp（新拿到的牌）的位置应该在end的前面，此时让end+1位置来存放这个end位置的值，此时end就是空的，然后再让end–，这时候就是比较end（原来的倒数第二个，倒数第一个就是我们新拿到的牌）位置的值了，然后一直循环，知道退出循环，然后end+1的位置肯定是空的，然后我们拿到的新的牌就放到end+1的位置。
这种代码刚好可以处理我们手里面有2，3，4，5，6这么多牌，然后我们end+1（新拿到的）是一个1，这时候我们需要把这张扑克牌放到第一个位置，如果我们直接在循环里面来处理这种情况的话？
下面的代码在循环里面处理不来这种情况（就是把交换函数放到循环里面），因为循环出来的条件就是end >= 0；当end == 0，就拿上面的（2，3，4，5 1）来判断然后end还会进入循环，a[0]的值是2，也比tmp（1）的值要大，所以end会进入end–那个程序然后end == -1；然后出循环。所以在循环里面交换的话，我们这种情况会遗漏，所以我们把交换函数放到了循环的外面，循环就是去找新来的牌应该放入到的位置，然后我们直接把新来的牌直接放入到它该有的位置上去。这样就不用再在循环里面去判断应该放入到最开头的位置的情况了。
//直接插入排序
void InsertSort1(int* a, int n)
{
assert(a);
for (int i = 0; i < n – 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end–;
}
else
break;
}
a[end + 1] = tmp;
}
}
