跳至主要内容

Sorting

Sorting Algorithm（排序演算法）指的是「把一堆亂七八糟的資料，依照大小順序重新排列」的方法。

處理的問題包括：

  • 數字從小排到大
  • 名字按首字母排序
  • 根據電影上映年份排序
  • 根據電影的票房多寡排序

在學習排序時，非常推薦利用視覺化演算法輔助學習。

常見的排序演算法主要會看時間複雜度 (Big O)，分成兩大類別：

基礎排序法 O(N^2)​

這組演算法的特色是程式碼非常好寫、直覺，但是當資料量變大時，速度會變得很慢。平均時間複雜度為 O(N^2)，適合拿來理解排序的基本邏輯。

Bubble Sort​

從頭開始，兩兩比較相鄰的數字。如果前面的比後面大就交換，像水底的氣泡一樣把最大的數字一路「推」到最後面。

一回的比對情況如下：

[ 5, 3, 4, 1, 2 ]
   \ /
[ 3, 5, 4, 1, 2 ]
      \ /
[ 3, 4, 5, 1, 2 ]
         \ /
[ 3, 4, 1, 5, 2 ]
            \ /
[ 3, 4, 1, 2, 5 ]

當一回結束之後，最後面的 5 代表是已經排序過的最大數字，所以下一回就不用再拿 5 和其他數字比對，因此每一回都會減少一次比對，也就是比對範圍會往 Array 的前面推一點。

function bubbleSort(arr) {
  let i = arr.length - 1;
  while (i > 0) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
    i--;
  }
  return arr;
}

Selection Sort​

在整串數字中找出最小的那一個，把它和第一個位置的數字交換。接著在剩下的數字裡找第二小的，放第二個位置，依此類推。

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[min]) min = j;
    }
    if (min !== i) {
        [arr[i], arr[min]] = [arr[min], arr[i]];
    }
  }
  return arr;
}

Insertion Sort​

就像玩撲克牌理牌一樣。每次拿到一張新牌，就由右往左看，把它「插入」到已經排好序的正確位置。

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i];
    let cursor = i - 1;
    while (cursor >= 0 && arr[cursor] > currentVal) {
      arr[cursor + 1] = arr[cursor];
      cursor--;
    }
    arr[cursor + 1] = currentVal;
  }
  return arr;
}

進階排序法 O(N log N)​

這組演算法利用了**「Divide and Conquer」**的策略（把大問題拆成小問題各自解決，最後再合併），速度極快，時間複雜度為 O(N log N)，是現代電腦處理大量資料的主力。

Quick Sort​

在 Array 裡隨便選一個數字當作 「基準點 (Pivot)」。比它小的全部丟到左邊，比它大的全部丟到右邊。

實作主要會分成兩部分，分別是

  • 切分 (Partitioning)
  • 遞迴切分 (Recursion)

Partitioning​

這邊用的方式稱為 Lomuto Partition，做法非常直覺，就像是 「用一個慢指針和一個快指針，把整個 Array 掃描一遍」。

// JavaScript

function partition(arr, start, end) {
    let pivot = arr[end];
    let i = start;
    
    for (let j = start; j < end; j++) {
        if (arr[j] <= pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]]; // 交換位置
            i++;
        }
    }
    
    // 將基準值換到正確的位置
    [arr[i], arr[end]] = [arr[end], arr[i]];
    return i;
}

此外，還有 Hoare partition，有興趣歡迎自己去搜尋資料了解。

Recursion​

針對 Pivot 左邊那堆比較小的數字，以及右邊那堆比較大的數字，各自重複 Partition，直到每堆資料都只剩下一個數字為止

// JavaScript

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIdx = partition(arr, left, right);
    quickSort(arr, left, pivotIdx - 1); // 排序左邊
    quickSort(arr, pivotIdx + 1, right); // 排序右邊
  }
  return arr;
}

選擇 Pivot​

值得注意的是，如果 Pivot 剛好選到最大或最小，時間複雜度會是最壞情況 O(N^2)。

為了避免這種情況，一般採用以下方法：

  • 隨機選取 (Randomized Quick Sort)：每次都用亂數隨機選一個數字當 Pivot，這樣幾乎不可能每次都選到最差的數字。
  • 三數取中法 (Median-of-three)：同時看「最左邊、最右邊、中間」這三個數，挑大小在正中間的那個當 Pivot，確保切分出來的左右兩邊相對平衡。

Quickselect​

Quickselect 是一種用來在未排序的陣列中，尋找「第 k 小」或「第 k 大」元素的超高效演算法。

核心概念與 Quick Sort 一樣，可直接參考 Quickselect 頁面。

Merge Sort​

直接把 Array 從中間「切一半、再切一半」，直到每組都只剩一個數字。接著再兩兩一組，一邊比較大小、一邊「合併」回原本的大 Array。缺點是合併時需要額外的記憶體空間。

Merge Sort 通常分兩部分：

  • Merging Arrays
  • Merge Sort

Merging Arrays​

負責將兩個已經排好序的 Array，合併成一個更大的 sorted Array。

function mergeArray(arr1, arr2) {
  let result = [];
  
  // p1 和 p2 分別對應到 arr1 和 arr2 裡的 index
  let p1 = 0;
  let p2 = 0; 
  
  while (p1 < arr1.length && p2 < arr2.length) {
    // 如果 arr1 的值小於 arr2 的值，則將 arr1 值放進 result
    // 相反的情況，放入 arr2 的值，兩值一樣則放哪個都可
    if (arr1[p1] < arr2[p2]) {
      result.push(arr1[p1]);
      p1++
    } else {
      result.push(arr2[p2]);
      p2++
    }
  }

  // 直接合併剩下的內容
  if (p1 < arr1.length) {
    result = result.concat(arr1.slice(p1));
  } 
  if (p2 < arr2.length) {
    result = result.concat(arr2.slice(p2));
  }
  return result;
}

Merge Sort​

負責切分 Array 再呼叫 mergeArray 合併，分為兩種做法

  • Top-Down (Recursion)
  • Bottom-Up (Iteration)
Top-Down (Recursion)​
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  let mid = Math.ceil(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  return mergeArray(left, right);
}
Bottom-Up (Iteration)​
function mergeSort(arr) {
  const { length: mainL } = arr;
  let workArr, leftArr, rightArr;
  
  // width 代表每次切成小單位 array 的長度
  for (let width = 1; width < mainL; width = width * 2) {
    workArr = [];
    for (let leftStart = 0; leftStart < mainL; leftStart += width * 2) {
      // 在該 width 下切割的小 array 分別 merge (and sort)
      leftArr = arr.slice(leftStart, leftStart + width);
      rightArr = arr.slice(leftStart + width, leftStart + 2 * width);
      workArr = workArr.concat(mergeArray(leftArr, rightArr));
    }
    arr = workArr;
  }
  return arr;
}

複雜度​

不管 Array 是已經排序好或是順序雜亂的情形，Merge Sort 的 Time Complexity 都是 O(n log n)。

其中，O(n log n) 又可分為：

  • 不斷對半切割成小 Array：O(log n)
  • 比較並合併 n 個 Array：O(n)

至於 Space Complexity 為 O(n)，因為分割成 n 個小 Array。

Heap Sort​

把所有資料建立成一個 Binary Heap，每次都從 Root 拿出最大（或最小）的數字，直到全部拿完，可直接參考 Heap。

最後於 更新