記錄自己的了解過程，防止遺忘！！
問題：
星期五的晚上，一幫同僚在希格瑪大廈附近的“硬碟酒吧”多喝了幾杯。程式員多喝了幾杯之後談什麼呢？自然是算法問題。有個同僚說：“我以前在餐館打工，顧客經常點非常多的烙餅。店裡的餅大小不一，我習慣在到達顧客飯桌前，把一摞餅按照大小次序擺好——小的在上面，大的在下面。由于我一隻手托着盤子，隻好用另一隻手，一次抓住最上面的幾塊餅，把它們上下颠倒個個兒，反複幾次之後，這摞烙餅就排好序了。我後來想，這實際上是個有趣的排序問題：假設有n塊大小不一的烙餅，那最少要翻幾次，才能達到最後大小有序的結果呢？”
你能否寫出一個程式，對于n塊大小不一的烙餅，輸出最優化的翻餅過程呢？
首先根據對題目的粗淺了解,寫出的代碼如下：
public class SortPie{
public static void main(String[] args){
int []arr={3,2,1,6,5,4,9,8,7,0};
System.out.println(sort(arr));;
}
private static int sort(int[] arr) {
// TODO Auto-generated method stub
int len=arr.length;
int max=0;
int count=len;
int result=0;
while(count!=0){
for(int i=0;i<len;i++){
if(max<arr[i]){
max=arr[i];
count=i;
}
}
if(count!=len&&count!=len-1)
{
System.out.println(count+"and"+len);
if(count!=0){
conver(arr,0,count);
print(arr);
result++;
}
conver(arr,0,len-1);
print(arr);
result++;
//System.out.println(result);
}
len--;
count=len;
max=0;
}
return result;
}
private static void print(int[] arr) {
// TODO Auto-generated method stub
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
private static void conver(int[] arr, int i, int count) {
// TODO Auto-generated method stub
int temp;
for(int j=i;j<(count+1)/2;j++){
temp=arr[count-j];
arr[count-j]=arr[j];
arr[j]=temp;
}
}
}
這個代碼簡單的實作了尋找一個解，看了解答，發現果然是自己想少了。題目要求實作 最優解 。
而上面的代碼的過程如下：
1.找到未排序數組中最大的，翻轉一次（若最大的在未排序的最後的位置，則跳過）
2.未排序數組部分的翻轉一次（未排序數組中最大的到了最下面，此時将該最大值劃入已排序部分）
3.不斷重複1,2直到全部有序
上述方法隻是找到一個确定解，而要找到最優解，就要找到全部的解，從中找到最優解。那麼隻要窮舉出所有可能的交換方案，那麼一定能夠從中找到最優解。
這樣思考就轉換為找一個翻轉政策使用遞歸把所有的可能全部翻轉一遍。
從間距為1到間距為n-1依次翻轉，然後遞歸。
遞歸的退出條件：
1.烙餅已經有序；
2.遞歸次數超過最大翻轉次數2（n-1）。
由于本題還要求要輸出最優翻餅過程，是以還需記錄下最優解在二叉樹中的搜尋路徑。
舉個例子：
圖中兩個解的路徑分别為{1,2,1,2}和{2,1}
圖中路徑i所表示的含義為第0個到第i個元素進行翻轉，是以有了路徑就可以很容易的求出翻轉過程。
{2,1}的翻轉過程為4,1,2->2,1,4->1,2,4
根據上面的思路，程式如下：
public class BestSortPie {
static int [] pieArr={3,2,1,6,5,4,9,8,7,0};//烙餅原始數組
static int searchtime=0;//調用search函數的次數
static int pieNum=pieArr.length;//烙餅個數
static int maxSwapTime=pieNum*2;//整個過程最大交換次數
static int [] path=new int[maxSwapTime];//儲存烙餅翻轉的分支路徑
public static int[] resultPath=new int[maxSwapTime];//儲存烙餅翻轉的最終分支路徑
public static int[] tempPath=new int[maxSwapTime];//儲存烙餅翻轉的臨時分支路徑
public static void main(String [] args){
search(0);//從初始狀态開始
System.out.println("最大的交換次數為："+maxSwapTime);
System.out.println("搜尋次數為"+searchtime);
System.out.print("初始序列為：");
print(pieArr);
for(int i = 0; i < maxSwapTime; i++){
revert(pieArr,0,resultPath[i]);//根據選擇的分支路徑來對烙餅ji
System.out.print("經過"+(i+1)+"次翻轉後為：");
print(pieArr);
}
}
private static int lowBound(int[] pieArr) {//确定下界
// TODO Auto-generated method stub
int t, ret = 0;
for(int i = 1; i < pieArr.length; i++){
t = pieArr[i] - pieArr[i-1];
if( (t==1) || (t == -1)){//若兩個數之間相鄰，則不需翻轉。
}
else{
ret ++;
}
}
return ret;
}
private static void search(int step) {
// TODO Auto-generated method stub
int i;
int minSwapTime=lowBound(pieArr);
searchtime++;
if(step+minSwapTime>=maxSwapTime){//step表示已經翻轉的次數，minSwapTime表示接下來最少還要翻轉幾次
return;
}
if(isSorted(pieArr)){//判斷是否已有序
if(step<maxSwapTime){
maxSwapTime=step;
for(i = 0; i <maxSwapTime; i++)//記錄解的路徑
resultPath[i] =tempPath[i];
}
return;
}
for(i=1;i<pieNum;i++){
revert(pieArr,0,i);//翻轉
tempPath[step]=i;//記錄目前解的路徑
search(step+1);//遞歸搜尋
revert(pieArr,0,i);//翻轉回上一步，相當于退回一步
}
}
private static void print(int[] arr) {
// TODO Auto-generated method stub
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
private static void revert(int[]pieArr,int i, int count) {
// TODO Auto-generated method stub
int temp;
if(count>i){
for(int j=i;j<(count+1)/2;j++){
temp=pieArr[count-j];
pieArr[count-j]=pieArr[j];
pieArr[j]=temp;
}
}
}
private static boolean isSorted(int[] pieArr) {
// TODO Auto-generated method stub
for(int i = 1; i < pieArr.length; i++)
if( pieArr[i-1] > pieArr[i])
return false;
return true;
}
}
但是上述代碼還存在一些問題，有很多重複搜尋，效率較低。如何确定剪枝條件使得更多的搜尋不必再重複進行，提高效率以最快的速度得到最優解？仍然待優化。
![leetcode 169-Majority Element[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)