package com.jiucaiyuan.net.algrithm.sort;



/**

 * <pre>

 * 插入法排序

 * i从0~N-1

 * 处理0~i位置上有序，检查i-1和i是否有序，如果没有，交换，再检查i-2和i-1是否有序

 * （效果就是当前i个元素往前找，找到合适自己的位置）

 * 排序结果是升序数组

 * 时间复杂度O(N^2)    空间复杂度O(1)

 *

 * 数据状况不同，时间复杂度不同

 * 最差的情况 7 6 5 4 3 2 1 时：时间复杂度O(N^2)    空间复杂度O(1)

 * 最好的情况 1 2 3 4 5 6 7 时：时间复杂度O(N)    空间复杂度O(1)

 * </pre>

 *

 * @Author jiucaiyuan  2022/3/25 21:48

 * @mail services@jiucaiyuan.net

 */



public class InsertSort {



    public static void insertionSort(int[] arr) {

        if (arr == null || arr.length < 2) {

            return;

        }

        //0位置时是有序的，所以直接从1位置开始处理

        for (int i = 1; i < arr.length; i++) {

            for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {

                swap(arr, j - 1, j);

            }

        }

    }

    private static void swap(int[] arr, int i, int j) {

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }



    public static void main(String[] args) {

        int[] arr = {1, 2, 8, 3, 5, 7, 2, 7, 8, 12, 4};

        insertionSort(arr);

        print(arr);

    }



    private static void print(int[] arr) {

        if (arr == null) {

            return;

        }

        for (int a : arr) {

            System.out.print(a + "\t");

        }

        System.out.println();

    }

}