数据结构与算法之插入排序

前面介绍了两个O(n²)级别的算法，冒泡排序和选择排序，在本章节中，将继续介绍最后一个O(n²)的算法，插入排序。

基本思想：在我们对i这个元素进行排序时，假定i前面的元素都已经有序，那么只需将i位置的元素向前移动，知道它前面的元素小于等于它，后面的大于它即可。

排序数据：3,5,7,2,4,9,6,8,1

示意图：

第一次排序，对元素5进行排序，大于3位置不变。

第二次：对元素7进行排序，将7与5进行比较，7大于5，位置不变。

第三次：对元素2进行排序，2小于7，交换位置，2小于5交换位置，2小于3交换位置。

第四次：对元素4进行排序，4小于7，交换位置，4小于5，交换位置。

依此类推，第五次排序后的数组为：

    2 3 4 5 7 9 6 8 1

第六次排序后的数组为：

  2 3 4 5 6 7 9 8 1

第7次排序后的数组为：

2 3 4 5 6 7 8 9

第8次排序后的数组为：

1 2 3 4 5 6 7 8 9

根据此演示不难写出算法。

/**
    *   @author：kevin
    *   @Description：   基础排序
    *   @Date：0:00 2018/3/24
    */
    public void sort(int[] arr, int n){
        for (int i = 1; i < n; i++) {
            for (int j = i; j >0 ; j--) {
                if (arr[j] < arr[j-1]){
                    SortUtil.swap(arr, j, j-1);
                }
            }
        }
    }

优化：

思考上面的排序算法，我们每次在对元素i进行排序的时候如果小于前面的都会交换位置，我们知道，交换位置是一个很费时的操作，如果在对元素i进行排序的时候，我们只是将元素后移，直到找到元素i应该放置的位置，再将i元素赋值给需要放置位置的那个元素即可：

/**
     *   @author：kevin
     *   @Description：   优化1
     *   如果每次往前移动的时候只是将元素后移，最后只是将要交换的元素和其交换即可
     *   @Date：0:00 2018/3/24
     */
    public void sort1(int[] arr, int n){
        for (int i = 1; i < n; i++) {
            int temp = arr[i];
            int j = i;
            for (; j >0 && temp < arr[j-1]; j--) {
                    arr[j] = arr[j-1];
            }
            arr[j] = temp;
        }
    }