十大排序（C++）-- 插入排序（InsertSort）

        前两种算法原理和实现都相对简单，而到了插入排序开始，就会有一点小小的绕。（我当初也晕了(¦3」∠)）插入排序的原理不难，每次选择一个数插入到前面他应该在的位置上。原理很简单hhh但是实现有点小绕。我们同样的一组测试用例：[5,3,8,6,9,2,1,4,7]，利用Excel表格能更好的看到效果。

我们举个栗子，在第一遍遍历时的设置初始下标i=1，j=i-1,nums[i]此时值为3，j=0，那么此时nums[j]的值比nums[i]大，因此，nums[i]应该插入到nums[j]的前面！说明有序时nums[i]的位置应该在更前面，所以我们先把nums[i]记录下来，把j往后面挪，令nums[j+1]=nums[j]，而j继续向前，直到遍历到开头或者遇到nums[i]比nums[j]大的时候，这时的位置就是nums[i]该插入的位置了。

我们来看一下实现的代码：

打印一下每遍运行的结果看一下。

由每次的循环我们可以看到，每一次遍历都会多出一个数插入到前面他应到的位置上。

时间复杂度：O(n^2)，空间复杂度：O(1)

优点：在最好的情况下时间复杂度为O(n)，与冒泡排序一样。但是在处理大量数据时，还记不记得我们是怎么处理冒泡排序中的值的？没错，交换！而一次交换需要耗费3条语句，插入排序只需要一次赋值即可。因此在同样的情况下，插入排序的处理时间会优于冒泡排序。
缺点：同样的，在最差的条件下（比如我们要求正序但用例是完全倒序），时间复杂度为O(n^2)。