什么是“煎饼排序”？
通过“煎饼翻转”来进行排序，叫“煎饼排序”，那什么是“煎饼翻转”呢？（禁止套娃🐶）
一次煎饼翻转的执行过程如下：
选择一个整数 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--; } } };
验证：
OK，以上便是本篇分享~~
我是掘金安东尼，输出暴露输入，技术洞见生活，再会~
