插入排序

public static void (String[] args) {

   
    int arr[] ={9,8,7,6,5,4,3};

    InsertSort(arr);
    System.out.println(Arrays.toString(arr));
}

public static int[] InsertSort(int[] arr){

    //分成已排序和dai待排序两部分
    //初始状态 已排序部分：第一个元素  待排序部分：第二个元素至最后一个元素

    for(int i=1;i < arr.length ;i++){
        //待插入的值
        int insertValue=arr[i];
        // 插入的位置
        int insertIndex=i-1;
        while( insertIndex>=0 && insertValue < arr[insertIndex]){
           //待插入的值比已排序部分的元素值小,已排序部分当前比较元素后移
            arr[insertIndex+1] =arr[insertIndex];
            //待插入的值比已排序部分的元素值小，插入位置前移
            insertIndex--;
        }

        //将待插入的值赋值到对应位置的数组中
        arr[insertIndex+1] = insertValue;
    }

    return arr;
}