日拱算法：什么是“煎饼排序”？

2022 年 8 月 30 日
广东
本文字数：984 字
阅读完需：约 3 分钟

什么是“煎饼排序”？

通过“煎饼翻转”来进行排序，叫“煎饼排序”，那什么是“煎饼翻转”呢？（禁止套娃🐶）

一次煎饼翻转的执行过程如下：

选择一个整数 k ，1 <= k <= arr.length 反转子数组 arr[0...k-1]（下标从 0 开始）例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。

以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。

任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。

比如：

输入：[3,2,4,1]输出：[4,2,4,3]解释：我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。初始状态 arr = [3, 2, 4, 1]第一次翻转后（k = 4）：arr = [1, 4, 2, 3]第二次翻转后（k = 2）：arr = [4, 1, 2, 3]第三次翻转后（k = 4）：arr = [3, 2, 1, 4]第四次翻转后（k = 3）：arr = [1, 2, 3, 4]，此时已完成排序。

复制代码

解题思路：

每次找出最大值，做两次翻转
第一次将它翻转到最上面
第二次将它翻转到最下面

这样每次轮都会把最大的放到最下面，重复递归，直到第一个。

JavaScript 实现：

/** * @param {number[]} arr * @return {number[]} */var pancakeSort = function(arr) {    const res = [];    sort(arr, arr.length);    return res;    function sort(cakes, n) {        if (n === 1) return;        // 寻找最大烧饼索引        let maxCake = 0;        let maxCakeIndex = 0;        for (let i = 0; i < n; i++) {            if (cakes[i] > maxCake) {                maxCake = cakes[i];                maxCakeIndex = i;            }        }
        // 第一次反转，将最大烧饼翻到最上面        reverse(cakes, 0, maxCakeIndex);        // 记录反转        res.push(maxCakeIndex + 1);        // 第二次翻转，翻转到最下面        reverse(cakes, 0, n - 1);        res.push(n);        // 递归        sort(cakes, n - 1);    }
    // 翻转元素    function reverse (arr, i, j) {        // 翻转元素,对称翻转        while (i < j) {            const temp = arr[i];            arr[i] = arr[j];            arr[j] = temp;            i++; j--;        }    }};