Iterative sorting algorithms

•6 min read
algorithmsorting
Back

Bubble sort

將陣列中相鄰元素兩兩做比較，若第一個元素大於第二個元素，兩者順序互換，依序重複此步驟到最後兩個元素，可以確保最大元素被放在陣列的尾端

略過已經排序完的尾端元素，重複上述步驟，即為泡沫排序法，時間複雜度為 O(n²)

以 [3, 7, 5, 1] 為例：

  1. [3, 7, 5, 1] 從 index 0 開始
    1. 3 小於 ７，略過
    2. 7 大於 5，互換 [3, 5, 7, 1]
    3. 7 大於 1，互換 [3, 5, 1, 7]
    4. 有換過順序，繼續下一輪
  2. [3, 5, 1, 7] 從 index 0 開始，忽略已排序元素 (7 為已排序)
    1. 3 小於 5，略過
    2. 5 大於 1，互換 [3, 1, 5, 7]
    3. 有換過順序，繼續下一輪
  3. [3, 1, 5, 7] (5, 7 為已排序)
    1. 3 大於 1，互換 [1, 3, 5, 7]
    2. 有換過順序，繼續下一輪
  4. [1, 3, 5, 7] (3, 5, 7 為已排序)
    1. 沒有比對元素，即完成排序
function bubbleSort(nums) {
  let counter = 0;
  let swapped = false;
 
  do {
    swapped = false;
    counter += 1;
 
    for (let i = 0; i < nums.length - counter; i++) {
      if (nums[i] > nums[i + 1]) {
        const lesser = nums[i + 1];
        nums[i + 1] = nums[i];
        nums[i] = lesser;
        swapped = true;
      }
    }
  } while(swapped);
 
  return nums;
}
 
bubbleSort([3, 7, 5, 1]);

Insertion sort

取自維基百科

它的工作原理是通過構建有序序列，對於未排序資料，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用 in-place 排序（即只需用到 O(1) 的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

插入排序法的時間複雜度為 O(n²)

下方程式碼以 [3, 7, 5, 1] 為例，先將 3 視為已排序的部分：

  1. 從 index 1，依序向左掃瞄
    1. 7 大於 3，插入的 index 為 1 [3, 7, 5, 1]
  2. 從 index 2 ，依序向左掃瞄
    1. 5 小於 7，將 7 向右移 [3, 7, 7, 1]
    2. 5 大於 3，插入位置 3 的右側，即為 index 1 [3, 5, 7, 1]
  3. 從 index 3 ，依序向左掃描
    1. 1 小於 7，7 向右移 [3, 5, 7, 7]
    2. 1 小於 5，5 向右移 [3, 5, 5, 7]
    3. 1 小於 3，3 向右移 [3, 3, 5, 7]
    4. 找到 1 的插入位置為 index 0 [1, 3, 5, 7]
export default function insertionSort(arr: Array<number>): Array<number> {
  // 從 index 1 開始
  for (let i = 1; i < arr.length; i++) {
    // 暫存待排序的元素
    const numberToInsert = arr[i];
    // 紀錄插入排序的指標
    let j = i - 1;
    // 依序往前比對
    while (j >= 0 && arr[j] > numberToInsert) {
      // 先將元素往右移
      arr[j + 1] = arr[j];
      // 更新插入排序指標
      j--;
    }
    // 將待排序元素更新至插入排序指標
    arr[j + 1] = numberToInsert;
  }
  return arr;
}

Selection sort

取自維基百科

在未排序的序列中找到最小元素，放到已排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢

選擇排序法的時間複雜度為 О(n²)

以 [3, 5, 7, 1] 為例：

  1. 從 index 0 開始，找出最小值
    1. 3 小於 5，最小值為 3
    2. 3 小於 7，最小值為 3
    3. 3 大於 1，最小值為 1
    4. 將 1 放到最左側 [1, 3, 5, 7]。將 1 視為已排序序列
  2. 在剩餘元素 [3, 5, 7] 中找出最小值，放到已排序序列的右側
    1. 3 小於 5，最小值為 3
    2. 3 小於 7，最小值為 3
    3. 將 3 放到已排序序列的右側 (index 相同可以忽略)
  3. 在剩餘元素 [5, 7] 中找出最小值，放到已排序序列的右側
    1. 5 小於 7，最小值為 7
    2. 將 5 放到已排序序列的右側 (index 相同可以忽略)

實作的範例程式碼如下：

indexOfMin 表示已排序序列的末尾位置，如果與未排序序列最小值 index 相同，則可忽略

比較該位置與已排序序列末尾位置，若不相同則將兩者進行替換

function selectionSort(nums) {
  for (let i = 0; i < nums.length - 1; i++) {
    let indexOfMin = i;
 
    for(let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[indexOfMin]) {
        indexOfMin = j;
      }
    }
 
    if (i !== indexOfMin) {
      const lesser = nums[indexOfMin];
      nums[indexOfMin] = nums[i];
      nums[i] = lesser;
    }
  }
  
  return nums;
}
 
selectionSort([3, 7, 5, 1]);

Reference