[algorithms] Sorting 排序演算法

視覺化概覽

flowchart TD
    A["需要排序"] --> B{"資料量大小？"}
    B -->|"小 < 50"| C{"近乎有序？"}
    C -->|"是"| D["Insertion Sort\nO(n) 最佳"]
    C -->|"否"| E["Insertion Sort\n簡單、常數因子小"]
    B -->|"大"| F{"需要穩定排序？"}
    F -->|"是"| G["Merge Sort\nO(n log n) 穩定"]
    F -->|"否"| H{"記憶體受限？"}
    H -->|"是"| I["Quick Sort\n原地排序 O(log n) 空間"]
    H -->|"否"| J["Quick Sort\n實務上最快"]

💡 白話版：排序就像整理一副撲克牌。你可以一張一張插到正確位置（Insertion Sort），也可以先分成兩堆再合併（Merge Sort）。

概覽

演算法	時間(平均)	時間(最差)	空間	穩定性
Bubble Sort	O(n²)	O(n²)	O(1)	穩定
Selection Sort	O(n²)	O(n²)	O(1)	不穩定
Insertion Sort	O(n²)	O(n²)	O(1)	穩定
Merge Sort	O(n log n)	O(n log n)	O(n)	穩定
Quick Sort	O(n log n)	O(n²)	O(log n)	不穩定

穩定性：相同值的元素，排序後相對順序是否不變。

Bubble Sort 氣泡排序

像氣泡一樣，大的往上浮。

[64, 34, 25, 12]
 比較相鄰，大的往後推

第一輪：64 和 34 交換 → [34, 64, 25, 12]
       64 和 25 交換 → [34, 25, 64, 12]
       64 和 12 交換 → [34, 25, 12, 64] ← 最大的到位

第二輪：[25, 34, 12, 64]
       [25, 12, 34, 64] ← 第二大到位

第三輪：[12, 25, 34, 64] ← 完成！

Selection Sort 選擇排序

每次選最小的放前面。

[64, 34, 25, 12]

第一輪：找最小 12 → [12, 34, 25, 64]
第二輪：找最小 25 → [12, 25, 34, 64]
第三輪：找最小 34 → [12, 25, 34, 64] ← 完成！

Insertion Sort 插入排序

像撲克牌一樣，一張一張插入正確位置。

[64, 34, 25, 12]
 ──  已排序 | 未排序

[64] | 34, 25, 12   → 插入 34 → [34, 64]
[34, 64] | 25, 12   → 插入 25 → [25, 34, 64]
[25, 34, 64] | 12   → 插入 12 → [12, 25, 34, 64]

特點：近乎有序時特別快！

Merge Sort 合併排序

分而治之：分割、排序、合併。

[64, 34, 25, 12]
      ↓ 分割
[64, 34]  [25, 12]
    ↓         ↓
[64] [34]  [25] [12]
    ↓         ↓ 合併
[34, 64]  [12, 25]
      ↓ 合併
[12, 25, 34, 64]

合併過程

合併 [34, 64] 和 [12, 25]:

[34, 64]  [12, 25]
  ↑         ↑
  i         j

比較 34 和 12 → 取 12 → [12]
比較 34 和 25 → 取 25 → [12, 25]
取 34            → [12, 25, 34]
取 64            → [12, 25, 34, 64]

Quick Sort 快速排序

選一個 pivot，小的放左邊，大的放右邊。

[64, 34, 25, 12, 22, 90]
                     ↑ pivot = 90

小於 90 放左邊：[64, 34, 25, 12, 22]
大於 90 放右邊：[]
結果：[64, 34, 25, 12, 22, 90]

對左邊遞迴：pivot = 22
小於 22：[12]
大於 22：[64, 34, 25]
結果：[12, 22, 64, 34, 25, 90]

繼續遞迴...

Partition 過程

[64, 34, 25, 12, 22, 90] pivot=90
  i                       j

arr[j]=64 < 90 → i++, swap → [64, ...]
arr[j]=34 < 90 → i++, swap → [64, 34, ...]
...所有都小於 90
最後 swap pivot → [..., 90]

如何選擇？

場景	推薦	原因
小資料量 (< 50)	Insertion	常數因子小，簡單
近乎有序	Insertion	最佳 O(n)
一般情況	Quick Sort	實務上最快
需要穩定排序	Merge Sort	保持相對順序
記憶體受限	Quick Sort	原地排序 O(log n)

為什麼 Quick Sort 實務上最快？

雖然最差是 O(n²)，但：

1. 平均 O(n log n)
2. 原地排序，cache 友好
3. 常數因子小

避免最差情況：隨機選 pivot 或取三數中位數。

相關檔案

• Java 實作：Sorting.java
• 視覺化：sorting.html