C/C++ 學院 0907 —— 象棋五子棋編譯錯誤排查與經典查找排序算法實現集錦

本文記錄 MFC 專案編譯常見錯誤（MBCS/Unicode、PDB 格式不兼容）解決方案，並整理了插值查找、斐波那契查找、插入排序、堆排序、二路插入、非遞歸快排、歸併排序、紅黑樹、計數/基數/桶/希爾/選擇/冒泡/快速排序等 13 種算法的 C++ 完整實現代碼。

一、MFC 專案編譯錯誤速查

二、查找算法

1. 插值查找

mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]);

適用於均勻分佈有序數組，平均 O(log log n)，最差 O(n)。

2. 斐波那契查找

利用黃金分割點 F[k-1]-1，僅含加減法，無除法，平均性能優於二分。

三、排序算法核心代碼片段

1. 插入排序

for (int i = 1; i < n; ++i)
    for (int j = 0; j < i; ++j)
        if (a[i] < a[j]) { /* 後移插入 */ }

2. 堆排序

void maxHeapify(int* a, int n, int i) { /* 向下篩選 */ }
void buildMaxHeap(int* a, int n) { for (int i = (n-2)/2; i >= 0; --i) maxHeapify(a,n,i); }
void heapSort(int* a, int n) { buildMaxHeap(a,n); for (int i=n-1;i>0;--i){ swap(a[0],a[i]); maxHeapify(a,i,0); } }

3. 非遞歸快速排序（棧模擬）

stack> st; st.push({0,n-1});
while (!st.empty()) {
    auto [l,r] = st.top(); st.pop();
    int m = partition(l,r);
    if (l < m-1) st.push({l,m-1});
    if (m+1 < r) st.push({m+1,r});
}

4. 歸併排序

void merge(int* a, int l, int mid, int r) {
    for (int i=l, j=mid+1, k=l; k<=r; ++k)
        tmp[k] = (j>r || (i<=mid && a[i]<=a[j])) ? a[i++] : a[j++];
    copy(tmp+l, tmp+r+1, a+l);
}

5. 紅黑樹（關鍵操作）

• 左旋 / 右旋
• 插入修復：叔父紅 → 變色上移；叔父黑 → 旋轉+變色
• 刪除修復：雙重黑處理，兄弟紅/黑分情況旋轉

6. 計數排序 / 基數排序 / 桶排序

非比較排序，線性時間，適用於已知範圍整數。

7. 希爾排序

for (gap = 1; gap <= n; gap = gap*3+1);
while (gap > 0) { /* 插入排序 */ gap = (gap-1)/3; }

四、代碼獲取

完整 13 個 .cpp 文件已上傳至配套資源，含 main 測試入口，可直接編譯運行驗證。