插入排序算法詳解，排序算法詳解

插入排序算法詳解，排序算法詳解

1 圖解

android學習手冊地址android學習手冊包含9個章節，108個例子，源碼文檔隨便看，例子都是可交互，可運行，源碼采用android studio目錄結構，高亮顯示代碼，文檔都采用文檔結構圖顯示，可以快速定位。360手機助手中下載,圖標上有貝殼

2概念介紹

有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入後此數據序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外（讓數組多一個空間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。

3 過程

直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的紀錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的紀錄插入完為止，得到一個新的有序序列。^[1] 

例如,已知待排序的一組紀錄是：

60,71,49,11,24,3,66

假設在排序過程中，前3個紀錄已按關鍵碼值遞增的次序重新排列，構成一個有序序列：

49,60,71

將待排序紀錄中的第4個紀錄（即11）插入上述有序序列，以得到一個新的含4個紀錄的有序序列。首先，應找到11的插入位置，再進行插入。可以講11放入數組的第一個單元r[0]中，這個單元稱為監視哨，然後從71起從右到左查找，11小於71，將71右移一個位置，11小於60，又將60右移一個位置，11小於49，又再將49右移一個位置，這時再將11與r[0]的值比較，11≥r[0]，它的插入位置就是r[1]。假設11大於第一個值r[1]。它的插入位置應該在r[1]和r[2]之間，由於60已經右移了，留出來的位置正好留給11.後面的紀錄依照同樣的方法逐個插入到該有序序列中。若紀錄數n,續進行n-1趟排序，才能完成。

直接插入排序的算法思路：

（1） 設置監視哨r[0]，將待插入紀錄的值賦值給r[0]；

（2） 設置開始查找的位置j；

（3） 在數組中進行搜索，搜索中將第j個紀錄後移，直至r[0].key≥r[j].key為止；

（4） 將r[0]插入r[j+1]的位置上。

4 java代碼

public class InsertSort {
     public static void main(String[] args){
         int[] a = {87,45,78,32,17,65,53,9,122,1,88};
         printArray(a);
         insertSort(a);
         printArray(a);
     }
     public static void insertSort(int[] a){
         int i=0;
         int j=0;
         for( i=1;i<a.length;i++){
             int temp=a[i];
             if(a[i-1]>a[i]){
                 for(j=i-1;j>=0;j--){
                     if(temp<a[j]){
                         a[j+1]=a[j];
                        // a[j]=temp;
                     }else{
                         break;
                     }
                 }
                 a[j+1]=temp;
             }
             
         }
     }
     public static void swapArray(int i,int j,int[] a){
         int temp=a[i];
         a[i]=a[j];
         a[j]=temp;
     }
     public static void printArray(int[] array){
         for(int i:array){
                  System.out.print(i+" ");
          }
         System.out.println();
     }
}

5 類比

      插入排序非常類似於整撲克牌。在開始摸牌時，左手是空的，牌面朝下放在桌上。接著，一次從桌上摸起一張牌，並將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置，要將它與手中已有的牌從右到左地進行比較。無論什麼時候，左手中的牌都是排好序的。也許你沒有意識到，但其實你的思考過程是這樣的：現在抓到一張7，把它和手裡的牌從右到左依次比較，7比10小，應該再往左插，7比5大，好，就插這裡。為什麼比較了10和5就可以確定7的位置？為什麼不用再比較左邊的4和2呢？因為這裡有一個重要的前提：手裡的牌已經是排好序的。現在我插了7之後，手裡的牌仍然是排好序的，下次再抓到的牌還可以用這個方法插入。編程對一個數組進行插入排序也是同樣道理，但和插入撲克牌有一點不同，不可能在兩個相鄰的存儲單元之間再插入一個單元，因此要將插入點之後的數據依次往後移動一個單元。

6、效率分析

如果輸入數組已經是排好序的話，插入排序出現最佳情況，其運行時間是輸入規模的一個線性函數。如果輸入數組是逆序排列的，將出現最壞情況。平均情況與最壞情況一樣，其時間代價是Θ(n2)。

穩定 
空間復雜度O(1) 
時間復雜度O(n²) 
最差情況：反序，需要移動n*(n-1)/2個元素 
最好情況：正序，不需要移動元素

數組在已排序或者是“近似排序”時，插入排序效率的最好情況運行時間為O(n)；

插入排序最壞情況運行時間和平均情況運行時間都為O(n²)。

通常，插入排序呈現出二次排序算法中的最佳性能。

對於具有較少元素（如n<=15）的列表來說，二次算法十分有效。

在列表已被排序時，插入排序是線性算法O(n)。

在列表“近似排序”時，插入排序仍然是線性算法。

在列表的許多元素已位於正確的位置上時，就會出現“近似排序”的條件。

通過使用O(nlog₂n)效率的算法（如快速排序）對數組進行部分排序，

然後再進行選擇排序，某些高級的排序算法就是這樣實現的。