数据结构与算法（1）插入排序

插入排序，字面意思可以理解为：利用插入元素的手法将乱的数组按顺序排序。插入的手法指的是在一个已经排序好的元素中插入元素，多次重复插入达到排序的效果。

简单的总结为：在不打乱排序好的数组中，循环插入到排序好的数组中。

比如：现在有数组[2,3,4,5,3,4,1]需要从小到大进行排序,在数组中[2,3,4,5]是已经排好序的元素。在不打乱顺序的情况下，将第5个元素3插入排序好的元素中。多次重复操作将整个数组排序完成。

如何执行插入的操作呢？

我们可以想象成，3把位置空出来，在排序好的元素[2,3,4,5]中找到进行比较，找到位置，将比3大的都往后挪一个位置。

image-20201027204401705.png

以此类推，重复插入步骤，实现排序。

如何用代码实现呢？

人思考的时候和代码会有一定差别。比如，把3的位置空出来，挪动位置，大脑可以记住位置上原来是3，电脑却记不住，挪动位置后3就会被覆盖掉。因此我们需要将3赋值给一个变量保证3不会被覆盖掉。

public static void main(String[] args) {

        int[] arrNum = {2, 3, 4, 5, 3};


        /*
         * 步骤1：空出位置
         * */

//    将3赋值给一个变量，保证挪动位置不会被覆盖掉，
        int currentNum = arrNum[4];


        /*
         * 步骤 2：进行比较，查找位置
         *
         * */

//    排序好的最大下标为3
        int i = 3;
//    从后往前遍历排序好的数组
//    当第一次遇到比3小的时候，3的位置就在这个位置的后一个。如果第i个元素大于currentNum继续执行循环
        while (i >= 0 && arrNum[i] > currentNum) {

            i--;
        }
        System.out.println("3的需要放的位置是" + (i + 1));

        /*
         *  步骤3：挪动位置
         *     将3需要放置的位置到排序好的最后一个位置进行往后挪一个位置,
         *     由于从前往后，会覆盖掉后面的数，需要在定义一个变量，才能实现，
         *     而3的位置空出，因此采用从后往前挪的方式进行挪动。
         * */

        for (int j = 3; j >= i + 1; j--) {
            arrNum[j + 1] = arrNum[j];
        }
//    将空出的位置用-1代替方便观察
        arrNum[i + 1] = -1;
        System.out.print("挪动位置：");
        for (int item : arrNum) {
            System.out.print(item + ",");
        }
        System.out.println();

//    将3放入位置
        arrNum[i + 1] = currentNum;
        System.out.print("放入：");
        for (int item : arrNum) {
            System.out.print(item + ",");
        }


    }

运行效果如下：

image-20201028090050794.png

我们可以将代码中的几个定量修改为变量，就可以实现n个元素数组的一次排序，但数组是有条件的：数组需要满足前n-1个元素是从小到大排序的。

public static void main(String[] args) {

      int[] arrNum = {2, 3, 4, 5, 3};
      sort(arrNum);
      int[] arrNum2 = {6, 7, 8, 8, 11, 20, 4};
      sort(arrNum2);

   }

   private static void sort(int[] arrNum) {


      /*
       * 步骤1：空出位置
       * */

//    将3赋值给一个变量，保证挪动位置不会被覆盖掉，
//    ！！！！！改动
      int currentNum = arrNum[arrNum.length - 1];

      /*
       * 步骤 2：进行比较，查找位置
       *
       * */

//    排序好的最大下标为3
      //    ！！！！改动
      int i = arrNum.length - 2;
//    从后往前遍历排序好的数组
      while (i >= 0 && arrNum[i] > currentNum) {
//       当第一次遇到比3小的时候，3的位置就在这个位置的后一个。

         i--;
      }
//    ！！！！！改动
      System.out.println(currentNum+ "的需要放的位置是" + (i + 1));

      /*
       *  步骤3：挪动位置
       *     将3需要放置的位置到排序好的最后一个位置进行往后挪一个位置,
       *     由于从前往后，会覆盖掉后面的数，需要在定义一个变量，才能实现，
       *     而3的位置空出，因此采用从后往前挪的方式进行挪动。
       * */

//    改动
      for (int j = arrNum.length - 2; j >= i + 1; j--) {
         arrNum[j + 1] = arrNum[j];
      }
//    将空出的位置用-1代替方便观察
      arrNum[i + 1] = -1;
      System.out.print("挪动位置：");
      for (int item : arrNum) {
         System.out.print(item + ",");
      }
      System.out.println();

//    将3放入位置
      arrNum[i + 1] = currentNum;
      System.out.print("放入：");
      for (int item : arrNum) {
         System.out.print(item + ",");
      }
      System.out.println();
   }

