简介

根据元素序列最左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到左侧已排序元素的右边。

  • 特点：
    • 默认第一个元素为已排序好的值。会从第二个元素值进行排序操作。
    • 右侧元素会一直和前一个元素进行比较，如果小于则互换位置，如果大于则保持不变。

图解

同样对1-5进行排序

image.png
首先假设最左边的5已经排序完成，所以此时只有5号元素为已归位的状态。第一轮排序完毕

  • 第二轮比较是从未排序元素中取出最靠左边的元素值3号**，然后与左侧已归位的元素5**进行比较，如果比它小则交换位置，直到没有比它更小的值，否则继续进行下一个元素值的比较。

image.png

  • 因为5 > 3，算法按正序排序，则交换这两个数的位置。至此第二轮的操作完成。
  • 接下来是第三轮的比较，取出右边未排序的4号元素，它将与左边的5进行比较。

image.png
由于4 < 5，所以交换两个值的位置，再与左边的3进行比较，4 > 3则不作任何操作。

  • 接下来进入第四轮的比较，只剩下右边的1和2元素等待排序中，首先看1号元素。

image.png

从图中可以看出，首先从待排序区中1这个数值依次与左边进行比较，1 < 5, 1 < 4, 1 < 3，直到左边没有比1更大的元素位置，所以1元素被排到了最左侧。

  • 最后一轮比较只剩一个2元素，如上图所示，依次和左边已排序好的元素进行比较，如果小于则互换位置。

image.png

  • 至此所有元素已经排序完毕。

代码实现（Java）

  • 正序排序
  1. package sort.example.insert;
  3. import java.util.Arrays;
  5. public class PracticeInsertion {
  7.     public static void main(String[] args) {
  9.         int[] arrays = { 5,3,4,7,2,8,6,9,1 };
  10.         int count; // 临时变量 count
  11.         for (int i = 1; i < arrays.length; i++) { //从第一个元素开始遍历排序
  13.             if (arrays[i] < arrays[i - 1]) { // 当arrays[i]小于arrays[i-1] 也就是后一位元素小于前一位元素时再执行下面的操作。
  14.                 count = arrays[i]; // 存储arrays[i]的值
  15.                 int j = i; // 将i交给变量j，从当前位置开始处理。
  16.                 while (j > 0 && count < arrays[j -1]) { // 如果j大于0，count小于前一位的元素则进行下面的操作。
  17.                     arrays[j] = arrays[j -1]; // 将前一位元素的值和后一位元素的值互换。
  18.                     j--; // 继续向前比较。
  19.                 }
  20.                 arrays[j] = count;
  21.             }
  22.         }
  23.         System.out.println(Arrays.toString(arrays));
  24.     }
  25. }
  • 倒序排序
  1. package sort.example.insert;
  3. import java.util.Arrays;
  5. public class PracticeInsertion {
  7.     public static void main(String[] args) {
  9.         int[] arrays = { 5,3,4,7,2,8,6,9,1 };
  10.         int count;
  11.         for (int i = 1; i < arrays.length; i++) { //从第一个元素开始遍历排序
  13.             if (arrays[i] > arrays[i - 1]) { // 当arrays[i]大于arrays[i-1] 也就是后一位元素大于前一位元素时再执行下面的操作。
  14.                 count = arrays[i]; // 存储arrays[i]的值
  15.                 int j = i; // 将i交给变量j，从当前位置开始处理。
  17.                 while (j > 0 && count > arrays[j -1]) { // 如果j大于0，count大于前一位的元素则进行下面的操作。
  18.                     arrays[j] = arrays[j -1]; // 将前一位元素的值和后一位元素的值互换。
  19.                     j--; // 继续向前比较。
  20.                 }
  21.                 arrays[j] = count; // 将count中的值归位。
  22.             }
  23.         }
  24.         System.out.println(Arrays.toString(arrays));
  25.     }
  26. }

DeBug分析

  • 通过debug调试的方式对代码进行逐行分析
  1. 首先在外层for循环中打上一个断点。<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/10360782/1615796354896-21871ca0-7329-48ac-9400-1b9576d5cc02.png#align=left&display=inline&height=42&margin=%5Bobject%20Object%5D&name=image.png&originHeight=42&originWidth=1496&size=15517&status=done&style=none&width=1496)

  • i 从1号索引开始遍历。

    然后点击 Step Over 进行下一步流程
    image.png

  • 第二步进入了 if 判断，此时 i 遍历指向了1号索引， 也就是3元素。如果 arrays[i] 小于 arrays[i-1],也就是1号索引的3元素小于 i减1 ，也就是小于0号索引的5元素，则再执行下一步操作。

在触发了if语句内的条件后，则紧接着将 arrays[i] 赋值给临时变量 count 进行保存。
image.png

  • 此时arrays[i]指向了1号索引下标，也就是3号元素

    继续 Step Over 下一步，在外部定义一个变量 j 并且将 i 属性赋值给它。用于后面的操作。
    image.png

  • 注： i 变量指向的索引编号为1，也就是数字为3的元素。

    外层 for 循环是用于控制等待排序的元素，而下面还需要一个循环来控制元素排序的次数，由于不确定循环几次，所以下面用到 while 循环进行循环判断。
    image.png

  • while循环中的条件为，j（元素为3） > 0 并且count（元素为3）小于 arrays[j-1 也就是前一位元素，条件成立则继续往下执行。

    当while循环条件成立则进行元素索引值的互换。
    image.png

    • j的1号索引值和j-1的0号索引互换位置。

每次循环都有一次 -- 的操作，目的是继续对左边的元素值进行比较。
image.png

继续 Step Over 下一步
image.png

  • 在执行了 i-- 之后，继续往左进行检索，指向0号索引，可以看到图中的0号索引为j，并且不大于0，其本身是等于0的，并且虽然count<arrays[j-1]成立，但依然不能执行下一步，所以直接跳到下一步进行数值的位置交换。

image.png

图：进行位置的交换

继续下一步，回到最外层的循环，可以看到两个数已经被互换了过来。
image.png

  • 至此上面第一轮的两个数已经互换完毕，下一轮则是根据第二个索引编号进行排序操作，如果小于前一位则互换位置，否则继续循环操作，直到找到比左边元素小的数值。

image.png

  • 第二轮排序，从2号索引4号元素开始判断。以上步骤以此类推。