大饼排序详解(doge)

manbo

2026-07-11 16:52:38

发布于：天津

6阅读

0回复

0点赞

大饼排序 $β0.1$ 版

什么是大饼排序？

思想和概述

大饼排序比较中规中矩。
唯一允许操作：翻转数组前 k 个元素（前缀翻转），不能交换、不能任意区间反转。

我们怎么做？(AI生成)

锁定当前未排序区间 [0, size-1]；
找到区间内最大值下标 pos；
两次翻转把最大值送到区间末尾：

若不在首位：翻转前 pos+1 个，最大值到顶部；

翻转前 size 个，最大值落到未排序末尾，固定不动；

size--，缩小未排序区间，重复直到有序。

参考代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

// 翻转前k个元素（k是个数，下标0~k-1）
void flip(vector<int>& a, int k)
{
    int l = 0, r = k - 1;
    while(l < r) swap(a[l++], a[r--]);
}

vector<int> pancakeSort(vector<int>& a)
{
    vector<int> op; // 记录每次翻转的k
    int n = a.size();
    for(int sz = n; sz > 1; sz--)
    {
        // 找未排序区间最大值下标
        int maxp = 0;
        for(int i = 0; i < sz; i++)
            if(a[i] > a[maxp]) maxp = i;
        if(maxp == sz - 1) continue; // 已经在末尾，不用操作
        if(maxp != 0)
        {
            flip(a, maxp + 1);
            op.push_back(maxp + 1);
        }
        flip(a, sz);
        op.push_back(sz);
    }
    return op;
}

int main()
{
    vector<int> arr = {3,1,4,2};
    auto res = pancakeSort(arr);
    for(int x : res) printf("%d ", x);
    return 0;
}