排序算法(1)--Insert Sorting--插入排序[1]--straight insertion sort--直接插入排序

将一個記錄插入到已排序好的有序表中，進而得到一個新，記錄數增1的有序表。即：先将序列的第1個記錄看成是一個有序的子序列，然後從第2個記錄逐個進行插插入到已入，直至整個序列有序為止。

作者QQ：1095737364    QQ群：123300273     歡迎加入！

1.基本思想

　　将一個記錄插入到已排序好的有序表中，進而得到一個新，記錄數增1的有序表。即：先将序列的第1個記錄看成是一個有序的子序列，然後從第2個記錄逐個進行插插入到已入，直至整個序列有序為止。

2.實作原理

　　每次從無序表中取出第一個元素，把它插入到有序表的合适位置，使有序表仍然有序。

　　第一趟比較前兩個數，然後把第二個數按大小插入到有序表中； 第二趟把第三個資料與前兩個數從後向前掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以後就完成了整個排序過程。

　　直接插入排序是由兩層嵌套循環組成的。外層循環辨別并決定待比較的數值。内層循環為待比較數值确定其最終位置。直接插入排序是将待比較的數值與它的前一個數值進行比較，是以外層循環是從第二個數值開始的。目前一數值比待比較數值大的情況下繼續循環比較，直到找到比待比較數值小的并将待比較數值置入其後一位置，結束該次循環。

3.代碼執行個體

　　(1)代碼:

public static void insertsort(int arr[]){
    for(int i = 1;i < arr.length; i ++){
        if(arr[i] < arr[i-1]){//注意[0,i-1]都是有序的。如果待插入元素比arr[i-1]還大則無需再與[i-1]前面的元素進行比較了，反之則進入if語句
            int temp = arr[i];
            int j;
            for(j = i-1; j >= 0 && arr[j] > temp; j --){
                arr[j+1] = arr[j];//把比temp大或相等的元素全部往後移動一個位置
            }
            arr[j+1] = temp;//把待排序的元素temp插入騰出位置的(j+1)
        }
    }
}
public static void main(String[] args) {
    int array[] = {4,2,1,5};
    System.out.println("排序之前：");
    for(int element : array){
        System.out.print(element+" ");
    }
    insertsort(array);
    System.out.println("\n排序之後：");
    for(int element : array){
        System.out.print(element+" ");
    }
}      

　　(2)結果:

排序之前：  
4 2 1 5 
排序之後：
1 2 4 5       

4.算法分析

　　1.當元素的初始序列為正序時，僅外循環要進行n-1趟排序且每一趟隻進行一次比較，沒有進入if語句不存在元素之間的交換(移動)。此時比較次數(Cmin)和移動次數(Mmin)達到最小值。

Cmin = n-1    

Mmin = 0;

     　　 此時時間複雜度為O(n)。

　　2.當元素的初始序列為反序時，每趟排序中待插入的元素都要和[0,i-1]中的i個元素進行比較且要将這i個元素後移(arr[j+1] = arr[j])，i個元素後移移動次數當然也就為i了，再加上temp = arr[i]與arr[j+1] = temp的兩次移動，每趟移動的次數為i+2,此時比較次數(Cmin)和移動次數(Mmin)達到最小值。

  　　　　　  Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2)

　　　　　　Mmax = (1+2)+(2+2)+...+(n-1+2) = (n-1)*(n+4)/2 = O(n2)  (i取值範圍1~n-1)

      　　 此時時間複雜度為O(n2)。

　　3.在直接插入排序中隻使用了i,j,temp這3個輔助元素，與問題規模無關，是以空間複雜度為O(1).

　　4.在整個排序結束後，即使有相同元素它們的相對位置也沒有發生變化，

                  如：5,3,2,3排序過程如下

                     A--3,5,2,3

                     B--2,3,5,3

                     C--2,3,3,5

     排序結束後兩個元素3的相對位置沒有發生改變，是以直接插入排序是一種穩定排序。

5.排序特點

(1)它是穩定排序，不改變相同元素原來的順序。

(2)它是in-place排序，隻需要O(1)的額外記憶體空間。

(3)它是線上排序，可以邊接收資料邊排序。

(4)它跟我們牌撲克牌的方式相似。

(5)對小資料集是有效的。