思路
有數(shù)組[26, -3, 14, -15, 0, 324, 98, 1, 22]
現(xiàn)對(duì)該數(shù)組進(jìn)行排序狠毯，使用插入排序算法蚕脏。
先來(lái)屢一下思路和步驟：
- 從下標(biāo)為1的元素開(kāi)始進(jìn)行遍歷；
- 如果它前面的元素比它大，那么將前面的元素進(jìn)行后移回挽，并記錄下標(biāo)；
- 直至遇見(jiàn)小于等于它的數(shù)猩谊，將當(dāng)前元素插入上面記錄的下標(biāo)中千劈。
講解
第一步，記錄當(dāng)前元素（從下標(biāo)為1的元素開(kāi)始）牌捷，即 -3墙牌；插入下標(biāo)初始化為 -1。
image.png
第二步暗甥，將 -3 前面的所有元素與 -3 進(jìn)行對(duì)比喜滨，大于 -3 的，進(jìn)行后移撤防，并將后移元素的下標(biāo)賦值到插入下標(biāo)中：
image.png
第三步虽风，將當(dāng)前元素 -3 插入到插入下標(biāo)的位置：
image.png
這樣就完成了一個(gè)元素的插入排序。以此類推即可完成整個(gè)數(shù)組排序寄月。
實(shí)現(xiàn)
@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;
}
// 從下標(biāo)為1的元素開(kāi)始遍歷
for (int i = 1; i < nums.length; i++) {
// 記錄當(dāng)前元素
int cur = nums[i];
// 初始化插入下標(biāo)為-1
int insertIndex = -1;
// 遍歷當(dāng)前元素前面的所有元素
for (int j = i - 1; j >= 0; j--) {
// 如果前面的某個(gè)元素大于當(dāng)前元素辜膝，則前面的元素后移一位
if (nums[j] > cur) {
// 元素后移
nums[j + 1] = nums[j];
// 記錄插入下標(biāo)
insertIndex = j;
}
}
// 如果插入下標(biāo)不等于-1，將當(dāng)前元素賦值到插入下標(biāo)
if (insertIndex != -1) {
nums[insertIndex] = cur;
}
}
}
看一下運(yùn)行結(jié)果：
image.png
這樣插入排序就實(shí)現(xiàn)完成了漾肮。
