JAVA:实现PancakeSor煎饼排序算法（附带源码）

m0_61840987

440人浏览 · 2025-08-04 00:15:00

m0_61840987 · 2025-08-04 00:15:00 发布

【一、项目背景详细介绍】

在计算机科学中，排序算法是基础且广泛的研究方向，从简单的冒泡排序到高性能的快速排序、归并排序，不同算法针对不同场景各有优劣。煎饼排序（Pancake Sort）是一种基于翻转（flip）操作的有趣排序算法，形象地模拟了烹饪煎饼时用锅铲翻转一叠煎饼的过程：每次将当前最大（或最小）的元素“煎饼”翻转到顶端，再整体翻转到末尾，最终完成排序。

煎饼排序的时间复杂度为O(n^2)，空间复杂度为O(1)，虽在大规模数据排序中不具优势，但它独特的翻转思想和原地、常数级额外空间开销，使其在教学、特定有限大小场景以及算法竞赛中颇具趣味和启发意义。同时，该算法与现实场景的类比，也为设计与理解带来直观体验。

【二、项目需求详细介绍】

功能需求
- 在Java环境中实现Pancake Sort算法，能够对整数数组或可比较对象数组进行正序和逆序排序。
- 提供可视化辅助接口（可选），通过打印翻转步骤展示排序过程。
性能需求
- 时间复杂度O(n^2)，应在元素数量较小时运行良好。
- 额外空间复杂度O(1)，除输入数组外无其他大规模开销。
代码质量需求
- 方法职责单一，拆分为翻转函数、主排序函数、辅助工具函数等。
- 充分注释算法关键步骤与翻转原理。
- 提供JUnit单元测试，覆盖边界条件、重复元素和随机场景。

【三、相关技术详细介绍】

数组操作与原地翻转
- Java原生数组的下标访问与交换操作。
- 原地反转子数组的两端指针技巧。
泛型与Comparable接口
- Java泛型支持对任意实现Comparable接口类型进行排序。
算法复杂度分析
- 每次寻找当前未排序区间中的最大（或最小）元素需O(n)，每次翻转操作最坏需O(n)，共O(n^2)。
可视化打印
- 使用System.out.printf或日志框架打印每次翻转前后状态，便于理解过程。

【四、实现思路详细介绍】

主流程
- 从i = arr.length - 1开始，逐步将未排序区间[0, i]的最大元素放到位置i。
- 每次先在[0, i]中找到最大值索引maxIdx。
- 若maxIdx != i：
  a) 若maxIdx != 0，则先翻转子数组[0, maxIdx]，将最大元素带到首位；
  b) 再翻转子数组[0, i]，将最大元素放到末尾i。
辅助翻转方法
- reverse(arr, start, end):双指针从start和end两端交换，直到相遇。
逆序可选
- 通过传入asc参数切换查找最大或最小元素，并相应调整比较逻辑。
可视化输出（可选）
- 在每次reverse或主循环后调用printArray(arr)展示当前数组状态和翻转区间。

【五、完整实现代码】

// 文件：PancakeSort.java
// 描述：基于煎饼翻转思想的Pancake Sort实现，支持泛型、正序/逆序及可选过程打印

import java.util.Arrays;

public class PancakeSort {

    /**
     * 主入口：对可比较对象数组进行煎饼排序
     * @param arr 待排序数组
     * @param ascending true: 正序，false: 逆序
     * @param <T> 实现Comparable接口的类型
     */
    public static <T extends Comparable<T>> void pancakeSort(T[] arr, boolean ascending) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        // 主循环：将最大/最小元素依次放到末尾
        for (int currSize = n; currSize > 1; currSize--) {
            // 找到[0, currSize-1]区间中的最大或最小索引
            int extremumIdx = findExtremumIndex(arr, currSize, ascending);
            if (extremumIdx != currSize - 1) {
                // 若未在末尾，则先翻转到首位，再翻转到末尾
                if (extremumIdx != 0) {
                    reverse(arr, 0, extremumIdx);
                    // 可视化：System.out.println("Flipped 0 to " + extremumIdx + ": " + Arrays.toString(arr));
                }
                reverse(arr, 0, currSize - 1);
                // 可视化：System.out.println("Flipped 0 to " + (currSize-1) + ": " + Arrays.toString(arr));
            }
        }
    }

    /**
     * 找到当前区间中的极值（最大或最小）元素索引
     * @param arr 数组
     * @param length 当前区间长度
     * @param ascending 排序方向
     * @param <T> 元素类型
     * @return 极值元素索引
     */
    private static <T extends Comparable<T>> int findExtremumIndex(T[] arr, int length, boolean ascending) {
        int idx = 0;
        for (int i = 1; i < length; i++) {
            if (ascending) {
                if (arr[i].compareTo(arr[idx]) > 0) idx = i;  // 查找最大值
            } else {
                if (arr[i].compareTo(arr[idx]) < 0) idx = i;  // 查找最小值
            }
        }
        return idx;
    }

    /**
     * 原地翻转子数组
     * @param arr 数组
     * @param start 起始索引
     * @param end 结束索引
     * @param <T> 元素类型
     */
    private static <T> void reverse(T[] arr, int start, int end) {
        while (start < end) {
            T tmp = arr[start];
            arr[start++] = arr[end];
            arr[end--] = tmp;
        }
    }

    /**
     * 简单测试与演示
     */
    public static void main(String[] args) {
        Integer[] data = {5, 2, 9, 1, 5, 6};
        System.out.println("原始数组：" + Arrays.toString(data));
        pancakeSort(data, true);
        System.out.println("煎饼排序正序：" + Arrays.toString(data));
        pancakeSort(data, false);
        System.out.println("煎饼排序逆序：" + Arrays.toString(data));
    }
}

【六、代码详细解读】