1.动画展示

直接插入.gif

2.思路分析

例如从小到大排序:
1. 从第二位开始遍历，
2. 当前数（第一趟是第二位数）与前面的数依次比较，如果前面的数大于当前数，则将这个数放在当前数的位置上，当前数的下标-1，**

3. 重复以上步骤，直到当前数不大于前面的某一个数为止，这时，将当前数，放到这个位置，
1-3步就是保证当前数的前面的数都是有序的，内层循环的目的就是将当前数插入到前面的有序序列里
4. 重复以上3步，直到遍历到最后一位数，并将最后一位数插入到合适的位置，插入排序结束。

思路2：
插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一一个无序表，开始时有序表中只包含-一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素， 把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

根据思路分析，每一趟的执行流程如下图所示：

3.直接插入排序 - 图2
image.png

3.复杂度分析

1. 时间复杂度：插入算法，就是保证前面的序列是有序的，只需要把当前数插入前面的某一个位置即可。
所以如果数组本来就是有序的，则数组的最好情况下时间复杂度为O（n）
如果数组恰好是倒=倒序，比如原始数组是5 4 3 2 1，想要排成从小到大，则每一趟前面的数都要往后移，一共要执行n-1 + n-2 + … + 2 + 1 = n (n-1) / 2 =** 0.5 n^s2 - 0.5 n次，去掉低次幂及系数，所以最坏情况下时间复杂度为O（n^2）
平均时间复杂度(n+n2 )/2，所以平均时间复杂度为O（n^2）
2. 空间复杂度：插入排序算法，只需要两个变量暂存当前数，以及下标，与n的大小无关，所以空间复杂度为：O（1）*

4.代码实现

最近看的
分为有序的队伍和无序的队伍
逐步扩大有序队伍，缩减无序队伍

  1. public class InsertSort {
  2.     public static void main(String[] args) {
  3.         int[] a = {5, 8, 5, 2, 6, 9,2, 3};
  4.         insert(a);
  5.         System.out.println(Arrays.toString(a));
  6.     }
  7.     public static void insert(int[] arr){
  8.         //i代表的是带插入的元素索引
  9.         for (int i = 1; i < arr.length; i++) {
  10.             int t = arr[i];//代表带插入的元素，保存索引i的值，方便空出来，和其他元素交换
  11.             int j = i-1;
  12.             while (j>=0){
  13.                 if (t<arr[j]){
  14.                     arr[j+1] = arr[j];
  15.                 }else {
  16.                     break;//前面是有序的，退出循环，减少比较次数
  17.                 }
  18.                 j--;
  19.             }
  20.             arr[j+1] =t;//j+1是空出来的位置，也就是前面t要去的位置
  21.             System.out.println(Arrays.toString(arr));
  22.         }
  23.     }
  24. }

输出结果: [5, 8, 5, 2, 6, 9, 2, 3] 红色为有序的范围,逐渐扩大,就是将无序的元素从有序队伍中找它合适的位置
[5, 5, 8, 2, 6, 9, 2, 3] 然后它后面的有序队伍逐个向后移动，腾出来的位置就给这个待插入的元素
[2, 5, 5, 8, 6, 9, 2, 3] break;的存在就是当待插入的都比有序队伍的大，则这个元素的位置就无须
[2, 5, 5, 6, 8, 9, 2, 3] 改变
[2, 5, 5, 6, 8, 9, 2, 3]
[2, 2, 5, 5, 6, 8, 9, 3]
[2, 2, 3, 5, 5, 6, 8, 9]
[2, 2, 3, 5, 5, 6, 8, 9]

  1. public class InsertSort {
  2.     public static void main(String[] args) {
  5.         int arr[] = {10, 7, 9, 3, 2};
  6.         System.out.println(Arrays.toString(arr));
  7. //        System.out.println("排序前："+Arrays.toString(arr));
  8.         insert(arr);
  9. //        System.out.println("排序前："+Arrays.toString(arr));
  10.     }
  12.     private static void insert(int[] arr) {
  15.         int insertVal = 0;
  16.         int insertIndex = 0;
  17.         for (int i = 1; i < arr.length; i++) {
  19.             //等待插入的值
  20.             insertVal = arr[i];
  21.             insertIndex = i-1;//即arr[1]的前面的这个数的下标
  23.             while(insertIndex >= 0 && insertVal < arr[insertIndex]){ //>则是从大到小
  24.                 arr[insertIndex +1] =arr[insertIndex]; //将原先等待插入的那个值先替换成要插入的位置的值  {101, 34, 119, 1}; => {101,101,119,1}
  25.                 insertIndex--;//退出循环
  26.             }
  27.             // 当退出while循环时，说明插入的位置找到, insertIndex + 1
  28.             // 举例：理解不了，我们一会 debug
  29.             //这里我们判断是都需要赋值
  30.             if (insertIndex+1 != i) {
  31.                 arr[insertIndex + 1] = insertVal; //{101, 34, 119, 1};  => {34, 101, 119, 1}
  32.             }
  33.             System.out.println("第"+i+"轮插入");
  34.             System.out.println(Arrays.toString(arr));
  35.         }
  36.     }
  37. }

逐步推导

  1.    //使用逐步推导的方式来讲解，便利理解
  2.         //第1轮 {101, 34, 119, 1};  => {34, 101, 119, 1}
  4.         //{101, 34, 119, 1}; => {101,101,119,1}
  5.         //定义待插入的数
  6.         int insertVal = arr[1];
  7.         int insertIndex = 1-1;//即arr[1]的前面的这个数的下标
  9.         //给insertVal找到插入的位置
  10.         //说明
  11.         //1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
  12.         //2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
  13.         //3. 就需要将 arr[insertIndex] 后移
  14.        while(insertIndex >= 0 && insertVal < arr[insertIndex]){
  15.            arr[insertIndex +1] =arr[insertIndex];
  16.            insertIndex--;//退出循环
  17.        }
  18.        arr[insertIndex+1] =insertVal;
  19.         System.out.println("第"+1+"轮插入");
  20.         System.out.println(Arrays.toString(arr));
  22.         //第2轮
  23.          insertVal = arr[2];
  24.          insertIndex = 2-1;//即arr[1]的前面的这个数的下标
  26.         while(insertIndex >= 0 && insertVal < arr[insertIndex]){
  27.             arr[insertIndex +1] =arr[insertIndex];
  28.             insertIndex--;//退出循环
  29.         }
  30.         arr[insertIndex+1] =insertVal;
  31.         System.out.println("第"+2+"轮插入");
  32.         System.out.println(Arrays.toString(arr));
  34.         //第三轮
  36.         insertVal = arr[3];
  37.         insertIndex = 3-1;//即arr[1]的前面的这个数的下标
  39.         while(insertIndex >= 0 && insertVal < arr[insertIndex]){
  40.             arr[insertIndex +1] =arr[insertIndex];
  41.             insertIndex--;//退出循环
  42.         }
  43.         arr[insertIndex+1] =insertVal;
  44.         System.out.println("第"+3+"轮插入");
  45.         System.out.println(Arrays.toString(arr));
  47.         //第4轮
  49.         insertVal = arr[4];
  50.         insertIndex = 4-1;//即arr[1]的前面的这个数的下标
  52.         while(insertIndex >= 0 && insertVal < arr[insertIndex]){
  53.             arr[insertIndex +1] =arr[insertIndex];
  54.             insertIndex--;//退出循环
  55.         }
  56.         arr[insertIndex+1] =insertVal;
  57.         System.out.println("第"+4+"轮插入");
  58.         System.out.println(Arrays.toString(arr));
  60. */

运行截图
image.png