C 語言經典算法模板庫：持續更新的代碼筆記

編輯：關於C語言

C 語言經典算法模板庫：持續更新的代碼筆記

收錄高頻算法的標準 C 實現，註釋詳盡，適合面試複習、競程模板、工程速查。所有代碼經測試可直接編譯運行。

1. 最大子序列和 — Kadane 算法 O(N)

int MaxSubsequenceSum(const int A[], int N) {
    int ThisSum = 0, MaxSum = 0;
    for (int j = 0; j < N; j++) {
        ThisSum += A[j];
        if (ThisSum > MaxSum) MaxSum = ThisSum;
        else if (ThisSum < 0) ThisSum = 0; // 拋棄負前綴
    }
    return MaxSum; // 全負數組返回 0，若需返回最大負值需微調
}

核心洞察：負數前綴不可能是最優解一部分，果斷歸零重啟累加。

2. 二分查找 — 有序數組 O(log N)

int BinarySearch(const int A[], int X, int N) {
    int Low = 0, High = N - 1;
    while (Low <= High) {
        int Mid = Low + (High - Low) / 2; // 防溢出寫法
        if (A[Mid] < X) Low = Mid + 1;
        else if (A[Mid] > X) High = Mid - 1;
        else return Mid; // 找到
    }
    return -1; // 不存在
}

3. 最大公約數 — 歐幾里得算法 O(log min(M,N))

unsigned int Gcd(unsigned int M, unsigned int N) {
    unsigned int Rem;
    while (N != 0) {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return M;
}

遞歸版：return N ? Gcd(N, M%N) : M; 同樣優雅。

4. 快速冪 — 分治遞歸 O(log N)

long int Pow(long int x, int N) {
    if (N == 0) return 1;   // x^0 = 1
    if (N == 1) return x;
    if (N % 2 == 0) return Pow(x * x, N / 2);
    else return Pow(x * x, N / 2) * x;
}

迭代版（無遞歸開銷）：

long int PowIter(long int x, int N) {
    long int res = 1;
    while (N) {
        if (N & 1) res *= x;
        x *= x;
        N >>= 1;
    }
    return res;
}

5. 排序算法對比

算法	平均時間	最壞	空間	穩定	備註
冒泡排序	O(N²)	O(N²)	O(1)	✓	教學用，實戰慎用
選擇排序	O(N²)	O(N²)	O(1)	✗	交換次數少於冒泡
快速排序	O(N log N)	O(N²)	O(log N)	✗	工程首選，需隨機化樞軸
歸並排序	O(N log N)	O(N log N)	O(N)	✓	外部排序/鏈表首選
堆排序	O(N log N)	O(N log N)	O(1)	✗	原地、保證上界

冒泡排序模板

void BubbleSort(int a[], int len) {
    for (int i = 0; i < len - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < len - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break; // 已有序提前退出
    }
}

選擇排序模板

void SelectSort(int a[], int len) {
    for (int i = 0; i < len - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < len; j++)
            if (a[j] < a[minIdx]) minIdx = j;
        if (minIdx != i) {
            int tmp = a[i]; a[i] = a[minIdx]; a[minIdx] = tmp;
        }
    }
}

持續更新中… 歡迎指正錯誤、補充邊界情況或貢獻新算法（如 KMP、Trie、並查集、線段樹等）。