每日算法 — 使用java实现Pancake Sorting：翻转操作与贪心最优前缀反转排序

算法概述

Pancake Sorting（煎饼排序）是一种有趣且独特的排序算法，其基本操作是翻转数组的前缀（类似于用铲子翻转一叠煎饼）。该算法的目标是将一个无序数组通过最少的翻转次数变为有序，在实际应用中与基因组重排中的反转排序问题密切相关。

本文将深入讲解煎饼排序的贪心策略、上界分析以及变体问题（烧焦煎饼问题），并给出完整的Java实现。

核心思想

翻转操作

煎饼排序的唯一允许操作是flip(arr, k)：将数组从索引0到k的子段进行反转。例如：

数组: [3, 2, 5, 1, 4]
flip(2) -> [5, 2, 3, 1, 4]  (前3个元素反转)
flip(4) -> [4, 1, 3, 2, 5]  (前5个元素反转)

贪心排序策略

标准煎饼排序采用贪心策略，每次将当前未排序部分的最大元素”翻转”到正确位置：

1. 在未排序前缀[0...i]中找到最大元素的索引maxIdx
2. 执行flip(maxIdx)，将该最大元素翻到数组最前面
3. 执行flip(i)，将该最大元素从前面翻到位置i（其最终正确位置）
4. i减1，重复上述过程直到数组有序

该策略保证在最多2n-3次翻转内完成排序（对于n≥2）。

示例演示

排序[3, 2, 5, 1, 4]：

让我重新仔细追踪：
初始: [3, 2, 5, 1, 4]，i=4，未排序部分[0..4]，最大元素5在索引2
– flip(2): [5, 2, 3, 1, 4]
– flip(4): [4, 1, 3, 2, 5]，5到达位置4 ✓

现在 i=3，未排序部分[0..3] = [4, 1, 3, 2]，最大元素4在索引0
– 4已经在未排序部分的末尾（位置3相对于未排序部分），不需要flip(0)
– 实际上4已经在位置3，而i=3，所以不需要任何操作？等等，4在索引0…

让我重新：数组现在是[4, 1, 3, 2, 5]，i=3，未排序部分是[0..3] = [4, 1, 3, 2]
最大元素是4，在索引0。
– flip(0): [4, 1, 3, 2]… 翻转0个元素没有意义，如果maxIdx已经是i，就跳过

实际上，如果最大元素已经在位置i，就不需要翻转。但这里4在索引0，不在位置3。
– flip(0): 单元素翻转，数组不变 [4, 1, 3, 2, 5]
– flip(3): [2, 3, 1, 4, 5]，4到达位置3 ✓

现在 i=2，未排序部分[0..2] = [2, 3, 1]，最大元素3在索引1
– flip(1): [3, 2, 1, 4, 5]
– flip(2): [1, 2, 3, 4, 5]，3到达位置2 ✓

现在 i=1，未排序部分[0..1] = [1, 2]，最大元素2在索引1
– 已经在位置1，不需要操作

现在 i=0，只有一个元素，完成！

总共5次翻转（有一步flip(0)可优化掉）。

实际上，当maxIdx == 0时我们可以直接flip(i)，不需要先flip(0)。优化后的策略：
– 如果maxIdx == i：已经在正确位置，跳过
– 如果maxIdx == 0：直接flip(i)
– 否则：先flip(maxIdx)，再flip(i)

完整Java实现

import java.util.*;

/**
 * Pancake Sorting（煎饼排序）实现
 * 时间复杂度: O(n²) 次比较，O(n) 次翻转
 * 空间复杂度: O(1)
 */
public class PancakeSort {

    /**
     * 执行煎饼排序，返回翻转操作序列
     * @param arr 待排序数组（会被原地修改）
     * @return 翻转位置列表（flip(k)表示翻转前k+1个元素）
     */
    public static List<Integer> pancakeSort(int[] arr) {
        List<Integer> flips = new ArrayList<>();
        int n = arr.length;

        // 从后往前处理，每次将当前未排序部分的最大元素放到正确位置
        for (int size = n; size > 1; size--) {
            // 在[0, size-1]范围内找到最大元素的索引
            int maxIdx = findMaxIndex(arr, size);

            // 如果最大元素已经在正确位置，跳过
            if (maxIdx == size - 1) {
                continue;
            }

            // 如果最大元素不在最前面，先将其翻到最前面
            if (maxIdx != 0) {
                flip(arr, maxIdx);
                flips.add(maxIdx);
            }

            // 将最大元素从前面翻到其最终位置
            flip(arr, size - 1);
            flips.add(size - 1);
        }

        return flips;
    }

