插入排序

将数组分成两部分，左侧排序好的，右侧未排序的，然后从右侧拿数据，遍历左侧数据进行比较替换
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {9, 3, 1, 4, 6, 8, 7, 5, 2};
        sort(arr);
        print(arr);
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    private static void sort(int[] arr) {
        // 默认第一位排好序，从第二位开始
        for (int i = 1; i < arr.length; i++) { // 外层相当于从无序中抽牌
            for (int j = i; j > 0; j--) { // 遍历有序的  进行比较换牌
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                }
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void print(int[] arr) {

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

　　优化:折半插入排序，缩短有序队列中遍历范围

    /**
     * 插入排序-折半插入
     *
     * @param arr
     */
    private static void sort2(int[] arr) {
        // 默认第一位排好序，从第二位开始
        for (int i = 1; i < arr.length; i++) { // 外层相当于从无序中抽牌
            int left = 1, right = i - 1;
            int temp = arr[i];
            while (left <= right) {
                int mid = (right + left) / 2;
                if (temp < arr[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i; j > right; j--) { // 遍历有序的  进行比较换位置
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                }
            }
        }
    }