C 語言範例學習 04：八大排序、四大查找與 Dijkstra 演算法完整實作

C 語言範例學習 04：八大排序、四大查找與 Dijkstra 演算法完整實作

前言

演算法體現程式設計思維，思維指引演算法。複雜演算法多由簡單演算法演繹而來，重點在於從基礎演算法中體會設計思想。

4.1 簡單問題演算法

實例 111：任意次方後的最後三位

邏輯：直接計算 x^y 易溢位。每次迴圈乘完即取模 1000 保留後三位。若 x > 999 先取 x % 1000 結果不變。
代碼：

#include 
main() {
    int i, x, y, z = 1;
    printf("please input two numbers x and y(x^y):\n");
    scanf("%d%d", &x, &y);
    for (i = 1; i <= y; i++) z = z * x % 1000;
    printf("the last 3 digits of %d^%d is:%d\n", x, y, z);
}

4.2 八大排序演算法

排序分內部（記憶體）與外部（磁碟）。常用高效排序：合併、快速、堆排序（O(n log n)）。

1. 直接插入排序

哨兵 s[0] 避免資料後移丟失。

2. 希爾排序

分組插入排序，增量 d 逐步減半至 1，資料移動可跨越多元素。

3. 簡單選擇排序

每輪選最小值與首位交換。改進版：二元選擇排序，同輪定最小與最大，輪數減半。

4. 堆排序

樹形選擇排序，建立大根堆（完全二叉樹，父 ≥ 子），堆頂為最大值。不適合小資料量。

5. 冒泡排序

相鄰比較交換，小值上浮如氣泡。教學與考試常見。

6. 快速排序

基準值分三組（小、等、大），遞迴處理左右組。冒泡改進版，分組思想同希爾排序。

7. 合併排序

兩路合併，遞迴分解合併。綜合多種排序思想。

8. 基數排序

分配式排序，按關鍵字各位數值分配桶子。另闢蹊徑，非比較類排序。

4.3 四大查找演算法

1. 循序查找

遍歷比對，最直觀但最耗時。考試常考。

2. 二分查找

針對有序表，每次對半縮小範圍。極快但需有序。

3. 分塊查找

索引順序查找，建立有序索引表確定區塊，再區塊內循序查找。效率介於兩者間，適合多次查找。

4. 雜湊查找

透過雜湊函數計算儲存位置。處理衝突四法：開放定址（線性/二次探測）、鏈結法、再雜湊、公共溢出區。最複雜但平均 O(1)。

4.4 其他重要演算法

Dijkstra 最短路徑

圖譜搜尋，應用於網路路由、物流。維護集合 S（已定最短路徑頂點），每輪從 V-S 選距離最小者加入 S，更新鄰接點距離。

參考資源

• 八大排序演算法：CSDN
• 統治世界的十大演算法：36Kr