思路
有数组[26, -3, 14, -15, 0, 324, 98, 1, 22]
现对该数组进行排序，使用插入排序算法。
先来屡一下思路和步骤：
- 从下标为1的元素开始进行遍历；
- 如果它前面的元素比它大，那么将前面的元素进行后移，并记录下标；
- 直至遇见小于等于它的数，将当前元素插入上面记录的下标中。
讲解
第一步，记录当前元素（从下标为1的元素开始），即 -3；插入下标初始化为 -1。
image.png
第二步，将 -3 前面的所有元素与 -3 进行对比，大于 -3 的，进行后移，并将后移元素的下标赋值到插入下标中：
image.png
第三步，将当前元素 -3 插入到插入下标的位置：
image.png
这样就完成了一个元素的插入排序。以此类推即可完成整个数组排序。
实现
@Test
public void sortTest() {
int[] nums = new int[]{26, -3, 14, -15, 0, 324, 98, 1, 22};
insertSort(nums);
System.out.println(Arrays.toString(nums));
}
private void insertSort(int[] nums) {
if (nums.length < 2) {
return;
}
// 从下标为1的元素开始遍历
for (int i = 1; i < nums.length; i++) {
// 记录当前元素
int cur = nums[i];
// 初始化插入下标为-1
int insertIndex = -1;
// 遍历当前元素前面的所有元素
for (int j = i - 1; j >= 0; j--) {
// 如果前面的某个元素大于当前元素，则前面的元素后移一位
if (nums[j] > cur) {
// 元素后移
nums[j + 1] = nums[j];
// 记录插入下标
insertIndex = j;
}
}
// 如果插入下标不等于-1，将当前元素赋值到插入下标
if (insertIndex != -1) {
nums[insertIndex] = cur;
}
}
}
看一下运行结果：
image.png
这样插入排序就实现完成了。
