跳到主要內容
Jasonmel Online

演算法

同一個問題，不同的解題思路

主題 · 排序

排序

插入、合併、快速、堆積四種排序放在同一份資料上比較：誰快取決於資料原本長什麼樣子。

資料
演算法
元素數量
顯示
輸入

拿最後一個數字當基準，比它小的都搬到左邊，再分別排左右兩邊。

1/54
80111426324953657781091210111

左右捲動可保持標籤大小，也可以減少元素或選「顯示全部」。

正在比較搬動／寫入p：基準目前的位置不在目前範圍

lo／hi：分區範圍；i：寫入邊界；j：掃描位置；p：基準的位置。

標籤表示這一步使用的索引；陣列顯示寫入後的結果。

比較次數
0
寫入次數
0
全部跑完：比較
37
全部跑完：寫入
30

12 個數字，隨機。按播放或下一步開始。

亮起來的是這一步執行的程式碼
function insertionSort(a: number[]): void {
  for (let i = 1; i < a.length; i++) {
    for (let j = i; j > 0 && a[j] < a[j - 1]; j--) {
      [a[j], a[j - 1]] = [a[j - 1], a[j]];
    }
  }
}
 
function mergeSort(a: number[], lo = 0, hi = a.length - 1): void {
  if (hi <= lo) return;
  const mid = lo + Math.floor((hi - lo) / 2);
  mergeSort(a, lo, mid);
  mergeSort(a, mid + 1, hi);
  const left = a.slice(lo, mid + 1);
  const right = a.slice(mid + 1, hi + 1);
  let i = 0, j = 0, k = lo;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) {
      a[k++] = right[j++];
    } else {
      a[k++] = left[i++];
    }
  }
  while (i < left.length) a[k++] = left[i++];
  while (j < right.length) a[k++] = right[j++];
}
 
function quickSort(a: number[], lo = 0, hi = a.length - 1): void {
  const pending: [number, number][] = hi > lo ? [[lo, hi]] : [];
  while (pending.length) {
    const [lo, hi] = pending.pop()!;
    const pivot = a[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) {
      if (a[j] < pivot) {
        if (i !== j) [a[i], a[j]] = [a[j], a[i]];
        i++;
      }
    }
    if (i !== hi) [a[i], a[hi]] = [a[hi], a[i]];
    // LIFO: visit the left partition first, without recursive calls.
    if (i + 1 < hi) pending.push([i + 1, hi]);
    if (lo < i - 1) pending.push([lo, i - 1]);
  }
}
 
function heapSort(a: number[]): void {
  const n = a.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    siftDown(a, 0, end);
  }
}
 
function siftDown(a: number[], i: number, size: number): void {
  while (true) {
    const left = 2 * i + 1, right = left + 1;
    let largest = i;
    if (left < size && a[left] > a[largest]) largest = left;
    if (right < size && a[right] > a[largest]) largest = right;
    if (largest === i) return;
    [a[i], a[largest]] = [a[largest], a[i]];
    i = largest;
  }
}

模型假設與範圍

  • Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。
  • 比較只看數字鍵；身分字母用來觀察相同鍵的順序。寫入計原陣列的元素賦值，交換算兩次，跳過自己與自己的交換；暫存複製、堆疊和動畫快照另計。合併指標表示這一步使用的來源與目的位置。

什麼時候用

  • 絕大多數時候直接用語言內建的排序。自己挑演算法，是因為資料或環境有特殊條件。
  • 資料幾乎已經排好：插入排序只需要差不多 n 次比較。
  • 需要穩定（相同的鍵保持原本順序，例如先按日期、再按姓名排）：合併排序。
  • 記憶體很緊、不能另開陣列：堆積排序原地進行，而且最壞情況也是 n log n。
  • 平均最快：快速排序，但基準要隨機挑或三數取中。

和其他主題的關係

由這些組成
資料結構 · 堆積
延伸閱讀
二分搜尋

語言內建的版本

Array.prototype.sort · toSorted
操作寫法成本
原地排序（數字）nums.sort((x, y) => y - x)O(n log n)
排序成新陣列nums.toSorted((x, y) => x - y)O(n log n)
字串依語系排序x.localeCompare(y, "en")O(n log n)
多個鍵q.age - p.age || p.name.localeCompare(q.name)O(n log n)
const nums = [10, 9, 1];
[...nums].sort();                       // → [1, 10, 9]
nums.toSorted((x, y) => x - y);         // → [1, 9, 10]
nums;                                   // → [10, 9, 1]
nums.sort((x, y) => y - x);             // → [10, 9, 1]
 
