【编程之美】一摞烙饼的排序

#include<stdio.h>
#include<assert.h>
class CPrefixSorting
{
public:
	CPrefixSorting()
	{
		m_nCakeCnt = 0;
		m_nMaxSwap = 0;
	}
	//计算烙饼翻转信息 
	//pCakeArray 存储烙饼索引数组
	//nCakeCnt 烙饼个数
	void Run(int* pCakeArray, int nCakeCnt)
	{
		Init(pCakeArray, nCakeCnt);

		m_nSearch = 0;
		Search(0);
	}

	//输出烙饼具体翻转的次数
	void Output()
	{
		for(int i = 0; i < m_nMaxSwap; i++)
			printf("%d ", m_SwapArray[i]);

		printf("\n |Search Times| : %d \n", m_nSearch);  //索引次数
		printf("Total Swap Times = %d \n", m_nMaxSwap);  //翻转次数
	}

private:
	void Init(int* pCakeArray, int pCakeCnt)
	{
		assert(pCakeArray != NULL);
		assert(pCakeCnt > 0);
		m_nCakeCnt = pCakeCnt;

		//初始化烙饼数组
		m_CakeArray = new int[m_nCakeCnt];
		assert(m_CakeArray != NULL);
		for(int i = 0; i < m_nCakeCnt; i++)
		{
			m_CakeArray[i] = pCakeArray[i];
		}

		//设置更多交换次数信息
		m_nMaxSwap = UpBound(m_nCakeCnt);

		//初始化交换结果数组
		m_SwapArray = new int[m_nMaxSwap];
		assert(m_SwapArray != NULL);

		//初始化中间交换结果信息
		m_ReverseCakeArray = new int[m_nCakeCnt];
		for(int i = 0; i < m_nCakeCnt; i++)
		{
			m_ReverseCakeArray[i] = m_CakeArray[i];
		}
		m_ReverseCakeArraySwap = new int[m_nMaxSwap];
	}

	//寻找当前翻转的上界
	int UpBound(int nCakeCnt)
	{
		return nCakeCnt*2;
	}

	//寻找当前翻转的下界
	int LowerBound(int* pCakeArray, int nCakeCnt)
	{
		int t, ret = 0;
		//根据当前数组的排序信息情况来判断至少需要交换多少次
		for(int i = 1; i < nCakeCnt; i++)
		{
			t = pCakeArray[i] - pCakeArray[i-1];
			if((t == 1) || (t == -1))
			{
			}
			else
			{
				ret ++;
			}
		}
		return ret;
	}

	//排序的主函数
	void Search(int step)
	{
		int i,nEstimate;

		m_nSearch++;

		//估算这次搜索所需要的最小交换次数
		nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt);
		if(step + nEstimate > m_nMaxSwap)
			return;

		//如果已经排好序，即翻转完成，输出结果
		if(IsSorted(m_ReverseCakeArray,m_nCakeCnt))
		{
			if(step < m_nMaxSwap)
			{
				m_nMaxSwap = step;
				for(i = 0; i < m_nMaxSwap; i++)
					m_SwapArray[i] = m_ReverseCakeArraySwap[i];
			}
		    return;
		}

		//递归进行翻转
		for(i = 1;i < m_nCakeCnt; i++)
		{
			Revert(0, i);
			m_ReverseCakeArraySwap[step] = i;
			Search(step + 1);
			Revert(0, i);
		}
	}

	//判断是否已经排好序
	bool IsSorted(int* pCakeArray, int nCakeCnt)
	{
		for(int i = 1; i < nCakeCnt; i++)
		{
			if(pCakeArray[i-1] > pCakeArray[i])
				return false;
		}
		return true;
	}

	//翻转烙饼信息
	void Revert(int nBegin, int nEnd)
	{
		assert(nEnd > nBegin);
		int i, j, t;
		
		for(i = nBegin, j = nEnd; i < j; i++, j--)
		{
			t = m_ReverseCakeArray[i];
			m_ReverseCakeArray[i] = m_ReverseCakeArray[j];
			m_ReverseCakeArray[j] = t;
		}
	}

private:
	int* m_CakeArray; //烙饼信息数组
	int m_nCakeCnt;  //烙饼个数
	int m_nMaxSwap;  //最多交换次数
	int* m_SwapArray;//交换结果数组
	int* m_ReverseCakeArray;//当前翻转烙饼信息数组
	int* m_ReverseCakeArraySwap;//当前翻转烙饼交换结果数组
	int m_nSearch;//当前搜索次数信息
};

int main()  
{   
    CPrefixSorting *l=new CPrefixSorting();  
    int aa[10]={ 3,2,1,6,5,4,9,8,7,0};  
      
    l->Run(aa,10);  
    l->Output();  
 
    return 0;  
} 
           

结果在编译时存在以下问题：

1） Assert 应该是 assert

2） m_arrSwap 未被定义，应该改为m_SwapArray

3 ）Init函数两个for循环，后一个没定义变量i，应该将i 改为 int i

另外，每运行一次Run函数，就会调用Init函数，就会申请新的内存，但却没有释放原来的内存，会造成内存泄漏。if(step + nEstimate > m_nMaxSwap) 这句还会造成后面对m_ReverseCakeArraySwap数组的越界访问，使程序不能正常运行。

书上程序的低效主要是由于进行剪枝判断时，没有考虑好边界条件，可进行如下修改：

1 ） if(step + nEstimate > m_nMaxSwap)  >改为 >=。

2 ） 判断下界时，如果最大的烙饼不在最后一个位置，则要多翻转一次，因而在LowerBound函数return ret; 前插入行：

                if (pCakeArray[nCakeCnt-1] != nCakeCnt-1)

                                        ret++;

3 ） n个烙饼，翻转最大的n-2烙饼最多需要2*(n-2)次，剩下的2个最多1次，因而上限值为2*n-3，因此，m_nMaxSwap初始值可以取2*n-3+1=2*n-2，这样每步与m_nMaxSwap的判断就可以取大等于号。

4 ）采用书上提到的确定“上限值”的方法，直接构建一个初始解，取其翻转次数为m_nMaxSwap的初始值。

         1和2任改一处，都能使搜索次数从172126降到两万多，两处都改，搜索次数降到3475。若再改动第3处，搜索次数降到2989；若采用4的方法（此时初始值为10），搜索次数可降到1045。