over 1 year ago

插入排序法是我們第一個學習到的排序方法,我們本篇會針對它來詳細的介紹一下。

  • 插入排序法的原理
  • 插入排序法的執行效能
  • javascript演算法實作

插入排序法的原理

我們先來看看下圖,來理論一下它是著麼進行排序,該圖來源為此interactivepython

首先,我們會將資料分成兩部份,已排序與未排序,然後我們會進行將已排序資料與後一個資料進行比較,如果已排序資料大於它,則進行位移,我們下面將以前四行來進行說明。

注意,下列的A[0]代表陣列的第一個位置。

  • 第一行 : 已排序資料為54,然後我們與後一個26進行比較,54大於26因此我們會將26的位置替換成54,並將26插入至54的原位,結果為第二行。
  • 第二行 : 已排序資料為26、54,然後我們與後一個93進行比較,54小於93因此不用進行位移,因為26、54為已排序資料,因此只需要比較54就好,結果為第三行。
  • 第三行 : 已排序資料為26、54、93,然後與17進行比較,首先93大於17因此將93位移置A[3],則時還沒插入喔,還要繼續比較,接下來54大於17因此將54位移至A[2],然後26大於17,因此將26位移至A[1],最後在將17插入剩餘的空間A[0],結果為第四行。
  • 第四行 : 已排序資料為17、26、54、93,開始與77進行比較,93大於77因此將93位移至A[4]的位置,然後54小於77,因此54不需要位移,最後將77插入至空缺的位置A[3],當果為第五行。

插入排序法的執行效能

那這個排序演算法效能如何 ? 我們會分成最好與最壞與平均來看。

最好狀況

O(n)

該演算法最好的情況是時間複雜度為O(n),假設我們有下列陣列要排序。

[ 1 , 2 , 3 , 4 ] 

我們一看就知道,他不用進行排序,但演算法還不知道,所以它至少還是要跑個for迴圈,跑個4次,才知道它不用排序,因為我們這時最好的狀況就是只要跑4次,也就是陣列的大小。

最壞狀況

O(n^2)

假設我們要下列陣列要排序。

[ 4 , 3 , 2 , 1 ] 

對就是完全相反的,我們首先要跑for迴圈,然後裡面還要一個while比較,而且因為我們的陣列是完全相反的。

平均狀況

O(n^2)

我也不知道為啥平均是O(n^2),真的。

建議使用情況

  • 要排序的資料數量不大 : 平均是時間複雜度是O(n^2),如果來個1百萬個 n,你看看會如何。
  • 大部份的資料已排序 : 上面有說過,該演算法會將資料分成已排序與未排序的來進行比較,也就是說如果已排序的資料越多,你就可以少做越少的比較。

javascript演算法實作

我們來看看它的演算法,我們採用javascript來進行撰寫。

function insertionSort(arr) {
  if (!Array.isArray(arr))
    throw 'elements is not array';

  var len = arr.length;
  var i = 0,
    value = 0;
    
  for (var pos = 1; pos < len; pos++) {
    i = pos - 1;
        value = arr[pos];  //正在處理的值
        
    //判斷是否移位
    while (i >= 0 && arr[i] > value) { 
      arr[i + 1] = arr[i];
      i--;
    }
    
    // 插入新值
    arr[i + 1] = value;
    
      console.log(arr);
  }
}

簡單的測試一下。

insertionSort([3,54,24,33,22,58,95,1,2,31])

參考資料

← 搜尋之二元搜尋法 (binary search) 排序之選擇排序法(Selection Sort) →
 
comments powered by Disqus