九章算法 | 烙饼排序 - 杂谈

烙饼排序（Pancake Sort）是一种通过翻转数组前缀来实现排序的算法。其核心思想是每次找到当前未排序部分的最大值，通过两次翻转将其移动到正确位置。以下是详细解答：

算法步骤

初始化：设定未排序部分的右边界 len 为数组长度。
寻找最大值：在未排序部分 [0, len-1] 中找到最大值的索引 maxIndex。
翻转操作：
若 maxIndex 不为 0，翻转 [0, maxIndex]，将最大值移到数组首位。
翻转 [0, len-1]，将最大值移到未排序部分的末尾（即 len-1 位置）。
更新边界：缩小未排序范围（len--），重复步骤 2-3 直到整个数组有序。

代码实现public class Solution { public void pancakeSort(int[] array) { int len = array.length; if (array == null || len == 0) return; while (len > 0) { int maxIndex = 0; // 找到当前未排序部分的最大值索引 for (int i = 0; i < len; i++) { if (array[i] > array[maxIndex]) { maxIndex = i; } } // 若最大值已在正确位置，跳过 if (maxIndex == len - 1) { len--; continue; } // 翻转将最大值移到首位（若不在首位） if (maxIndex != 0) { FlipTool.flip(array, maxIndex); } // 翻转将最大值移到未排序部分的末尾 len--; FlipTool.flip(array, len); } }}复杂度分析

时间复杂度：O(n2)每次查找最大值需遍历未排序部分（O(n)），最多进行 n 次操作，总时间为 O(n2)。
空间复杂度：O(1)仅使用常数额外空间。

示例解析样例 1

输入：[6,11,10,12,7,23,20]输出：[6,7,10,11,12,20,23]操作步骤：

找到最大值 23（索引 5），翻转 [0,5] → [23,7,12,10,11,6,20]，再翻转 [0,6] → [20,6,11,10,12,7,23]。
在剩余部分重复此过程，逐步将最大值移到末尾。

样例 2

输入：[4,2,3]输出：[2,3,4]操作步骤：

最大值 4（索引 0），直接翻转 [0,2] → [3,2,4]。
剩余部分最大值 3（索引 0），翻转 [0,1] → [2,3,4]。

关键点

两次翻转定位最大值：通过两次翻转将当前最大值移动到正确位置。
边界更新：每次操作后，未排序部分右边界左移（len--）。
优化：若最大值已在首位，可省略第一次翻转。

此算法虽非最优（比较次数较多），但通过有限操作（翻转）实现排序，适合特定场景（如硬件限制）。

九章算法 | 烙饼排序

您可能感兴趣问答

Collapsible

热门标签

热点问答