["b", "a", "B"].sort();                 // → ["B", "a", "b"]
["b", "a", "B"].sort((x, y) => x.localeCompare(y, "en"));  // → ["a", "b", "B"]
 
const people = [
  { name: "Cy", age: 30 },
  { name: "Bob", age: 25 },
  { name: "Ann", age: 30 },
];
// Stable: people of equal age keep their original order.
people.toSorted((p, q) => p.age - q.age).map((p) => p.name);  // → ["Bob", "Cy", "Ann"]
// Age descending, then name ascending.
people.toSorted((p, q) => q.age - p.age || p.name.localeCompare(q.name)).map((p) => p.name);  // → ["Ann", "Cy", "Bob"]

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

  • 不給比較函式時，sort() 把元素轉成字串再比，數字會排錯。比較函式回傳負數代表 x 在前、正數代表 y 在前。
  • sort() 會改掉原陣列並回傳同一個陣列；toSorted()（ES2023，Node 20 起）回傳新的、原陣列不動。
  • 從 ES2019 起規格要求 sort 是穩定排序（V8 用 Timsort），所以「先按名字排，再按年齡排」會得到年齡相同時按名字排的結果。
  • 多個鍵可以用 || 串起來：前一個鍵比出來是 0（相等）才會看下一個。

時間與空間複雜度（Big O）

操作平均最差
插入排序
幾乎排好的資料只要 O(n)
O(n²)O(n²)
合併排序O(n log n)O(n log n)
快速排序
這裡拿最後一個當基準，已排序的輸入就是最差情況
O(n log n)O(n²)
堆積排序O(n log n)O(n log n)

空間：O(1) – O(n)，插入與堆積排序原地進行 O(1)；快速排序改用明確堆疊，平均 O(log n)、最差 O(n)，不依賴呼叫堆疊上限；合併排序暫存區 O(n)。圖中的身分與快照另計

Big O 實測：n 變大時步數怎麼長

數的是：比較次數，各跑一次

Big On = 250n = 500n = 1,000n = 2,000成長倍數：實測（理論）
插入排序（隨機）O(n²)16,10358,520244,053981,773×61 (×64)
合併排序（隨機）O(n log n)1,6923,8438,70719,437×11 (×11)
快速排序（隨機）O(n log n)2,4125,44211,18229,337×12 (×11)
堆積排序（隨機）O(n log n)3,2007,45516,86137,700×12 (×11)
快速排序（已排序）O(n²)31,125124,750499,5001,999,000×64 (×64)

n 變成 8 倍：n log n 的三種多了 11–12 倍，n² 的兩種多了 61–64 倍。插入排序在 n 小的時候其實很快，差距是 n 變大之後才拉開的。

和其他做法比

隨機已排序反序大量重複
插入排序244,053 / 486,116999 / 0499,500 / 999,000189,864 / 377,730
合併排序8,707 / 9,9765,044 / 9,9764,932 / 9,9767,935 / 9,976
快速排序11,182 / 8,396499,500 / 0499,500 / 1,000127,160 / 3,884
堆積排序16,861 / 18,16417,583 / 19,41615,965 / 16,63213,891 / 14,104

每格是「比較次數 / 寫入次數」：把 1,000 個數字交給上面同一份程式實際排一次數出來的（隨機與大量重複用固定種子）。交換算兩次寫入。

真實世界裡的它

  • V8（JavaScript）、Python 與 Java 的物件排序都用 TimSort：合併排序加上插入排序，專門吃「已經部分排好」的資料。
  • C++ 的 std::sort 是 introsort：快速排序，遞迴太深就換堆積排序，切到很小段就換插入排序。
  • 資料庫的 ORDER BY 放不進記憶體時用外部合併排序：分批排好寫到磁碟，再一路合併回來。

取捨與陷阱

  • 快速排序拿最後一個當基準，遇到已排序的資料就退化：1,000 筆要比較 499,500 次，正好是 n(n−1)/2。實務上用隨機基準避開。
  • 大量重複值也會拖慢這種切法：等於基準的值全擠到同一邊。三路切分（小於／等於／大於）可以解決。
  • 展示的快速排序用明確堆疊保存尚未處理的分區，不用遞迴，所以 Python 的預設遞迴上限不會限制輸入筆數。但最差情況的 O(n²) 比較成本仍然存在。
  • 比較次數不是全部：合併排序要一個一樣大的暫存陣列；插入排序的寫入次數可能比比較還多。
  • JavaScript 的 [10, 9, 1].sort() 預設照字串排，結果是 [1, 10, 9]；數字要傳 (a, b) => a - b。

LeetCode 練習