package com.rao.linkList;

import java.util.Arrays;

/**
 * @author Srao
 * @className InsertSort
 * @date 2019/12/4 12:02
 * @package com.rao.linkList
 * @Description 插入排序
 */
public class InsertSort {

    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++){

            //先把要插入的数保存下来
            int temp = arr[i];

            int k = i-1;

            //找到第一个比它小的数的下标
            while (k >=0 && arr[k] > temp){
                k--;
            }

            //把较小的元素之前的元素全部后移一位，为要插入的元素空出一个位置
            for (int j = i; j > k+1; j--){
                arr[j] = arr[j-1];
            }

            //插入这个元素到第一个比它小的元素的前面
            arr[k+1] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3,6,2,5,9,1,0,8};
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println(Arrays.toString(arr));

    }
}