插入排序

package com.pangzi.stucture;

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
        
        int[] arr = {101,34,119,1};
        insertSort(arr);
    }

    //插入排序
    public static void insertSort(int[] arr){
        //使用for循环
        for(int i = 1;i< arr.length;i++){
            int insertVal = arr[i];//从数组的第二个元素开始，与第一个有序元素进行比较
            int insertIndex = i-1;//即arr[1]前面这个数的索引下标
            
            while(insertIndex >= 0 && insertVal < arr[insertIndex]){//判断索引不越界，且插入的元素小于插入元素左边的元素
                arr[insertIndex + 1] = arr[insertIndex];//将第一个元素向右移动1位,将arr[0]赋值给arr[1]
                insertIndex--;//将arr[0]的索引减一，这时候insertIndex为-1
            }
            
             arr[insertIndex + 1] = insertVal;//将待插入元素赋值给arr[-1+1]，即arr[0]
            
        }