Java排序算法之插入排序

　　插入排序是简单排序中最快的排序算法，虽然时间复杂度仍然为O(n*n)，但是却比冒泡排序和选择排序快很多。

一、原理

　　1、将指针指向某个元素，假设该元素左侧的元素全部有序，将该元素抽取出来，然后按照从右往左的顺序分别与其左边的元素比较，遇到比其大的元素便将元素右移，直到找到比该元素小的元素或者找到最左面发现其左侧的元素都比它大，停止；

       2、此时会出现一个空位，将该元素放入到空位中，此时该元素左侧的元素都比它小，右侧的元素都比它大；

　　3、指针向后移动一位，重复上述过程。每操作一轮，左侧有序元素都增加一个，右侧无序元素都减少一个。

二、例子

　　待比较数据：7, 6, 9, 8, 5,1

　　第一轮：指针指向第二个元素6，假设6左面的元素为有序的，将6抽离出来，形成7,_,9,8,5,1，从7开始，6和7比较，发现7>6。将7右移，形成_,7,9,8,5,1，6插入到7前面的空位，结果：6,7,9,8,5,1

　　第二轮：指针指向第三个元素9，此时其左面的元素6,7为有序的，将9抽离出来，形成6,7,_,8,5,1，从7开始，依次与9比较，发现9左侧的元素都比9小，于是无需移动，把9放到空位中，结果仍为：6,7,9,8,5,1

　　第三轮：指针指向第四个元素8，此时其左面的元素6,7,9为有序的，将8抽离出来，形成6,7,9,_,5,1，从9开始，依次与8比较，发现8<9，将9向后移，形成6,7,_,9,5,1，8插入到空位中，结果为：6,7,8,9,5,1

　　第四轮：指针指向第五个元素5，此时其左面的元素6,7,8,9为有序的，将5抽离出来，形成6,7,8,9,_,1，从9开始依次与5比较，发现5比其左侧所有元素都小，5左侧元素全部向右移动，形成_,6,7,8,9,1，将5放入空位，结果5,6,7,8,9,1。

　　第五轮：同上，1被移到最左面，最后结果：1,5,6,7,8,9。

三、编码分析

　　需要两层循环，第一层循环index表示上述例子中的指针，即遍历从坐标为1开始的每一个元素；第二层循环从leftindex=index-1开始，leftindex--向左遍历，将每一个元素与i处的元素比较，直到j处的元素小于i出的元素或者leftindex<0；遍历从i到j的每一个元素使其右移，最后将index处的元素放到leftindex处的空位处。

四、算法实现

package sort;

import java.util.Arrays;

/**
 * @author zsh
 * @company wlgzs
 * @create 2019-02-15 20:59
 * @Describe 插入排序两种实现方法
 */
public class InsertSort {

    //for循环实现插入排序
    static int[] insertSort1(int[] arr){
        //最外层指针从1开始
        for (int index = 1; index < arr.length; index++) {
            //存指针取出来的数据
            int temp = arr[index];
            //指针前一位索引
            int leftindex = index - 1;
            while (leftindex >= 0 && arr[leftindex] > temp ){
                arr[leftindex+1] = arr[leftindex];
                leftindex--;
            }
            //把temp放在空位上
            arr[leftindex+1] = temp;
        }
        return arr;
    }

    //递归实现插入排序
    static int[] insertSort2(int[] arr,int k){
        if (k == 0){
            return arr;
        }
        //对前k-1个元素排序
        insertSort2(arr,k-1);
        //把k位置上的元素插入到前面的部分
        int x = arr[k];
        int index = k -1;
        while (index >= 0 && x <arr[index]){
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = x;
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5,4,9,6,3};
        System.out.println(Arrays.toString(insertSort1(arr)));
        System.out.println(Arrays.toString(insertSort2(arr,arr.length-2)));
    }

}

五、插入排序分析

　　时间复杂度，由于仍然需要两层循环，插入排序的时间复杂度仍然为O(n*n)。
　　比较次数：在第一轮排序中，插入排序最多比较一次；在第二轮排序中插入排序最多比较二次；以此类推，最后一轮排序时，最多比较N-1次，因此插入排序的最多比较次数为1+2+...+N-1=N*(N-1)/2。尽管如此，实际上插入排序很少会真的比较这么多次，因为一旦发现左侧有比目标元素小的元素，比较就停止了，因此，插入排序平均比较次数为N*(N-1)/4。

　　移动次数：插入排序的移动次数与比较次数几乎一致，但移动的速度要比交换的速度快得多。

　　综上，插入排序的速度约比冒泡排序快一倍（比较次数少一倍），比选择排序还要快一些，对于基本有序的数据，插入排序的速度会很快，是简单排序中效率最高的排序算法。