Open in app

Sign in

Write

Sign in

演算法-資料結構學習筆記 Bubble Sort , Selection Sort, Insertion Sort

William Tsou
13 min readNov 1, 2021

一、前言

除了上一篇介紹過的搜尋演算法之外，還有另外一種情境就是排序。

面對生活中各式各樣的資料，有時會需要將資料按照某種條件來排序，例如按照數字大小或開頭英文字母的順序，這麼作不僅是為了看出資料之間的階層或規律，也可以方便搜索特定資料。

舉例來說，先前提到的二元搜尋法，就只能使用於排序過的資料。

然而，就像搜尋演算法的情況，不同的情境也會有各自適用的排序演算法，因此本篇要介紹的是三種常見的排序法：冒泡排序、選擇排序與插入排序，並且比較三者之間的差異和使用情境。

事不宜遲，讓我們開始吧！

二、Bubble Sort 冒泡排序

概念

冒泡排序是相對簡單的排序方式，它的概念是不斷比較兩個相鄰的資料，並依據排序的條件去判斷是否需要交換兩筆資料的位置，整個過程就是重複對所有的相鄰資料進行比較與交換的動作，直到整組資料的順序已經符合排序的條件，無須再交換。

用比較實際的方式來舉例，假設今天有一個陣列，紀錄的是 5 位遊戲角色的等級，並且需要從低到高排序。

[13, 25, 6, 77, 15]

冒泡排序的方式大約會有四個步驟，分別是：

  1. 比較相鄰的兩個元素，因為排序的條件是由小到大，如果 A > B，則交換位置，反之則不動。
[13, 25, 6, 77, 15] A < B // 13 與 25 的位置不變
  1. 從第一對相鄰元素逐一比較到最後一對相鄰元素，最後留在陣列尾部的就會是最大的元素，就像泡泡逐漸從底部冒至頂部的感覺。
[13, 25, 6, 77, 15]     A > B // 25 與 6 的位置交換[13, 6, 25, 77, 15]         A < B // 25 與 77 的位置不變[13, 6, 25, 77, 15]
             
             A > B // 77 與 15 的位置交換[13, 6, 25, 15, 77]
  1. 由於最後一個元素已經是最大值了，因此會針對前面的元素重複上述步驟。
[13, 6, 25, 15, 77] A > B // 13 與 6 的位置交換[6, 13, 25, 15, 77]...以此類推
  1. 回傳排序後的陣列。
[6, 13, 15, 25, 77]

實作

看完上述的舉例後，來試著實作一下冒泡排序的程式碼吧！

在冒泡排序的步驟中，有兩個部分是最重要的，第一個是每次比較相鄰資料後是否交換位置的動作；另一個則是確保每次都能比較每一對相鄰資料，除了已經排序好的最後一筆資料。

先來實作交換的部分吧！

function bubbleSort(arr) {
  // 透過 ES6 的解構賦值語法交換陣列元素位置
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
  }
}

好了，接著來實作逐一比較每一對相鄰元素的部分並且回傳排序好的陣列。

function bubbleSort(arr) {
  // 透過 ES6 的解構賦值語法交換陣列元素位置
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
  }
  
  // 加入這段
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      // 比較相鄰元素，如果 A > B 則呼叫先前定義好的 swap 交換兩者位置
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
      }
    }
  }
  // 回傳排序好的陣列
  return arr
}

這邊也有幾個重點要注意一下：

  • 第一層 for 迴圈之所以選擇由後往前迭代，是因為每一輪的比較，都會讓目前最大的值移動至陣列的最尾端，而下一輪就不需要再把最大值納入需要比較的範圍內了，所以設 i 為陣列的長度並且每比完一輪就減一，把移至尾端的最大值排除。
  • 第二層迴圈的條件設定為 j < i — 1，而不是 j < i，是因為 if 條件比較的索引值是目前的元素與下一個相鄰元素，因此如果設定為 j < i，就會迭代至陣列的最後一個元素，並且發生和最後一個元素的下一個元素 (undefined) 相比的不必要情況。
[13, 25, 6, 77, 15] // 以此陣列為例，第一層迴圈的 i = 5 (arr.length) ; 第二層迴圈的條件為 j < 4 (i - 1)
// 因此，j 最多只會到 3，並且和 4 (j + 1) 比較，也就是 77 與 15 ，避免 15 與 undefined 
// 比較的情況[13, 6, 25, 15, 77]// 第一輪比較完後，最大值 77 已經被移至陣列最後，所以無須再納入比較的範圍了
// 因此 i - 1 = 4, j < 3 ，由於 j 最多只會到 2，也就是只會比較到 25 與 15 的地方
// 就可以避免 15 與 77 比較的情況，因為毫無意義

最後，可以優化一下程式碼，因為目前的函式一定會將陣列內的所有相鄰元素逐一比對，直到最後一個輪次，但如果陣列早在那之前就已經排序完成，那麼後續的步驟就完全是浪費時間。