    /**
     * 在arr[0..limit-1]中找到最大元素的索引
     */
    private static int findMaxIndex(int[] arr, int limit) {
        int maxIdx = 0;
        for (int i = 1; i < limit; i++) {
            if (arr[i] > arr[maxIdx]) {
                maxIdx = i;
            }
        }
        return maxIdx;
    }

    /**
     * 翻转数组的前k+1个元素（索引0到k）
     */
    private static void flip(int[] arr, int k) {
        int left = 0;
        int right = k;
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    /**
     * 带详细步骤追踪的煎饼排序
     */
    public static List<Integer> pancakeSortWithTrace(int[] arr) {
        List<Integer> flips = new ArrayList<>();
        int n = arr.length;
        int[] original = arr.clone();

        System.out.println("初始数组: " + Arrays.toString(original));

        for (int size = n; size > 1; size--) {
            int maxIdx = findMaxIndex(arr, size);

            if (maxIdx == size - 1) {
                System.out.println("第" + (n - size + 1) + "轮: 最大元素" + arr[maxIdx] + 
                                 "已在位置" + maxIdx + "，无需翻转");
                continue;
            }

            if (maxIdx != 0) {
                flip(arr, maxIdx);
                flips.add(maxIdx);
                System.out.println("第" + (n - size + 1) + "轮: 翻转前" + (maxIdx + 1) + 
                                 "个元素，最大元素" + arr[0] + "翻到前面");
                System.out.println("       -> " + Arrays.toString(arr));
            }

            flip(arr, size - 1);
            flips.add(size - 1);
            System.out.println("       再翻转前" + size + "个元素，放到位置" + (size - 1));
            System.out.println("       -> " + Arrays.toString(arr));
        }

        System.out.println("排序完成: " + Arrays.toString(arr));
        System.out.println("翻转序列: " + flips);
        return flips;
    }

    /**
     * 计算煎饼排序的上界（最大翻转次数）
     * 已知上界为 2n - 3 (n >= 2)
     * 实际上对于n >= 2，任何排列都可以用不超过 (5n+5)/3 次翻转排序
     */
    public static int upperBound(int n) {
        return Math.max(0, 2 * n - 3);
    }

    /**
     * 烧焦煎饼问题（Burnt Pancake Problem）
     * 每个煎饼有一面是烧焦的，排序后所有烧焦面必须朝下
     * 翻转时煎饼的正反面会交换
     * 
     * 状态表示: (值, 朝向)，朝向1表示正面朝上，-1表示反面（烧焦面）朝上
     */
    public static List<Integer> burntPancakeSort(int[] values, int[] orientations) {
        List<Integer> flips = new ArrayList<>();
        int n = values.length;

        for (int size = n; size > 0; size--) {
            // 在未排序部分找到需要放到位置size-1的煎饼
            // 这个位置应该放第size大的煎饼，且烧焦面朝下（朝向=-1）
            int targetValue = size; // 假设值就是1到n
            int targetIdx = -1;
            boolean foundReversed = false;

            for (int i = 0; i < size; i++) {
                if (Math.abs(values[i]) == targetValue) {
                    targetIdx = i;
                    foundReversed = (values[i] < 0);
                    break;
                }
            }

            if (targetIdx == -1) continue;

            // 如果煎饼烧焦面朝上，或者不在正确位置，需要翻转
            if (targetIdx != size - 1 || foundReversed || orientations[targetIdx] == 1) {
                if (targetIdx != 0) {
                    flipWithOrientation(values, orientations, targetIdx);
                    flips.add(targetIdx);
                }
                flipWithOrientation(values, orientations, size - 1);
                flips.add(size - 1);
            }
        }

        return flips;
    }

    /**
     * 带朝向翻转的烧焦煎饼翻转操作
     */
    private static void flipWithOrientation(int[] values, int[] orientations, int k) {
        int left = 0;
        int right = k;
        while (left < right) {
            // 交换值
            int tempV = values[left];
            values[left] = values[right];
            values[right] = tempV;

            // 交换并翻转朝向
            int tempO = orientations[left];
            orientations[left] = orientations[right];
            orientations[right] = tempO;

            left++;
            right--;
        }

        // 翻转所有经过的元素的朝向
        for (int i = 0; i <= k; i++) {
            orientations[i] = -orientations[i];
            values[i] = -values[i]; // 值也取反表示翻面
        }
    }

    // ==================== 测试主程序 ====================

    public static void main(String[] args) {
        // 测试1：基础煎饼排序
        System.out.println("=== 测试1: 基础煎饼排序 ===");
        int[] arr1 = {3, 2, 5, 1, 4};
        int[] arr1Copy = arr1.clone();
        List<Integer> flips1 = pancakeSortWithTrace(arr1Copy);
        System.out.println("翻转次数: " + flips1.size() + " (上界: " + upperBound(arr1.length) + ")");

        // 测试2：逆序数组（最坏情况）
        System.out.println("\n=== 测试2: 逆序数组 ===");
        int[] arr2 = {5, 4, 3, 2, 1};
        int[] arr2Copy = arr2.clone();
        List<Integer> flips2 = pancakeSortWithTrace(arr2Copy);
        System.out.println("翻转次数: " + flips2.size());

        // 测试3：随机数组
        System.out.println("\n=== 测试3: 随机数组 ===");
        int[] arr3 = generateRandomArray(8, 42);
        int[] arr3Copy = arr3.clone();
        List<Integer> flips3 = pancakeSortWithTrace(arr3Copy);
        System.out.println("翻转次数: " + flips3.size());

        // 测试4：大规模性能测试
        System.out.println("\n=== 测试4: 大规模性能测试 ===");
        performanceTest();

        // 测试5：烧焦煎饼问题
        System.out.println("\n=== 测试5: 烧焦煎饼问题 ===");
        burntPancakeDemo();
    }

    /**
     * 生成随机数组
     */
    private static int[] generateRandomArray(int n, int seed) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = i + 1;
        Random rand = new Random(seed);
        for (int i = n - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        return arr;
    }

    /**
     * 性能测试
     */
    private static void performanceTest() {
        int n = 10000;
        int[] arr = generateRandomArray(n, 123);

        long start = System.currentTimeMillis();
        List<Integer> flips = pancakeSort(arr);
        long end = System.currentTimeMillis();

        // 验证排序正确性
        boolean sorted = true;
        for (int i = 1; i < n; i++) {
            if (arr[i] < arr[i - 1]) {
                sorted = false;
                break;
            }
        }

        System.out.println("数组大小: " + n);
        System.out.println("翻转次数: " + flips.size());
        System.out.println("运行时间: " + (end - start) + "ms");
        System.out.println("排序正确: " + sorted);
    }

    /**
     * 烧焦煎饼问题演示
     */
    private static void burntPancakeDemo() {
        int n = 4;
        int[] values = {3, -1, 4, -2}; // 正值表示正面朝上，负值表示烧焦面朝上
        int[] orientations = {1, -1, 1, -1};

        System.out.println("初始状态 (值, 朝向): ");
        for (int i = 0; i < n; i++) {
            System.out.print("(" + values[i] + "," + (orientations[i] > 0 ? "正" : "焦") + ") ");
        }
        System.out.println();

        // 目标：按值升序排列，所有烧焦面朝下（朝向=-1）
        System.out.println("目标: 值升序且所有烧焦面朝下");
    }
}

理论分析

翻转次数上界

对于n个元素的排列，煎饼排序的翻转次数上界为：

• 简单上界：2n – 3（n ≥ 2）
• 改进上界：(5n + 5) / 3（Gates与Papadimitriou, 1979）
• 已知下界：15n / 14（已证明存在排列需要至少这么多翻转）

煎饼数（Pancake Number）

P(n)定义为n个煎饼的最坏情况翻转次数。已知的精确值：

烧焦煎饼数

烧焦煎饼问题的翻转次数上界更紧：
– 上界：3n/2 + 1（Cohen与Blum, 1995）
– 下界：3n/2（Heydari与Sudborough, 1997）

应用场景

• 基因组重排：生物序列通过反转操作进行重排，与煎饼排序同构
• 并行计算：路由网络中的前缀反转路由算法
• 算法教学：作为非传统排序算法的经典案例
• 组合优化：研究排列群上的Cayley图直径问题
• CPU缓存优化：某些缓存管理策略可建模为受限翻转问题

小结

Pancake Sorting通过独特的翻转操作展示了算法设计的多样性。其贪心策略每次将未排序部分的最大元素通过最多两次翻转放到正确位置，保证在O(n)次翻转内完成排序。该算法不仅是教学中的趣味案例，更与基因组学中的反转排序问题有深刻联系。理解煎饼排序的关键在于掌握前缀翻转的性质以及贪心选择的正确性证明。对于追求最少翻转次数的优化版本，该问题已被证明是NP-难的，这使其在计算复杂性理论中也占有一席之地。