JS 學資料結構與演算法 (排序篇) — 選擇排序法 & 插入排序法

各種排序法複雜度一覽表

前言

這篇文章將為排序篇章做一個結尾，文章會介紹選擇排序 (Selection Sort) 與插入排序 (Insertion Sort) 兩種排序法，透過上圖的排序法複雜度一覽表可以發現他們的執行效能相比其他排序法來的差一點，因此比較不常被使用，但要強調的是他們仍然有適合使用的情境，本篇文章將會簡單紀錄這兩個演算法的定義與程式碼實作。

選擇排序法 (Selection Sort)

選擇排序法示意圖

簡單來說選擇排序法一直重複的做兩件事:

1. 從尚未經過排序的陣列中找到最小值
2. 將當前找到最小值擺到最左邊

時間複雜度 O(n²)

程式碼範例

這邊先設陣列的第一個數字是目前的最小值，然後往後把陣列的數值一個一個讀取，如果讀取的下個數比最小值大，就不作處理。而如果讀取到的數比目前的最小值小，就把目前的最小值換成這個數。重複這個方法把所有陣列裡的數都讀過一遍，就能確保目前的最小值為整個數列的最小值，扣除掉已經確定的最小值，剩下未確定的元素再重複執行以上步驟，直到陣列完成排序。

function selectionSort(array) {
  const length = array.length;
  for(let i = 0; i < length; i++){
    // 將當前索引設為最小值
    let min = i;
    let temp = array[i];
    for(let j = i+1; j < length; j++){
      if (array[j] < array[min]){
      // 找到比前一個最小值還小時設為新最小值
        min = j;
      }
     }
     // 執行交換
     array[i] = array[min];
     array[min] = temp;
    }
    return array;
}

插入排序法 (Insertion Sort)

插入排序法示意圖

插入排序法雖然整體而言效率不高，但當應用在資料量少且幾乎快排序完成的陣列時，效率卻相當良好。

其實插入排序法是我們日常生活中就會使用到的排序法喔！大家都玩過大老二吧，當發牌結束後我們通常會整理手牌，將牌依照數字排列，這其實就是插入排序法的一種應用喔！

簡單來說他的作法就是從未排序的陣列中一次讀取一個數值，再放到已排列的陣列中的適當位置。我認為上方示意圖解釋得還蠻清楚的，因此就不用數值來舉例。

平均時間複雜度 O(n^2)

還記得前面提到若陣列是幾乎已經排序好，使用插入排序法會較有效率嗎？原因是我們除了讀取每一個元素值外，若元素已經在自己該在的位置，我們便不用額外進行元素的移動，因此最好的狀況下時間複雜度可以來到 O(n)。

程式碼範例

function insertionSort(array) {
 const length = array.length;
 for (let i = 0; i < length; i++) {
  if (array[i] < array[0]) {
   // 如果數值小於陣列第一個元素，將數字移動到第一個位置
   array.unshift(array.splice(i,1)[0]);
  } else {
   if (array[i] < array[i-1]) {
    // 找到數值該插入的位置
    for (var j = 1; j < i; j++) {
     if (array[i] >= array[j-1] && array[i] < array[j]) {
      // 將數值移動到陣列正確位置
      array.splice(j,0,array.splice(i,1)[0]);
     }
    }
   }
  }
 }
}

結語

利用 4 篇的篇幅介紹了 5 種的排序演算法，雖然排序演算法還有很多種類，但自己認為這 5 種是最常出現也最廣為人知的，所以排序演算法篇章將在這裏告一個段落，本來下一個篇章想介紹搜尋 (Searching) ，但後來思考過後決定先介紹資料結構再進入其他演算法主題，畢竟許多演算法都需要依賴特定資料結構為基底呢。

下回預告：鏈結串列 (Linked List)