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



前面介绍了两个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

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

[html] view plain copy print?

1. /**  
2.     *   @author：kevin  
3.     *   @Description：   基础排序  
4.     *   @Date：0:00 2018/3/24  
5.     */  
6.     public void sort(int[] arr, int n){  
7.         for (int i = 1; i < n; i++) {  
8.             for (int j = i; j >0 ; j--) {  
9.                 if (arr[j] < arr[j-1]){  
10.                     SortUtil.swap(arr, j, j-1);  
11.                 }  
12.             }  
13.         }  
14.     }  

/**
    *   @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元素赋值给需要放置位置的那个元素即可：

[html] view plain copy print?

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