C++ 四數排序：手寫冒泡排序網路 vs std::sort 最佳實踐

原始程式碼分析

// 原始：手寫的排序網路 (Sorting Network)
if (b < a) swap(b, a);
if (c < b) swap(c, b);
if (d < c) swap(d, c);
if (b < a) swap(b, a);
if (c < b) swap(c, b);
if (b < a) swap(b, a);

這是**固定大小 (n=4) 的排序網路**，比較次數固定為 6 次，屬於冒泡排序的展開版本。雖然對 n=4 最優，但：

• ❌ 程式碼冗長、難維護
• ❌ 擴展到 n=5 需重寫
• ❌ 可讀性差

現代 C++ 最佳實踐

方案一：std::array + std::sort (推薦通用)

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    std::array<int, 4> arr;
    for (int &x : arr) std::cin >> x;
    
    std::sort(arr.begin(), arr.end());
    
    for (int x : arr) std::cout << x << ' ';
    return 0;
}

• ✅ 標準庫、高度優化 (Introsort: 快排+堆排+插排)
• ✅ 任意容器、任意大小通用
• ✅ 可讀性最強

方案二：std::sort + 原始陣列 (相容舊碼)

int a[4];
for (int i = 0; i < 4; ++i) std::cin >> a[i];
std::sort(a, a + 4);  // 指針範圍
for (int i = 0; i < 4; ++i) std::cout << a[i] << ' ';

方案三：固定 4 元素的分支最優化 (極致效能)

// 來自 sorting network 研究的最優比較序列
void sort4(int &a, int &b, int &c, int &d) {
    if (a > b) std::swap(a, b);
    if (c > d) std::swap(c, d);
    if (a > c) std::swap(a, c);
    if (b > d) std::swap(b, d);
    if (b > c) std::swap(b, c);
    // 現在 a ≤ b ≤ c ≤ d
}

• ✅ 僅 5 次比較 (理論下界 log₂(4!) ≈ 4.58 → 5 次最優)
• ✅ 無循環、無函數調用、極易內聯
• ⚠️ 僅適用於固定 4 元素

效能對比 (10^8 次排序 4 個 int)

教學建議

• 🎓 **初學者**：用 std::sort，學會標準庫、泛型思維
• 🏗 **工程專案**：用 std::sort，維護性第一
• ⚡ **高頻熱點、固定小規模**：考慮排序網路或 std::array + std::sort 信任編譯器優化
• 🧠 **演算法課作業**：手寫冒泡/選擇/快排理解原理，但生產碼禁用

擴展：n=5, 6, 7 的最優排序網路

已知最優比較次數：n=5→9, n=6→12, n=7→16。超過 n=8 推薦直接用 std::sort，手寫網路收益遞減且維護成本指數級上升。