資料結構--直接插入排序

直接插入排序

概念

插入排序的基本思想是：在一個已排好序的記錄子集的基礎上，每一步将下一個待排序的記錄有序地插入到已排好序的記錄子集中，直到将所有待排記錄全部插入為止。

插入類排序的整個過程就如同打撲克的理牌過程類似，拿到一張牌然後在已排好序的序列中找到一個合适的位置将這張牌插入。

function insSort(arr){
    if(!arr && !arr.length){return -1;}
    for(let i=2,len=arr.length; i<len; i++){
        const curNum = arr[i];
        let j = i - 1 ;
        while(curNum < arr[j]){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = curNum;
    }
    return arr;
}
           

把目前數（curNum）之前的所有數字看做有序數組，從後往前逐個比較，找到合适位置後插入。

注：上述寫法由于變量

j

可能取值-1，是以在其他語言中可以采用将數組的第一個位置設定為目前值的方式（哨兵）來避免數組越界問題。

算法要點

• 從後往前查找應插入的位置
• 查找與移動在同一循環中完成

算法分析

從空間角度看，僅需要一個

curName

變量來存儲目前需要插入的數值。

從時間角度看，時間主要耗費在數值的比較和數組的移動上。

對于一趟插入排序，算法中的

while

循環的次數主要取決于待插記錄與前

i-1

個記錄的關鍵字的關系上。

最好情況為(順序)： r [ i ] . k e y &gt; r [ i − 1 ] . k e y r[i].key&gt; r[i-1].key r[i].key>r[i−1].key，while 循環隻執行 1 次，且不移動記錄；最壞情況為(逆序): r [ i ] . k e y &lt; r [ 1 ] . k e y r[i].key&lt; r[1].key r[i].key<r[1].key， 則

while

循環中關鍵字比較次數和移動記錄的次數為

i-1

。

對整個排序過程而言，最好情況是待排序記錄本身已按關鍵字有序排列，此時總的比較次數為 n − 1 n-1 n−1次，移動記錄的次數也達到最小值(n-1)(每一次隻對待插記錄移動一次)；最壞情況是待排序記錄按關鍵字逆序排列，此時總的比較次數達到 最大值為 ( n + 2 ) ( n − 1 ) / 2 (n+2)(n-1)/2 (n+2)(n−1)/2，記錄移動的次數也達到最大值 ( n + 4 ) ( n − 1 ) / 2 (n+4)(n-1)/2 (n+4)(n−1)/2。

執行的時間耗費主要取決于資料的分布情況。若待排序記錄是随機的，即待排序記錄可能出現的各種排列的機率相同， 則可以取上述最小值和最大值的平均值，約為 n2/4。是以，直接插入排序的時間複雜度為 T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2)，空間複雜度為 S ( n ) = O ( 1 ) S(n)=O(1) S(n)=O(1)。

排序算法的穩定性必須從算法本身加以證明。直接插入排序方法是穩定的排序方法。在直接插入排序算法中，由于待插入元素的比較是從後向前進行的， 循環

while

( x . k e y &lt; r [ j ] . k e y x.key&lt; r[j].key x.key<r[j].key)的判斷條件就保證了後面出現的關鍵字不可能插入到與前面相同的關鍵字之前。

總結

直接插入排序算法簡便，比較适用于待排序記錄數目較少且基本有序的情況。

當待排記錄數目較大時，直接插入排序的性能就不好， 為此我們可以對直接插入 排序做進一步的改進。

在直接插入排序法的基礎上，從==減少“比較關鍵字”和“移動記錄”==兩種操作的次數着手來進行改進。