演算法圖鑑
演算法 · 9 個細項

Sorting排序

排序是最常被呼叫的演算法，也是理解分治、穩定性、下界證明的最佳教材。學完你會知道語言內建的 sort 為什麼那樣設計，以及什麼時候可以突破 n log n。

為什麼要學 Sorting

現實中的應用
電商與排行榜

依價格、評分、銷量排列商品，或每分鐘更新的遊戲排行榜。資料一大，O(n²) 和 O(n log n) 的差距就是能不能即時回應。

→ 對應課程：Quick Sort
資料庫的 ORDER BY 與外部排序

資料庫背後就是排序演算法；記憶體放不下時用的是合併排序的外部版本，一次只讀一塊進來。

→ 對應課程：Merge Sort
排序是很多演算法的前置

二分搜尋、去除重複、合併時間區間、找中位數，都先假設資料有序。排好序，後面的問題會突然變簡單。

→ 對應課程：Insertion Sort
整數資料的特殊情況

年齡、分數、郵遞區號這種範圍固定的整數，不用比較也能排，這就是計數排序與基數排序能突破 n log n 的原因。

→ 對應課程：Counting Sort

細項

9 篇
#演算法難度
01Bubble Sort 氣泡排序相鄰交換，最直覺但最慢用在：教學用，理解「相鄰交換」與穩定性02Selection Sort 選擇排序每輪選最小的放到前面用在：交換次數最少，寫入昂貴的場合03Insertion Sort 插入排序像整理撲克牌，近乎有序時 O(n)用在：小陣列或幾乎有序的資料，內建排序在小段落會切換用它04Merge Sort 合併排序切半、各自排、合併，穩定用在：外部排序大檔案、鏈結串列排序、逆序對05Quick Sort 快速排序選 pivot 分兩邊，平均最快用在：大多數語言內建排序的基礎，Quick Select 找第 k 大06Heap Sort 堆積排序先 heapify 再逐個取出，原地用在：記憶體受限又要保證 n log n 的場合07Counting Sort 計數排序數每個值出現幾次，不比較用在：範圍小的整數，例如成績、年齡分布08Radix / Bucket Sort 基數與桶排序按位數或按區間分桶用在：固定長度的整數或字串，例如電話號碼09Sorting Lower Bound 比較排序下界用決策樹證明比較排序至少 Ω(n log n)用在：知道什麼時候不可能更快