插入排序

插入排序分两种：

1.直接插入排序

直接插入排序默认一个已经有序的集合，然后把待排节点插入到这个有序集合中去.

/**
     * 直接插入算法：
     * 思路：将一个元素插入到一个已经有序的集合中去.
     * 最好的情况是：O(n).
     * 最坏的情况是：O(n ^ 2).
     * 稳定算法.
     * 使用：当 n 很小的时候，适用，当 n 很大的时候，则不宜采用该算法.
     */
    @Test
    public void testDirectInsertSort(){
        int[] arr = {4,2,5,1,2,9,8,3,5,6,2,8};

        for(int i=1; i<arr.length; i++){
            int temp = arr[i];
            int j;
            for(j=i-1; j>=0; j--){
                if(temp < arr[j]){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }

2.折半插入排序

折半插入排序在直接插入排序的基础上改进了比较的次数，但是移动次数任然没有改变.

/**
     * 折半插入算法：
     * 思路：在于移动. 因为已经排序完的是有序序列，所以可以使用折办插入的办法.
     * 最好的情况是：O(n)
     * 最坏的情况是：O(n ^ 2) 因为折半插入算法只是减少了比较次数，数据的移动次数还是没有改变.
     * 稳定算法.
     * 使用：当 n 很小的时候，适用，当 n 很大的时候，则不宜采用该算法.
     */
    @Test
    public void testHalfOfAHalfInsertSort(){
        int[] arr = {4,2,5,1,2,9,8,3,5,6,2,8};

        for(int i=1; i<arr.length; i++){
            int low = 0;
            int high = i-1;
            int temp = arr[i];
            while(low <= high){
                int half = (low + high) / 2;
                if(temp < arr[half]){
                    high = half - 1;
                }else {
                    low = half + 1;
                }
            }
            for(int k=i; k>low; k--){
                arr[k] = arr[k-1];
            }
            arr[low] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }