Sorting

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

處理的問題包括：

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

白話理解

想像整理一手撲克牌：可像 Insertion Sort 一樣，每拿到一張新牌就插入手中已排好序的正確位置；也可以像 Merge Sort 一樣，先把牌分成兩堆各自排好序，再合併成一手排序好的牌。

排序演算法的差別，就在於「怎麼把亂序的資料，一步步變成有順序」的策略不同。

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

常見的排序演算法主要會看時間複雜度 (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 的前面推一點。

Python

def bubble_sort(arr):
    i = len(arr) - 1
    while i > 0:
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        i -= 1
    return arr

JavaScript

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;
}

Java

class Solution {
    public static int[] bubbleSort(int[] arr) {
        int i = arr.length - 1;
        while (i > 0) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp;
                }
            }
            i--;
        }
        return arr;
    }
}

Selection Sort

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

Python

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

JavaScript

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;
}

Java

class Solution {
    public static int[] selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) min = j;
            }
            if (min != i) {
                int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp;
            }
        }
        return arr;
    }
}

以 [5, 3, 4, 1, 2] 為例，逐步拆解：

[ 5, 3, 4, 1, 2 ]   i=0，剩餘範圍找到最小值 1（在 index 3），與 index 0 交換
[ 1, 3, 4, 5, 2 ]   i=1，剩餘範圍找到最小值 2（在 index 4），與 index 1 交換
[ 1, 2, 4, 5, 3 ]   i=2，剩餘範圍找到最小值 3（在 index 4），與 index 2 交換
[ 1, 2, 3, 5, 4 ]   i=3，剩餘範圍找到最小值 4（在 index 4），與 index 3 交換
[ 1, 2, 3, 4, 5 ]   i=4，只剩一個元素，排序完成

和 Bubble Sort 相反，Selection Sort 是「每一輪把確定的最小值往前排好」，而不是把最大值往後推。

Insertion Sort

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

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        current_val = arr[i]
        cursor = i - 1
        while cursor >= 0 and arr[cursor] > current_val:
            arr[cursor + 1] = arr[cursor]
            cursor -= 1
        arr[cursor + 1] = current_val
    return arr

JavaScript

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;
}

Java

class Solution {
    public static int[] insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int currentVal = arr[i];
            int cursor = i - 1;
            while (cursor >= 0 && arr[cursor] > currentVal) {
                arr[cursor + 1] = arr[cursor];
                cursor--;
            }
            arr[cursor + 1] = currentVal;
        }
        return arr;
    }
}

以 [5, 3, 4, 1, 2] 為例，逐步拆解（| 代表「目前已排序好的區域」與「還沒處理的區域」的分界）：

[ 5 | 3, 4, 1, 2 ]   起始狀態，只有第一個元素算是「已排序」
[ 3, 5 | 4, 1, 2 ]   拿出 3，往左比對，比 5 小就把 5 往右擠，3 插入最前面
[ 3, 4, 5 | 1, 2 ]   拿出 4，往左比對，比 5 小、比 3 大，插入在 3 和 5 之間
[ 1, 3, 4, 5 | 2 ]   拿出 1，往左一路比對到最前面，插入最前面
[ 1, 2, 3, 4, 5 ]   拿出 2，往左比對，插入在 1 和 3 之間，排序完成

Insertion Sort 很像玩撲克牌整理手牌的直覺動作，資料量小或「幾乎已經排序好」時效率特別好。

進階排序法 O(N log N)

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

Quick Sort

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

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

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

Partitioning

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

Python

def partition(arr, start, end):
    pivot = arr[end]
    i = start

    for j in range(start, end):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]  # 交換位置
            i += 1

    # 將基準值換到正確的位置
    arr[i], arr[end] = arr[end], arr[i]
    return i

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;
}

Java

class Solution {
    public static int partition(int[] arr, int start, int end) {
        int pivot = arr[end];
        int i = start;

        for (int j = start; j < end; j++) {
            if (arr[j] <= pivot) {
                int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; // 交換位置
                i++;
            }
        }

        // 將基準值換到正確的位置
        int tmp = arr[i]; arr[i] = arr[end]; arr[end] = tmp;
        return i;
    }
}

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

Recursion

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

Python

def quick_sort(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    if left < right:
        pivot_idx = partition(arr, left, right)
        quick_sort(arr, left, pivot_idx - 1)  # 排序左邊
        quick_sort(arr, pivot_idx + 1, right)  # 排序右邊
    return arr

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;
}

Java

class Solution {
    public static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIdx = partition(arr, left, right);
            quickSort(arr, left, pivotIdx - 1);  // 排序左邊
            quickSort(arr, pivotIdx + 1, right); // 排序右邊
        }
        return arr;
    }

    public static int[] quickSort(int[] arr) {
        return quickSort(arr, 0, arr.length - 1);
    }
}

選擇 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。

Python

def merge_array(arr1, arr2):
    result = []

    # p1 和 p2 分別對應到 arr1 和 arr2 裡的 index
    p1 = 0
    p2 = 0

    while p1 < len(arr1) and p2 < len(arr2):
        # 如果 arr1 的值小於 arr2 的值，則將 arr1 值放進 result
        # 相反的情況，放入 arr2 的值，兩值一樣則放哪個都可
        if arr1[p1] < arr2[p2]:
            result.append(arr1[p1])
            p1 += 1
        else:
            result.append(arr2[p2])
            p2 += 1

    # 直接合併剩下的內容
    result.extend(arr1[p1:])
    result.extend(arr2[p2:])
    return result