效果如下图：

image-20201028091345570.png

由小推大：我们把一个乱序的数组拆解多次重复上述操作。那么数组的条件怎么满足呢。我们可以先把第一个元素看成是一个有序的数组，因为只有一个元素所以无论如何都是有序的，这样就从前两个开始进行上述操作直至最后一个。这样就排好序了。

public static void main(String[] args) {

      int[] arrNum = {2, 3, 4, 5, 3,2,47,5,753,3};
      sort(arrNum);
      int[] arrNum2 = {6, 7, 8, 8, 11, 20, 4};
//    sort(arrNum2);

   }

   private static void sort(int[] arrNum) {


      for (int n = 1; n < arrNum.length; n++) {
         /*
          * 步骤1：空出位置
          * */

//    将3赋值给一个变量，保证挪动位置不会被覆盖掉，
//    改动
         int currentNum = arrNum[n];

         /*
          * 步骤 2：进行比较，查找位置
          *
          * */

//    排序好的最大下标为3
         //    改动
         int i = n-1;
//    从后往前遍历排序好的数组
         while (i >= 0 && arrNum[i] > currentNum) {
//       当第一次遇到比3小的时候，3的位置就在这个位置的后一个。

            i--;
         }
//    改动
         System.out.println(currentNum + "的需要放的位置是" + (i + 1));

         /*
          *  步骤3：挪动位置
          *     将3需要放置的位置到排序好的最后一个位置进行往后挪一个位置,
          *     由于从前往后，会覆盖掉后面的数，需要在定义一个变量，才能实现，
          *     而3的位置空出，因此采用从后往前挪的方式进行挪动。
          * */

//    改动
         for (int j = n-1; j >= i + 1; j--) {
            arrNum[j + 1] = arrNum[j];
         }
//    将空出的位置用-1代替方便观察
         arrNum[i + 1] = -1;
         System.out.print("挪动位置：");
         for (int item : arrNum) {
            System.out.print(item + ",");
         }
         System.out.println();

//    将3放入位置
         arrNum[i + 1] = currentNum;
         System.out.print("放入：");
         for (int item : arrNum) {
            System.out.print(item + ",");
         }
         System.out.println();
      }


   }

运行效果如下：

image-20201028093640570.png

优化

现在效果已经实现了，但是代码可以繁琐，我们可以进行优化。我们在进行找位置后进行挪位置。那么我们在找位置的时候，可以 一边找位置一遍进行挪位置吗？答案是可以的，我们可以在找位置的时候，当前元素和排序好的数组元素进行比较时，如果当前的元素比较小那我们是不是可以把他们的位置进行互换挪位置，这样当我们找到位置时，比当前元素大的元素都已近在找位置比较时进行过位置的移动了。后面的挪动位置和放入元素我们就合并在一起操作了。

image-20201028094754191.png

代码如下：

    public static void main(String[] args) {

      int[] arrNum = {2, 3, 4, 5, 3, 2, 47, 5, 753, 3};
      sort2(arrNum);
      int[] arrNum2 = {6, 7, 8, 8, 11, 20, 4};
//    sort(arrNum2);

   }

   

   private static void sort2(int[] arrNum) {
      for (int i = 0; i < arrNum.length; i++) {
//       1.空出位置
         int currentNum = arrNum[i];
//       2.找位置的同时进行互换挪位置
         int j = i - 1;
         while (j >= 0 && arrNum[j] > currentNum) {
//          互换挪位置
            arrNum[j + 1] = arrNum[j];
            j--;
         }
//       放入
         arrNum[j + 1] = currentNum;
      }

      for (int i : arrNum) {
         System.out.print(i + ",");
      }
   }

image-20201028095507632.png

举一反三

对于排序我们不仅需要会从小到大，我们还可以从大到小、通过找出中间数，以中间数为中心，一边从大到小，一边从小到大等等一系列排序。