演算法實戰：煎餅排序

問題：一堆大小不一的煎餅，只能用一隻手翻轉（另一隻手端盤），目標是大的在下、小的在上。輸出最優翻轉步驟。

算法思想

每輪處理當前未排序部分：

1. 找出未排序區間最大餅的索引 max。
2. 翻轉 [max, n-1]，將最大餅移到頂部。
3. 翻轉 [cur, n-1]，將最大餅移到已排序區頂部（即正確位置）。
4. cur++ 縮小未排序區，重複直到 cur == n-1。

最多 2(n-1) 次翻轉完成排序。

C++ 實現

#include <iostream>
using namespace std;

void reverse(int* a, int i, int j) { // 翻轉區間 [i, j]
    if (i < 0 || j < 0 || j < i) return;
    for (int t = 0; t < (j - i + 1) / 2; ++t) {
        swap(a[i + t], a[j - t]);
    }
}

void printStep(int* a, int pos, int n) {
    cout << "翻轉位置 " << pos << "：";
    for (int i = 0; i < n; ++i) cout << a[i] << ' ';
    cout << endl;
}

void pancakeSort(int* a, int n) {
    int cur = 0;
    while (cur < n - 1) {
        int maxIdx = cur;
        for (int i = cur + 1; i < n; ++i)
            if (a[i] > a[maxIdx]) maxIdx = i;

        if (maxIdx != n - 1) { // 最大餅不在底部
            if (maxIdx != cur) { // 不在頂部先翻到頂部
                printStep(a, maxIdx, n);
                reverse(a, maxIdx, n - 1);
            }
            // 翻到正確位置 cur
            printStep(a, cur, n);
            reverse(a, cur, n - 1);
        }
        ++cur;
    }
}

int main() {
    int a[] = {3, 1, 2};
    int n = sizeof(a)/sizeof(a[0]);
    pancakeSort(a, n);
    cout << "排序完成：";
    for (int x : a) cout << x << ' ';
    return 0;
}

示例輸出

翻轉位置 0：3 1 2
翻轉位置 0：2 1 3
翻轉位置 1：2 1 3
翻轉位置 1：1 2 3
排序完成：1 2 3

小結

煎餅排序是受限操作下的排序經典問題，展示了「選擇+翻轉」的直觀策略。雖非最優比較排序，但在只能翻轉的約束下最佳。