前言
排序皆以升序为例进行讲解
直接插入排序（插排）
生活样例 —— 我们玩扑克牌就是运用了插入排序的思想
一、图例演示
☆二、核心算法思路
从第2个开始，前面只有1个，只有1个就是有序。
把待排序的记录按其关键码值的大小逐个插入到一个 已经排好序的有序序列 中，直到所有的记录插入完为止，得到一个新的有序序列 。
三、算法思路步骤
升序降序同理
- 单趟
- end=0，指向第1个位置（1个也是有序），从第一个开始，将前面的数字都排成有序，已确保前方都是 已经排好序的有序序列
- end指向的是 序列中已经排好序 的部分的末端
- tmp先存储好 a[end+1] ( a[end+1]是要进行插入到前方有序序列的数据 ) ，避免与前面的数据进行比较后 后移，该节点的数据被覆盖。
- end其后一个数据end+1 向前比较，若 后小于前，则将前面的后移覆盖【也正是因为是 从前往后排 => 前面的数据是已经排好序的有序 => 比它大的都在后面 都往后移】同时end --，进行向前比较遍历。
- 遇到比它小的就停下，在a[end+1]的位置 将tmp赋值给a[end+1]（因为在整体中是在比较判断外面进行的 end–， 所以不管是否进行后移，都会end–，所以要+回1）
- 整体
就用 for(i=0; i<n-1(end到倒数第二个，end+1就是最后一个要进行插排的数了) ；i++) 循环，i 记录控制 end每轮单趟插排所在的 序列中已经排好序 的部分的末端。
【注意好这里有 i<n-1 的意义！！控制下标边界问题！！】
四、码源解析
- 插入排序 —— 单趟
//单趟 void InsertSort(DataType* a, int n) { int end = n - 1; DataType tmp = a[end]; while (end > 0) { if (tmp < a[end - 1]) { a[end] = a[end - 1]; end--; //是出循环的条件，别忘了 } else break; //有tmp比所有值都小的情况，则进入了if(tmp < a[end - 1])的条件没有办法出来 } a[end] = tmp; //将这个单独拎出来 }
- 插入排序 ——整体
//插入排序 —— 整体 //插入排序：是从前往后，一个一个往前对比遍历排 void InsertSort(DataType* a, int n) { for (int i = 0; i < n-1; i++) { int end = i; DataType tmp = a[end + 1]; //先将要移的数先保存起来，前面发生挪动会将其覆盖 while (end >= 0) { //错误示范while (end > 0)，那么第一个end=i=0时，进不去while循环 所以要 >= if (a[end] > tmp) { a[end+1] = a[end]; //比tmp大的都向后挪一位 } else { //遇到比tmp要小的就停下来，插入tmp break; //有tmp比所有值都小的情况，则进入了if(a[end] > tmp)的条件 没有办法走到else里将tmp赋值给a[end+1]，所以把a[end+1] = tmp;放在else里 会在tmp比所有值都小的情况下失效 } --end; //这里--了后面要+1 （--就到了空出的位置的前一个） } a[end+1] = tmp; //将这个单独拎出来 } }
注意点：
a[end+1] = tmp;单独拎出来，为了避免 tmp比所有值都小的情况，则进入了if(a[end] > tmp)的条件 没有办法走到else里将tmp赋值给a[end+1]，所以把a[end+1] = tmp;放在else里 会在tmp比所有值都小的情况下失效- 该算法的核心 操纵的是下标，而不是节点本身
- 下标边界问题：end 指向有序序列部分的末端，则end+1则是要进行向前比较插入的待排序的数据 ，数组是[0,n-1], end遍历到n-2就已经是最大了，则end+1 则是要进行向前比较插入的待排序的最后一个数据 为n-1。
五、效率分析
1. 时间复杂度
最坏：O（N^2）降序逆序
最好：O（N） 顺序有序
2. 空间复杂度
算法在执行过程中，只有 「移动」变量 时候，需要事先将变量存入临时变量x，而其它没有采用任何的额外空间，所以空间复杂度为 O ( 1 )
与冒泡排序进行对比（同样是小数据排序）：冒泡 < 插排
排前面都有序，就最后两个数字顺序颠倒
进行比较的次数
- 冒泡：n-1 [进行第一次遍历] + n-2 [第一次遍历排好后，再进行第二次遍历检查一遍，排好了结束]
- 插排：n-1 [从头开始遍历比较一遍] + 1 [多插一次]
得出结论：
时间复杂度上 O（N）一样
空间复杂度上O（1）也一样
但在细节上，局部有序，有一小段有序，插排的情况都会好很多，中间挪动次数也会少很多
