【排序算法03】--插入排序

package com.lll.algorithms.sort;

import java.util.Arrays;


public class InsertSort {
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            //定义一个待插入的数据
            int insertValue = arr[i];
            int insertIndex = i-1;
            //条件1：insertIndex>=0 保证insertIndex不越界（即不小于0）
            //条件2：insertValue < arr[insertIndex]满足的话说明insertValue还没有找到正确插入位置
            while(insertIndex>=0 && insertValue < arr[insertIndex]){
                // 将arr[insertIndex]元素后移
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }

            //当退出while循环时，表示本轮已经为insertValue找到正确的插入位置(注意：前面while循环中insertIndex进行了减减操作)
            arr[insertIndex+1] = insertValue;

        }

    }

    public static void main(String[] args) {
        int[] arr = {7,6,-1,9};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}