一、引言
在排序算法的大家族中，插入排序是一种简单且直观的排序方法。它的基本思想类似于我们日常生活中整理扑克牌的方式，通过不断地将未排序的数据插入到已排序的合适位置，逐步完成整个数组的排序。在这篇博客中，我们将深入分析一段用 Java 实现插入排序的代码，帮助大家更好地理解插入排序的原理和具体实现过程。
二、插入排序原理
插入排序的工作原理可以概括为以下步骤：
- 从数组的第二个元素开始（索引为 1），将其视为待插入的元素。
- 与已排序部分（初始时为数组的第一个元素）的元素依次进行比较。
- 如果待插入元素小于已排序部分的某个元素，就将该元素及其后面的已排序元素依次向后移动一位，为待插入元素腾出合适的位置。
- 直到找到待插入元素的合适位置（即前面的元素都小于等于它，后面的元素都大于等于它），将待插入元素插入到该位置。
- 重复上述步骤，每次处理一个未排序的元素，直到整个数组都被排序完成。
三、代码分析
1. 代码整体结构
以下是我们要详细分析的 Java 插入排序代码：
package 排序;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for (int i = 1; i < arr.length - 1; i++) {
//j和j+1进行比较交换
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
} else {
break;
}
}
}
}
}
2. main方法
在 main 方法中，首先定义了一个整数数组 arr，并初始化其值为 {5, 7, 4, 2, 0, 3, 1, 6}。这就是我们要进行排序的原始数组。
int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
然后调用了 sort 方法，并将数组 arr 作为参数传递给它，目的是对这个数组进行排序操作。
sort(arr);
最后，在排序完成后，使用 Arrays.toString 方法将排序后的数组以字符串的形式输出到控制台，以便直观地查看排序的结果。
System.out.println(Arrays.toString(arr));
3. sort 方法
sort 方法是实现插入排序核心逻辑的地方，下面我们来详细剖析其内部的循环结构和比较交换操作。
外层循环：
通过for (int i = 1; i < arr.length - 1; i++)这个外层循环，从数组的第二个元素（索引为 1）开始，依次遍历数组中的每个未排序元素。每次循环，都将当前索引为i的元素视为待插入的元素，准备将其插入到已排序部分的合适位置。内层循环：
在内层，通过for (int j = i - 1; j >= 0; j--)这个循环，从待插入元素的前一个元素（索引为i - 1）开始，依次向前遍历已排序部分的元素。这个循环的目的是将待插入元素与已排序部分的元素进行比较，并在必要时进行交换操作，以便为待插入元素腾出合适的位置。元素比较与交换：
在每次内层循环中，如果发现当前已排序元素arr[j]大于待插入元素arr[j + 1]（这里注意arr[j + 1]实际上就是当前的待插入元素，因为在内层循环中，我们是从后往前比较的），就通过一个临时变量temp来进行交换操作。具体交换过程如下：
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
} else {
break;
}
先将 arr[j] 的值赋给 temp，然后将 arr[j + 1] 的值赋给 arr[j]，最后将 temp 的值赋给 arr[j + 1]，这样就完成了两个元素的交换。如果发现当前已排序元素不大于待插入元素，说明已经找到了待插入元素的合适位置，就通过 break 语句跳出内层循环，不再继续向前比较。
四、测试结果
当我们运行上述代码时，对于给定的初始数组 {5, 7, 4, 2, 0, 3, 1, 6}，经过插入排序后，控制台会输出排序后的数组。不过需要注意的是，当前代码中的外层循环条件 for (int i = 1; i < arr.length - 1; i++) 存在一点小问题，应该改为 for (int i = 1; i < arr.length; i++)，这样才能确保数组中的所有元素都能参与排序。在修正这个问题后，排序后的数组结果应该是 {0, 1, 2, 3, 4, 5, 6, 7}。