因此，需要一個方法可以讓函式判斷陣列已經排序完成時，就從迴圈中跳脫並回傳排序好的陣列。

實作的邏輯其實也很簡單，只要有任何的交換，就意味著尚未排序完成，因此只要該比較的輪次沒有發生任何交換，就可以跳脫迴圈，回傳排序好的陣列了。

function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
  }
  
  for (let i = arr.length; i > 0; i--) {
    // 加入變數儲存布林值，用於判斷是否排序完成，預設為 true
    let isSorted = true
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        // 交換元素位置後，也記得要把 isSorted 改為 false，表示本輪次尚未排序完成
        isSorted = false
      }
    }
    
    // 加入 if 條件判斷 isSorted 是否為 true，如果是的話則跳脫迴圈
    if (isSorted) break
  }
  return arr
}

冒泡排序的實作就到這裡告一段落了，但不免俗的還是要來分析一下它的時間複雜度。

由於在上述程式碼當中，使用了兩個迴圈去處理陣列，因此時間複雜度為 O(n²)，除非是幾乎已經排序好的陣列，如果可以順利第一輪比較就排序完成，則時間複雜度為 O(n)。

不過，之前在介紹 BIG O 時就提過，要以最壞情況的方式去計算，因此冒泡排序的時間複雜度為 O(n²)，是個雖然容易卻相對低效率的排序方式。

三、Selection Sort 選擇排序

選擇排序也是一種相對簡單直觀的排序方式，主要的原理是在尚未排序的資料集合中尋找最小的元素，並將其排在序列首部，再尋找第二小的元素，並依序排在下一位，不斷重複此過程直到整個資料集合排序完成。

以下用一個陣列說明選擇排序的運作方式，假設要將一個無序陣列內的數字由小到大排序：

[5, 3, 2, 1, 4] ↑  ↑    // 3 < 5，目前暫存的最小值為 3[5, 3, 2, 1, 4] ↑     ↑  // 2 < 3，目前暫存的最小值為 2[5, 3, 2, 1, 4] ↑        ↑  // 1 < 2，目前暫存的最小值為 1[5, 3, 2, 1, 4] ↑           ↑  // 4 > 1，目前暫存的最小值仍為 1，交換 5 與 1 兩個元素[1, 3, 2, 5, 4]    ↑  ↑  // 從第二個元素開始，重複上述過程，直到整個陣列排序完成

了解運作原理後，接著也來實作一下選擇排序吧！

這次一樣要撰寫一個函式，會接受一個陣列作為參數，並且回傳由小排序到大的陣列。

首先，要建立一層迴圈，從陣列的第一個元素迭代至陣列的最後一個元素。

接著，要建立一個變數，暫時儲存目前最小數字在陣列內的索引值，方便後續比較大小與交換位置。

第三，再建立第二層迴圈並且迭代第一層迴圈目前陣列索引值之後的所有元素，並依據比較大小的結果判斷是否需要更換最小數字索引值

function selectSort(arr) {
  // 第一層迴圈
  for (let i = 0; i < arr.length; i++) {
    // 用變數暫時儲存最小數字的索引值，先設定為 i
    let lowestNumIndex = i
    // 第二層迴圈，j 設為 i + 1，才不會重複比較兩個一樣的元素
    for (let j = i + 1; j < arr.length; j++) {
      // 如果暫存的最小數字，比目前迭代的陣列元素還大，則更新最小數字的索引值
      if (arr[lowestNumIndex] > arr[j]) {
        lowestNumIndex = j
      }
    }
  }
}

第四，第二層迴圈迭代結束後，lowestNumIndex 儲存的會是該輪搜尋到的最小數字 Index，如果與一開始宣告的 i 不同，表示最小數字並不在一開始宣告的索引 i，需要交換位置

交換的部分，可以直接沿用先前冒泡排序使用過的方法，直接用 ES6 的解構賦值。

最後，再回傳排序完的陣列即可。

function selectSort(arr) {
  // 宣告交換的函式
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
  }
  
  for (let i = 0; i < arr.length; i++) {
    let lowestNumIndex = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[lowestNumIndex] > arr[j]) {
        lowestNumIndex = j
      }
    }
    // 在第二層迭代完後，比較 lowestNumIndex 是否有改變，若有則交換元素的位置
    if (lowestNumIndex !== i) swap(arr, i, lowestNumIndex)
  }
  // 回傳排序好的陣列
  return arr
}

以上就是選擇排序的實作，時間複雜度來說，由於依舊使用到了兩個迴圈，所以最壞情況下會是 O(n²)。

不過和冒泡排序相比，其交換操作的次數比較少，每一輪比較至多只會交換一次，也就是說一個陣列元素數量為 n 時，其最多次的交換操作為 n — 1 次。

總結來說，選擇排序也不算是有效率的排序方式，但它的概念比較簡單，有助於理解後續更進階的排序演算法，但實際上可以運用的場合並不多。

四、Insertion Sort 插入排序

