本
文
摘
要
插入排序
概述
插入排序是使用相对位置的方式进行排序的。也是一个比较常见的排序。
排序过程
插入排序的过程可以理解为我们玩扑克的时候对扑克进行排序的过程。每抽上来一张牌，就找到已知有序的牌中小于这个张牌的最大值，和大于这张牌的最小值，然后插入到这两张牌的中间。对于每张牌都这样操作，最后的结果就是有序的。
因为其操作过程就是插入两张相对位置的牌的中间因此称为插入排序。
例如：已知 5，7，10，13 新来了一个数 9，那只要找到比他小的最大值 7在哪个位置，或者找到比他大的最小值10在那个位置即可确定 9 的位置.
插入 9这时候再来一个数 8
插入 8对插入排序有了一个宏观的认识现在要来具体想一下这个步骤在代码上如何实现了。
可以假设第一个数已经是确定排好序的，因为一个数是没有顺序的，因此从第二个数开始遍历遍历 n-1 次
每次遍历：
与已知序列的数进行比较，可以从小到大也可以从大到小 如果是从小到大的话就是找到第一个比他大的数前面插入 如果是从大到小就是找到第一个比他小的数后面插入 后面的数向后移动一位例如：
对比找到适当的位置
寻找位置插入，后移
插入&后移结合以下动图理解一下：
插入排序代码实现（Java）
第一种实现方式：从头往后查找，查找到第一个比他大的数
static void insertionsort(int[] arr){ int n = arr.length; for(int i = 1; i < n; i++){ // 存储要插入的数，不然等会移动的时候会覆盖掉 int u = arr[i]; // 从小到大遍历 for(int j = 0; j < i; j++){ // 如果找到第一个比 u 大的值 if(arr[j] > u){ // 后面的数全部向后移动一位 for(int k = i-1; k >= j;k--){ arr[k+1] = arr[k]; } // 赋值，break arr[j] = u; break; } } } }第二种实现方式：从后往前查找，查找到第一个比他小的数
static void insertionsort2(int[] arr){ int n = arr.length; for(int i = 1; i < n; i++){ // 存储要插入的数 int u = arr[i]; // 从后往前遍历 int j = i-1; while(j >= 0 && arr[j] > u){ arr[j+1] = arr[j]; j--; } arr[j+1] = u; } }复杂度分析
时间复杂度分析
第一种解法是一定的 O(n2)的时间复杂度，并且遍历的次数也是 n2 的，因为里层循环，前一半是判断，后一半是移动，因此里层循环巡行的次数也是 n次因此为 n2次
1+2+3+...+n-1 = (n * n + n)/2
因此时间复杂度为 O(n2)
第二种解法也是 O(n2)的时间复杂度，但是不是满 n2 次的，因为其是从后往前找，因此判断和移动一起做，因此遍历的次数不会满 n2，除非是特殊序列，就是倒序序列进行排序才会跟上面的时间复杂度一样。
因此第二种解法的最坏时间复杂度为 O(n2)最好的时间复杂度是发生在原本就有序的情况，其时间复杂度是 O(n)的
因此总结一下使用插入排序的时间复杂度最坏情况是 O(n2)最好是 O(n)
空间复杂度分析
只使用了几个变量保存值，使用了常数级的变量因此使用的空间的复杂度是 O(1)的
稳定性分析
插入排序是稳定的。
在上面已经提到了这个插入排序是按照相对位置进行插入的，因此每次插入的时候如果判断到有相同的数，将当前的数放在相同数的后一个位置就保证了其稳定性。
因为前面那个数在原本的序列中是在当前数的前面，因此先 *** 入进来，如果要保证他们的稳定性就要保证前面的数依旧排在前面。
因此当判断条件为：while(j >= 0 && arr[j] > u) 时是稳定的，
但是如果判断条件为while(j >= 0 && arr[j] ≥ u)时是不稳定的。
因为插入排序可以达到稳定，因此称插入排序是稳定的。
