C語言經典算法總結：TopK、最大子數組和、全排列、循環移位

1. 最小 K 個數

方法一：快速選擇（QuickSelect）

改進快速排序 partition：每次 partition 後得到基準索引 idx。若 idx == k-1 結束；idx > k-1 遞歸左半；否則遞歸右半。平均 O(n)，最壞 O(n²)（可用隨機基準或中位數中位數優化）。缺點：修改原數組順序。

方法二：大根堆（尺寸 K）

維護大小為 K 的最大堆。遍歷數組：堆未滿直接入堆；滿後若新元素 < 堆頂，替換堆頂並下沉。最終堆中即為最小 K 個。時間 O(n log K)，不修改原數組，適合流式數據/大文件。

2. 最大子數組和（Kadane 算法）

核心思想：以 i 結尾的最大子數組和 = max(arr[i], arr[i] + 以 i-1 結尾的最大和)。
若前綴和 >0 繼續累加，否則捨棄重新開始。
代碼：

int maxSubArray(int *a, int n) {
    int max_sum = a[0], cur = a[0];
    for (int i=1; i 0) ? cur + a[i] : a[i];
        if (cur > max_sum) max_sum = cur;
    }
    return max_sum;
}

時間 O(n)，空間 O(1)。可擴展輸出區間端點、處理全負數組（返回最大單元素）。

3. 字符串全排列（遞歸回溯）

固定位置 begin，對 begin..end 每個字符與 begin 交換，遞歸處理 begin+1，回溯時交換恢復。去重：交換前檢查 [begin, i) 是否已有相同字符，有則跳過。
時間 O(n!)，空間 O(n) 遞歸棧。

4. 數組循環移位（原地逆序法）

左移 k 位：
1. 逆序前 k 個
2. 逆序後 n-k 個
3. 逆序整個數組
例：1234567 左移 3 → 321 7654 → 4567123
右移 k 位：對稱操作（先逆序後 k 個）。
時間 O(n)，空間 O(1)，無需額外緩衝區。

綜合對比表

面試高頻追問

• TopK：海量數據（無法全載入內存）如何求 TopK？ → 外部排序/分治+堆/MapReduce。
• 最大子數組：若為環形數組？ → 總和 - 最小子數組和（非全包情況）。
• 全排列：字典序下一個排列？ → STL next_permutation 實現邏輯。
• 循環移位：GCD(n,k) 環替換法（Juggling Algorithm）如何工作？