JavaScript

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;
}

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public static List<Integer> mergeArray(List<Integer> arr1, List<Integer> arr2) {
        List<Integer> result = new ArrayList<>();

        // p1 和 p2 分別對應到 arr1 和 arr2 裡的 index
        int p1 = 0;
        int p2 = 0;

        while (p1 < arr1.size() && p2 < arr2.size()) {
            // 如果 arr1 的值小於 arr2 的值，則將 arr1 值放進 result
            // 相反的情況，放入 arr2 的值，兩值一樣則放哪個都可
            if (arr1.get(p1) < arr2.get(p2)) {
                result.add(arr1.get(p1));
                p1++;
            } else {
                result.add(arr2.get(p2));
                p2++;
            }
        }

        // 直接合併剩下的內容
        result.addAll(arr1.subList(p1, arr1.size()));
        result.addAll(arr2.subList(p2, arr2.size()));
        return result;
    }
}

Merge Sort

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

• Top-Down (Recursion)
• Bottom-Up (Iteration)

Top-Down (Recursion)

Python

import math

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = math.ceil(len(arr) / 2)
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge_array(left, right)

JavaScript

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);
}

Java

import java.util.List;

class Solution {
    public static List<Integer> mergeSort(List<Integer> arr) {
        if (arr.size() <= 1) return arr;
        int mid = (int) Math.ceil(arr.size() / 2.0);
        List<Integer> left = mergeSort(arr.subList(0, mid));
        List<Integer> right = mergeSort(arr.subList(mid, arr.size()));
        return mergeArray(left, right);
    }
}

Bottom-Up (Iteration)

Python

def merge_sort(arr):
    main_l = len(arr)

    # width 代表每次切成小單位 array 的長度
    width = 1
    while width < main_l:
        work_arr = []
        for left_start in range(0, main_l, width * 2):
            # 在該 width 下切割的小 array 分別 merge (and sort)
            left_arr = arr[left_start:left_start + width]
            right_arr = arr[left_start + width:left_start + 2 * width]
            work_arr.extend(merge_array(left_arr, right_arr))
        arr = work_arr
        width *= 2
    return arr

JavaScript

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;
}

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public static List<Integer> mergeSort(List<Integer> arr) {
        int mainL = arr.size();

        // width 代表每次切成小單位 array 的長度
        for (int width = 1; width < mainL; width *= 2) {
            List<Integer> workArr = new ArrayList<>();
            for (int leftStart = 0; leftStart < mainL; leftStart += width * 2) {
                // 在該 width 下切割的小 array 分別 merge (and sort)
                List<Integer> leftArr = arr.subList(leftStart, Math.min(leftStart + width, mainL));
                List<Integer> rightArr = arr.subList(Math.min(leftStart + width, mainL), Math.min(leftStart + 2 * width, mainL));
                workArr.addAll(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。

總複雜度整理

排序法	平均時間複雜度	最壞時間複雜度	空間複雜度	是否穩定排序
Bubble Sort	O(n^2)	O(n^2)	O(1)	是
Selection Sort	O(n^2)	O(n^2)	O(1)	否
Insertion Sort	O(n^2)	O(n^2)	O(1)	是
Quick Sort	O(n log n)	O(n^2)	O(log n)	否
Merge Sort	O(n log n)	O(n log n)	O(n)	是
Heap Sort	O(n log n)	O(n log n)	O(1)	否

什麼是「穩定排序（Stable Sort）」？

如果兩個元素的值相同，穩定排序能保證它們在排序後相對前後順序不變。
例如依照「分數」幫一群學生排序，如果兩位同學分數相同，穩定排序會保持他們原本在名單中的先後順序，這在某些需要「多欄位排序」的情境（先按分數排、再按姓名排）非常重要。

新手該怎麼選？

剛開始學習時，不需要死記每個排序法的程式碼，比較重要的是先記住：

• 資料量小、或程式碼要簡單好懂：Insertion Sort（幾乎排序好的資料效率也很好）。
• 資料量大、追求平均效能：Quick Sort（各語言內建排序函式常見的實作基礎）。
• 需要「穩定排序」，或不想承擔最壞情況風險：Merge Sort。
• 面試被問到 Sorting，最常從 Quick Sort 與 Merge Sort 的原理與差異開始準備即可。

適用情況

• 資料量小或幾乎已排序：使用 Insertion Sort，程式碼簡單、常數項小，實務上效率反而不輸進階排序法。
• 一般情境下的通用排序：使用 Quick Sort，平均效能佳，是各語言內建排序函式常見的實作基礎。
• 需要穩定排序（多欄位排序）：使用 Merge Sort，例如先按分數排序、分數相同再按姓名排序時，必須保證同分的相對順序不變。
• 只需要「第 k 大 / 第 k 小」，不需要完整排序：不需要真的排序整個陣列，改用 Quickselect 通常更快。
• 需要動態、即時取得極值：不適合每次重新排序，改用 Heap 維護極值會更有效率。

常見誤區

• 誤以為平均時間複雜度就是保證值：Quick Sort 平均是 O(n log n)，但如果每次都選到最差的 Pivot（例如陣列已排序、又固定選最後一個當 Pivot），最壞情況會退化成 O(n^2)，實務上常用隨機選取或三數取中法降低風險。
• 忽略「穩定排序」的重要性：如果題目需要多欄位排序（先按 A 排、再按 B 排），選到不穩定的排序法（如 Quick Sort、Selection Sort）可能會打亂原本已經排好的順序，導致結果錯誤。
• Merge Sort 忘記額外的空間成本：Merge Sort 穩定且時間複雜度有保證，但合併時需要額外的 O(n) 空間，在記憶體受限的情境下需要納入考量。
• 看到「排序」就直接排整個陣列：如果題目只需要極值或第 k 大 / 小的元素，把整個陣列排序（O(n log n)）往往不是最快的做法，Quickselect 或 Heap 通常更合適。