package com.atguigu.sort;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr = {54, 12, 78, 687, 35, 5, 665,};
System.out.println("开始为"+ Arrays.toString(arr));
insertSort(arr);
System.out.println("插入排序后,结果为"+ Arrays.toString(arr));
}
public static void insertSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
int insertVal = arr[i+1];
int insertIndex = i;
//1.insertIndex >= 0保证不越界
//2.insertVal < arr[insertIndex] 表示待插入的数还没有找到位置
//3.while循环使得insertindex不断向前移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex+1]=arr[insertIndex];
insertIndex--;
}
// insertIndex+1即为插入的位置
//这里增加是否需要赋值
if (i!=insertIndex){
arr[insertIndex+1]=insertVal;
}
}
}
}