3 1 2

2(n-1)此翻转就可完成排序。


#include <iostream>
using namespace std;
//烙饼排序
void print(int* a, int pos,int n);
void out(int* a, int n);

//翻转数组中i-j位置元素的函数
void reverse(int* a, int i, int j){
if (i < 0 || j < 0 || j < i){
return;
}
int tmp = j - i + 1; //需翻转的元素个数
for (int t = 0; t < tmp / 2; t++){
int k = a[j];
a[j] = a[i];
a[i] = k;
j--;
i++;
}
}

//烙饼排序
void PrefixSorting(int* a,int n){

int cur = 0; //指针，指向当前已排序的烙饼位置的上一个烙饼

while (cur < n-1){

//查找烙饼最大值
int max = cur;
for (int i = max+1; i < n; i++){
if (a[max] < a[i]){
max = i;
}
}
//当最大的烙饼翻转到最上面
print(a, max,n);
reverse(a,max, n - 1);
out(a, n);

//将cur处的烙饼与当前最上面的烙饼（同时也是最大）翻转
print(a, cur,n);
reverse(a, cur, n - 1);
out(a, n);
cur++;
}
}

//输出翻转步骤信息
void print(int* a, int pos,int n){
cout << "翻转烙饼：" <<pos<< " ; 烙饼值为：" <<a[pos]<< " - ";
}

void out(int* a, int n){
for (int i = 0; i < n; i++){
cout << a[i] << " ";
}
cout << "\n";
}

int main(){
int array[] = { 4, 7, 5, 9, 8, 6, 1, 2, 3 };
out(array, 9);
//烙饼排序
PrefixSorting(array, 9);
getchar();
return 0;
}