三.插入排序介绍
插入排序的基本思路是每次插入一个元素，每一趟完成对一个待排元素的放置，直到全部插入完成。
直接插入排序
直接插入排序是一种最简单的排序方法，过程就是将每个待排元素逐个插入到已经排好的有序序列中。
折半插入排序
由于在插入排序的过程中，已经生成了一个（排好的元素组成的）有序数列。所以在插入待排元素时可以使用折半查找的方式更快速的确定新元素的位置，当元素个数较多时，折半插入排序优于直接插入排序。
希尔排序
希尔排序可以看做是分组插入的排序方法，把全部元素分成几组（等距元素分到一组），在每一组内进行直接插入排序。然后继续减少间距，形成新的分组，进行排序，直到间距为1时停止。
四. 直接插入排序
输入
n个数的序列，通常直接存放在数组中，可能是任何顺序。
输出
输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序排列）。
算法说明
每次从原有数据中取出一个数，插入到之前已经排好的序列中，直到所有的数全部取完，那么新的有序排列也就完成了。
通俗一点的解释就是好比我们在打扑克抓牌，所有的牌扣在桌面上，我们一张一张的抓，抓起一张就在手里把它排好。那么等我们把所有的牌都抓起来之后，手里的牌也都是有序的了。
算法流程
对于计算机来说，我们必须要详细的告诉它如何比较大小，以及如何确定位置，毕竟它不能像我们一样，“一眼”就看出位置。试想一下，当数据量比较多的时候，我们也是需要一个一个的看过来，然后才能确定新插入元素的位置。
第一个元素：放在第一个位置，直接排好
第二个元素：与第一个元素比较，如果更大，放在第二个位置，如果更小，放在第一个位置
第三个元素：顺次从后向前比较，如果更小，将已排好元素向后串位，最后插入第三个元素
剩余其他元素：顺次从后向前比较，如果更小，将已排好元素向后串位，直到找到合适的位置插入
如果待排元素是已排好的元素中最大的，只需要比较一次，然后直接追加到已排好的序列后面
四. 伪代码
直接插入排序是一个比较好理解的算法，大家直接用抓牌就可以完美刻画：每次摸起一张牌，从右至左（从大到小）的与手中的牌比较，如果摸起来的这张是手牌里最大的，就直接放在最右边，如果不是最大的，就顺次滑过比它大的牌（相当于串位），直到遇见一个比刚摸起这张牌小的手牌，插入到这张牌的后面。
按照这样的步骤重复操作，当所有的牌都被抓完时，手里的牌就都是有序的了，理解了算法的思路后，我们用伪代码来进行表示：
for j = 2 to A.length key = A[j] i = j - 1 while i > 0 and A[i] > key A[i + 1] = A[i] i = i - 1 A[i + 1] = key
初始计数器为2，代表第一个元素默认排好，从第二个元素开始操作，直到最后一个元素。
每次用key记录新操作的元素，i的初始值代表当前操作元素的前一个元素，也就是第一个要与之比较的元素。
while循环为内层循环，作用是在已排好的元素中找到合适的位置，来将key插入。
如果进入到循环体中执行，代表key相对较小，还要再向前寻找，同时，与之比对的元素要向后串位，因为此时可以确定，key一定在这个元素的前面，在进入下一次循环时，使用再前面一位的元素进行比对。
for循环的最后一行是将key插入到对应的位置，外层循环结束（每次循环插入一个数）。
五：算法实践
1. 算法实现
输入数据（input）：11，34，20，10，12，35，41，32，43，14
Java源代码
需要注意源代码与伪代码的区别，请查看文章开头补充的概念部分，这里不做过多说明。
public class DirectInsert { public static void main(String[] args) { // input data int[] a = {11,34,20,10,12,35,41,32,43,14}; // 数组下标从0开始，j初始为1，指向第二个元素 for (int j = 1;j < a.length;j++){ // 使用key记录当前元素的值 int key = a[j]; // 初始化i，为j的前一个元素 int i = j - 1; // while循环作用：在已经排好的有序数列中确定key的位置，并串出对应的位置 while(i >= 0 && a[i] > key){ // 串位覆盖，不需要使用交换，值已经被记录在key中 a[i + 1] = a[i]; // 逐渐前移 i = i - 1; } // 将待排元素放在对应的位置 a[i + 1] = key; } // 查看排序结果 for (int data : a){ System.out.print(data + "\t"); } } }
执行结果：
输出数据（output）：10，11，12，14，20，32，34，35，41，43
2. 时间复杂度
最坏的情况
最坏的情况就是指每一行代码都被执行了，循环也是被完全拉满的情况，一次都没有少，确实很充实很悲催了。
对于直接插入排序来说，如果输入的元素刚好是反向有序的，那么每次取出一个元素，都要和已经排好的每一个元素进行比较，直到比较到第一个元素，然后把自己放在最前面，没办法，每次拿到的都是比之前小的元素，好气哦。
在这种情况下，内层while循环中的代码一共执行了 ∑ i = 1 n − 1 i = n ( n − 1 ) 2 = O ( n 2 ) \sum_{i=1}^{n-1} i=\frac{n(n-1)}{2}=O\left(n^{2}\right) ∑i=1n−1i=2n(n−1)=O(n2)，其中n为输入的数据个数。
在计算时间复杂度时，我们只关心最后的量级就好，比如for循环中代码以及while循环中的代码都有多行，最后的结果一定比 n 2 n^{2} n2大，但都是属于O( n 2 n^{2} n2) 。
最好的情况
最好的情况就是指能不被执行的步骤都没有被执行，来的数据刚刚好，并且每个数据都是这样，简直就是天选之人。
对于直接插入排序来说，如果输入的元素已经是正向有序的，那么每次取出一个元素，在和已经排好的序列中的最后一个元素比较之后，就可以直接放到后面，循环都不用进，因为已经找到了它应该在的位置。
在这种情况下，内层的while循环可以只看成一个判断语句了，嗯，就是这样。所以代码执行的次数主要看外层for循环就好了，一共是n-1次，属于O(n) 。
平均情况
综合两种情况，插入排序的时间复杂度为O( n 2 n^{2} n2) 。
3. 空间复杂度
除计数器以外，算法执行过程中需要使用临时变量key来记录一下当前元素的值，除此之外的其他操作都可以在原数据结构（数组）上完成，所以空间复杂度为O(1) 。
部分文章来自；1,2,3
