烧饼排序算法 :: labuladong的算法小抄

[labuladong]

文章链接点这里：烧饼排序算法

评论礼仪 见这里，违者直接拉黑。

[fornobugworld]

是不是简化版汉诺塔？

[zhongweiLeex]

是不是简化版汉诺塔？

我看到一半也想起汉诺塔了

[ywj1352]

done

[861130245]

应该是优先反转有序的部分

[Leochens]

js

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var pancakeSort = function (arr) {

    // 在n个中找到最大的 然后铲起它 翻转其上的所有饼 这样他就到了最上面 然后翻转所有饼 这样最大的就到了最下面
    // 在对n-1个饼 进行此过程 直到n==1 返回 已经排好序了 
    // 以上思想很容易想到递归 在每次翻转的时候记录翻转序列中最大的数字

    let res = [];
    mysort(arr.length);
    function mysort(n) {
        let maxCakeIndex = 0, maxCake = 0;
        if (n == 1) return; // 就一个煎饼 不用翻转
        // 找到最大的煎饼 记录下索引
        for (let i = 0; i < n; i++) {
            if (arr[i] > maxCake) {
                maxCake = arr[i];
                maxCakeIndex = i;
            }
        }


        // 翻转 使得最大的煎饼在上面
        myreverse(0, maxCakeIndex);
        res.push(maxCakeIndex + 1);

        // 翻转 使得最大的煎饼到下面
        myreverse(0, n - 1);
        res.push(n);
        // console.log(arr);

        mysort(n - 1); // 
    }
    function myreverse(i, j) {
        while (i < j) {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    return res;



};

[potatogit]

最后那个思考题，是不是可以双向BFS来解，起点终点都有了，要求最短路径。

[zhuxiaoze]

有点像

[Maxiah]

我看开头就想起了汉诺塔，但是这题用递归有些过于复杂了，用冒泡排序每次把最大值沉底应该会快一些

[Gao-kai]

哈哈哈看到這個題目真的好好笑

[yonggui-yan]

打卡

[Lionb-Liu]

// 通过插入排序来实现的解法如下。    每次返回的操作序列都比递归解法返回的操作序列更短。
// 如果对返回前的ans序列剔除其中冗余的数字，则最终的操作序列会更短，但不确定是否为排序烧饼的最短操作序列
// 冗余操作是指连续翻转两个相同的长度，比如 [2, 3, 3, 4, 2] 中的两个连续的3。还能以更高效的插入排序框架来提升效率。
class Solution {
public:
    vector<int> pancakeSort(vector<int>& arr) {
        vector<int> ans;
        for(int i =  1,  j,  tmp,  n = arr.size();  i < n;  i++)  // 插入排序,前i个数字已经有序
            for(j = -1;  ++j < i; )
                if(arr[j] > arr[i]) {
                    for(tmp = i;  tmp > j; )
                        swap(arr[tmp], arr[--tmp]);
                    // 至此,以上内容为插入排序
                    // ================================
                    // 每轮插入排序等价于4次PancakeFlips
                    if(j != 0) //如果j==0则下面这两行的翻转操作是冗余的
                        ans.push_back(i + 1),      // 第1次翻转
                        ans.push_back(i + 1 - j);  // 第2次翻转
                    if(i != j + 1)  // 仅仅翻转1个数字的操作也会是冗余的
                        ans.push_back(i - j);  // 第3次翻转
                    ans.push_back(i + 1);  // 第4次翻转
                    break;
                }
        return ans;
    }
};

[marcmk6]

我一看完啪就写了一个bfs了，很快啊！就超时了

[muxingg]

vector<int> pancakeSort(vector<int>& arr) {
        // 答案数组申请空间
        res.reserve( 10 * arr.size());
           
        // 因为设想一下用锅铲翻转一堆烧饼的情景，其实是有一点限制的，
        // 我们每次只能将最上面（数组的左边）的若干块饼子翻转
        // 考虑使用插入排序    （代码提交的内存消耗仅击败 %8，还并不知道为什么）
        for (int i = 1; i < arr.size(); ++i) {

            // i 代表无序区第一个元素
            int value = arr[i];
            // j 代表有序区最后一个元素
            int j = i - 1;
            while (j >= 0 && arr[j] > value) {
                // arr[j + 1] = arr[j]; // 覆盖
                --j;
            } // j < 0 || arr[j] <= value;
            //arr[j + 1] = value;
            if (j + 1 != i) {
                 // 发生无序，进行翻转（一切符合条件，需翻转4次）
                 // 1 2 3 5 4
                 //     j   i
                 // 发生无序的两个元素 arr[j + 1] 和arr[i]
                 /* 
                      1 2 3 5 4
                 1st: [5 3 2 1] 4
                 2nd: [4 1 2 3 5]
                 3rd: [3 2 1 4] 5
                 4th: [1 2 3] 4 5 */              
                if (i - 1 > 0) { //[0..0] 就不翻转了
                     // [0..i - 1] 翻转，k 为索引加一
                    reverse(arr.begin(), arr.begin() + i);// 左闭右开区间[first, last)
                    res.push_back(i);  
                }
                 // [0..i] 翻转，k 为索引加一
                reverse(arr.begin(), arr.begin() + i + 1);
                res.push_back( i + 1);  // 翻转[0..i];

                // 发生无序时，--j;这里 j + 1才是发生无序的位置
                if (j + 1 > 0) { //[0..0] 就不翻转了
                 // [0..j + 1] 翻转，k 为索引加一
                    reverse(arr.begin(), arr.begin() + j + 2);
                    res.push_back(j + 2);  
                }
                if (j > 0) { //[0..0] 就不翻转了
                  // [0..j] 翻转，k 为索引加一
                    reverse(arr.begin(), arr.begin() + j + 1);
                    res.push_back(j + 1);  
                }
            }   
        }
        return res;
    }
    // 翻转数组

private:
    // 记录答案的数组
    vector<int> res;

[muxingg]

// 题目的目标，将arr = [3,2,4,1] 通过翻转实现 arr = [1, 2, 3, 4]；
// 这即为对 数组arr 进行升序排序的结果；
 //数组已经有序则不会发生翻转