- 特点： 从第二个元素开始，把前面的元素序列当作已经有序的，然后找合适的位置插入。
- 优点： 插入排序是普通排序里面效率最高的排序算法，而且在数据越趋于有序的情况下，插入排序的效
率是最高的。
对于插入排序算法来说，不仅仅没有交换，而且比较的次数也少！
插入排序： 每次会把前面的一组序列当做已经排序好的，然后把后面的元素，按照有序的方式插入到前面的序列就可以了。
具体该怎么做呢？
下面这是我们原始的一组待排序的序列。
我们认为第一个元素25本身就是有序的序列，因为就一个元素25嘛。
我们从第二个元素开始处理：
第1趟： 认为25是有序的序列，然后把40按照顺序插入到其前面已经有序的序列，因为前面已经是有序的序列，所以从40就往前找，找第一个小于或者等于40的数字，插入到其后面。
现在前面有序的序列是：25,40
第2趟： 处理25这个元素，25前面是有序的序列了，然后25往前找第一个小于或者等于25的元素（维护其稳定性），插入到其后面。
25先和40比，40比25大，把40往后挪：
然后25和25比，25==25，就插入到25的后面，保持其稳定性。
第二趟处理完，前面的有序序列是：25,25,40
现在开始第3趟：
处理元素9，9前面已经是有序的序列了，9往前遍历，寻找第一个小于等于9的元素，插入到其后面
现在前面有序的序列是：9，25,25,40
现在开始第4趟： 处理元素32，往前找第一个小于等于32的元素
这一趟只比较了1个元素，就按序插到前面有序的序列中了
在数据量大的情况下，元素越有序，选择排序算法的比较次数越少，效率越高。
第5趟也是如此操作，以此类推下去，直到最后一趟处理最后一个元素为止。
最后一趟：处理31
插入排序效率高：
- 两个元素没有交换过
- 因为每一趟的待处理元素的前面序列是有序的，所以基本上，比较的次数是比较少的，基本上都一两次，两三次就有序插入OK了，除非在后面处理的数字是非常小的数字，需要比较多次。
- 所以插入排序的每一趟处理的效率是非常高的，而且处理的步骤是非常少的，很快的。
有时候甚至比较1次就可以：（针对87这个元素）
// 插入排序算法 时间复杂度: 最坏、平均 O(n^2) 最好：O(n) 空间：O(1) 稳定性：稳定的
void InsertSort(int arr[], int size)
{
for (int i = 1; i < size; i++) // O(n)，假设第0个元素是有序的，从第1个元素开始
//注意: i < size, 最后一个元素要和前面的元素进行比较，插入
{
int val = arr[i];
int j = i - 1;
for (; j >= 0; j--) // O(n)
{
if (arr[j] <= val) //这个=就决定了算法是稳定性算法
{
break;
}
arr[j + 1] = arr[j]; //将当前元素一个个向后挪
}
arr[j + 1] = val;
}
}
3、插入排序算法的性能分析
3.1、时间、空间复杂度
时间复杂度:
最坏、平均时间复杂度 O(n^2)
因为是有2个for循环，是嵌套的
最好时间复杂度：O(n)
待排序的序列已经是有序的序列了。
相当于内层循环不做任何数据移动交换，外层循环遍历1遍就完了。
稳定排序！
因为它找的是 前面有序序列中，小于等于它的数字，然后插到其后面
后面的元素是不会跑到前面和它相等的元素的前面的，只会跟在其后面。
