插入排序算法

3. 插入排序

3.1 概念

• 什么是插入排序（Insertion Sort）：

  将数组分为两个区域，已排序的区域和未排序的区域，默认数组第一个元素为已排序的。每一轮从未排序的区域取出第一个元素，与未排序区域的元素从后往前比较，直到找到比自己小或插入到数组索引为0的位置。

• 动画展示（此动画为网上图片，拿来借鉴一下，便于大家理解）

  

3.2 代码演示

• 初步实现插入排序

  public class InsertSort01 {
      public static void main(String[] args) {
          int[] arr = {2, 8, 4, 3, 6, 5, 7, 9, 1};
          insert(arr);
      }
  
      public static void insert(int[] arr) {
          //i代表带插入元素的索引，索引初始值为1，默认索引为0的元素是已排序好的
          for (int i = 1; i < arr.length; i++) {
              //target变量存放带插入元素的值
              int target = arr[i];
              //此时j表示已排序好的部分的最后一个元素的索引
              int j = i - 1;
              while (j >= 0) {
                  if (arr[j] > target) {
                      arr[j + 1] = arr[j];
                  } else {//当待插入元素的值大于已排序好部分某一个元素的值，则直接退出循环，减少比较次数
                      break;
                  }
                  j--;
              }
              /*
              结束while循环的两种情况
              1. j >= 0且target>arr[j]，说明target的值大于第j个值，把target的值插入arr[j]的后一位，即arr[j + 1]的位置
              2. j < 0，说明target的值比已排序好的部分中的任何一个值都小
                 将target的值插入第（-1+1=0）中，也就是arr[0]的位置
               */
              arr[j + 1] = target;
              System.out.println(Arrays.toString(arr));
          }
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32

• 输出结果

  

• 进一步解析

  1. 因为默认第一个元素是已排序的，所以整个for循环是从 i = 1 开始的

  2. 变量target的设置有两个作用：

     • 一是用来存放此次待插入元素的值
     • 二是用来与已排序的部分做比较

  3. 变量 j 的设置，由于待插入的元素是与已排序的部分做比较，且是从后往前比较，故每个待插入的元素的第一次比较都是与自己前面的元素，即第 i - 1 个元素做比较。

  4. 结束while循环（待插入元素已找到插入位置）有两种情况：

     • 一是 j >= 0 且 target>arr[ j ]，这种情况说明 target 的值大于某一个 j 的值，此时把 target 的值插入该arr[ j ]的后一位，即arr[j + 1]的位置。然后 break 退出循环，减少比较次数，提高排序效率。
     • 二是 j < 0 ，这种情况说明 target 的值比已排序好的部分中的每一个值都小，导致循环 j-- 后 j < 0，此时将target的值插入第（-1+1=0）中，也就是 arr[0] 的位置。