插入排序的概念是從未排序的集合左方開始建立一個有序的排列，在迭代後續每一個尚未排列的元素，從已經建立好的排序中，由後往前找到該未排序元素可以插入的位置，再往下迭代另一個未排序的元素，直到全部都插入至已排序陣列中對應的位置，就完成了排序。

以下也用一個陣列說明插入排序的運作方式，假設要將一個無序陣列內的數字由小到大排序：

[5, 3, 2, 1, 4] =  ↑    // 5 < 3，交換兩者的位置並且建立出一個有序排列[3, 5, 2, 1, 4] =  =  ↑  // 從有序排列的後方開始掃描， 2 < 5，再往前， 2 < 3，因此 2 要插入 3 的前方[2, 3, 5, 1, 4] =  =  =  ↑  // 從有序排列的後方開始掃描， 1 < 5 → 1 < 3 → 1 < 2，因此 1 要插入 2 的前方[1, 2, 3, 5, 4] =  =  =  =  ↑  // 從有序排列的後方開始掃描，4 < 5 → 4 > 3，因此 4 要插入 3 與 5 之間[1, 2, 3, 4, 5] =  =  =  =  =  // 排序完成囉

了解運作原理後，接著也來實作一下插入排序吧！

前幾個步驟與選擇排序類似，要建立第一層迴圈與變數儲存當前元素的值，差別在於插入排序在比較未排序的元素與已排序好的集合時，是由後往前掃描的，所以第二層迴圈的索引值必須是由大到小。

此外，要特別注意本次排序的邏輯是由小到大，假設目前指向的元素已經比有序排列的當前值還大，就不需要繼續往下迭代了，因為已經找到要插入的位置，或是根本不需要插入。

所以，第二層迴圈除了索引值要大於等於 0 之外，也要限制 i 指向的元素值如果大於第二層迴圈指向的元素值，就直接跳脫迴圈。

function insertionSort(arr) {
  
  // 第一層迴圈從第二個元素開始，因為第一個元素自身就可當作一個有序排列
  for (let i = 1; i < arr.length; i++) {
    // 建立變數儲存當前的元素
    let currentValue = arr[i]
    let currentScannedIndex = i - 1
    // 第二層迴圈是由後往前掃瞄有序排列，而且一旦當前元素值大於第二層迴圈指向的元素值，就停止迭代
    while(currentScannedIndex >= 0 && arr[currentScannedIndex] > currentValue) {
     
    }
  }
  // 回傳排序好的陣列
  return arr
}

好了，完成兩個迴圈的迭代順序與條件後，接著要來處理迴圈內比較大小的條件，以及交換的方式

實作插入的方式，其實就是在每次比較的時候，如果當前 i 指向的數值小於有序排列的當前數值，則將有序排列的數值往後移一位，並持續比較直到找到 i 指向的數值應該插入的位置。

當達成跳脫 while 迴圈的條件時，currentScannedIndex 指向的會是下一次要掃描的 index，所以補上 +1 就會是插入的位置了。

function insertionSort(arr) {
  
  for (let i = 1; i < arr.length; i++) {
    let currentValue = arr[i]
    let currentScannedIndex = i - 1
    
    while(currentScannedIndex >= 0 && arr[currentScannedIndex] > currentValue) {
      // 因為當前 i 指向的值小於當前掃描的元素，所以將當前掃描的元素往後移一位，再繼續往前掃描
      arr[currentScannedIndex + 1] = arr[currentScannedIndex]
      // 記得減一才會繼續往前掃描，否則會形成無窮迴圈
      currentScannedIndex--
    }
    // 每次跳脫 while 迴圈，就表示找到了應該插入的位置
    arr[currentScannedIndex + 1] = currentValue
  }
  
  return arr
}

就插入排序的時間複雜度而言，因為它也使用了兩個迴圈，所以最壞情況下會是 O(n²)，與上述兩者其實差別不大。

但是，由於它會先把資料整理成比較小的有序排列，再逐步插入其它未排序值的特性，在某些情況下也是十分好用的排序法。

舉例來說，如果資料並不是整理完之後就不會再變動，可能隨時會有新的資料加入時，插入排序法因為已經有整理好一個次要的有序排列，就很適合這種情況。

五、三種排序演算法的複雜度比較

總結一下三種排序法的差異或特色：

  1. 對於幾乎排序好的資料集合時，冒泡排序與插入排序會是較好的做法，因為只需要跑一輪迴圈就可以排序完畢，但選擇排序依然要重複 n² 次步驟
  2. 這三種排序法的平均時間複雜度都是 O(n²)，因此是比較低效率的排序法，但它們的空間複雜度都是 O(1)，因為僅使用非常少量的變數去儲存一些暫時的值
  3. 在介紹插入排序法時就有提到，如果資料排序完之後，依然會有其他新的資料不斷加入，那麼插入排序法會是很適合的方式，只需要跑平均 n 次就可以完成排序
Sorting Algorithms
Algorithms
Nodejs

--

--

William Tsou

Written by William Tsou

4 Followers

紀錄在alphacamp學習的點點滴滴，以及邁向前端工程師的沿途風景

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams