【算法】烙饼排序

问题描述：
把一摞大小不一的烙饼按顺序排好，大的在下面，小的在上面，
要求只能用一只手去翻转烙饼位置，另一只手要端盘子；
输出最优化的排序过程。

---

示例：
3 1 2
翻转 1 , 当前烙饼排序 3 2 1
成功!

---

算法描述：
问题解析：一个未排序的数列，如 a,b,c,d,~z
每一次选取其中一个数，将它与最后一个数之间的
所有数（包含它们两个）进行翻转，直到这一列数
排好顺序

算法：
每次都先找出未排序烙饼中最大的烙饼，然后将其翻转到最上面；
然后将它翻转到已排序烙饼的最上层，接着换下一块，如此，只需要
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;
}