一摞烙饼的排序

　　问题：写出一个程序，对于n块大小不一的烙饼，输出最优化的翻饼过程？要保证烙饼按照大小次序摆好——小的在上面，大的在下面。

分析与解法：

用java实现的代码如下：

package chapter1youxizhilePrefixSorting;import java.util.Scanner;/** * 一摞烙饼的 * @author DELL * */public class PrefixSorting {    private int[] m_CakeArray;  //烙饼信息数组    private int m_nCakeCnt;  //烙饼个数    private int m_nMaxSwap;  //最多交换次数，根据推断，最多为(m_nCakeCnt-1)*2;    private int[] m_SwapArray;  //交换结果数组    private int[] m_ReverseCakeArray;    //当前翻转烙饼信息数组    private int[] m_ReverseCakeArraySwap;  //当前翻转烙饼交换结果数组    private int m_nSearch;    //当前搜索次数信息        public PrefixSorting(int[] pCakeArray, int nCakeCnt){        m_nCakeCnt = 0;        m_nMaxSwap = 0;        Run(pCakeArray, nCakeCnt);    }        /**     * 计算烙饼翻转信息     * @param pCakeArray  存储烙饼索引数组     * @param nCakeCnt      烙饼个数     */    public void Run(int[] pCakeArray, int nCakeCnt){        Init(pCakeArray, nCakeCnt);        m_nSearch = 0;        Search(0);    }        //输出烙饼具体翻转次数    public void Output(){        System.out.print("交换结果数组为：");        for(int i=0;i
     
       m_nMaxSwap)            return;        //如果已经排好序，即翻转完成，输出结果        if(IsSorted(m_ReverseCakeArray, m_nCakeCnt)){            if(step
      
        pCakeArray[i]){                return false;            }        }        return true;    }        /**     * 翻转烙饼信息     * @param nBegin 开始位置     * @param nEnd 结束位置     */    private void Revert(int nBegin, int nEnd){        if(nBegin>=nEnd){            System.out.println("参数信息有误！开始位置不能大于等于结束位置！");        }        int i,j,t;        //翻转烙饼信息        for(i=nBegin,j=nEnd; i
      
     

程序运行结果如下：

请输入烙饼从上到下的半径,以逗号分隔：3,2,1,6,5,4,9,8,7,0交换结果数组为：4 8 6 8 4 9 |Search Times| : 148015Total Swap times = 6