好记性不如铅笔头

java, 编程, 编程之美

《编程之美》读书笔记:烙饼排序问题

最近在学习《 编程之美 》这本书,书中提到了很多很经典的算法问题和实现,学起来真是耗费脑细胞啊。书中的算法实现使用C编写的,这里作者自己写了一部分java的实现,如果有错误,还请各位读者批评指正。截图版权属于原作者。

github:

https://github.com/cstriker1407/think_in_java 】

CONTENTS

第1.3节:烙饼排序问题:

解法1,每次翻转最大的拿张:

代码如下:

private static final int[] UnSortArr = {1,5,3,4};//,6,2,9,8,7};
//获取最大值
public static int getMaxSortNum()
{
	LinkedList<Integer> middleList = new LinkedList<Integer>();
	for (int item : UnSortArr)
	{
		middleList.add(item);
	}
	System.out.println("未排序:" + middleList.toString());
	int reverseTime = 0;
	int totalNum = middleList.size();
	int numNoSort = totalNum;
	while (numNoSort > 0)
	{
		/* sublist:
		 * 返回列表中指定的 fromIndex(包括 )和 toIndex(不包括)之间的部分视图。(如果 fromIndex 和 toIndex 相等,则返回的列表为空)。
		 * 返回的列表由此列表支持,因此返回列表中的非结构性更改将反映在此列表中,反之亦然。返回的列表支持此列表支持的所有可选列表操作。
		 */
		//从没有排序的list里面找到最大的一个数,以及它的ID
		int maxNum = Collections.max( middleList.subList(0, numNoSort));
		int maxNumIdx = middleList.indexOf(maxNum);
		
		//翻转最大数到第一个数之间的所有的数据
		Collections.reverse( middleList.subList(0, maxNumIdx + 1) );
		System.out.println("找到最大数["+ maxNum +"]并翻转:" + middleList.toString());
		reverseTime++;
		
		//翻转第一个数和没有排序的最后一个数间的所有数据
		Collections.reverse( middleList.subList(0, numNoSort) );
		System.out.println("将最大数翻到底部:" + middleList.toString());
		reverseTime++;
		
		//没有排序的数据个数--
		numNoSort--;
	}
	System.out.println("总数:"+ totalNum +" 翻转次数为:" + reverseTime);
	return reverseTime;
}

 Java的关于list的工具类比较多,也比较好用,实现起来相对容易一点。

通过枚举方法来获取最小的数目:

首先备份下用到的工具函数:

//判断是否排序OK
private static boolean isListSorted(LinkedList<Integer> middleList)
{
	for (int i = 1; i < middleList.size(); i++)
	{
		if(middleList.get(i-1) >= middleList.get(i))
		{
			return false;
		}
	}
	return true;
}

 使用递归的方法,在上一次翻转的基础上进行二次翻转:

/*
 *在当前已经进行部分翻转的list上面进行下一次的翻转,并且对翻转的序号x【0,x】进行遍历
 *times表示当前已经翻转的次数
 */
private static void internalSort(LinkedList<Integer> middleList, int times)
{
	//已经排序OK,不用再测试了。
	if (isListSorted(middleList))
	{	//记录最小值
		minSortNum = times < minSortNum ? times : minSortNum;
		return;
	}
	
	/*
	 *加速判断,根据getMaxSortNum函数的测试,可以发现最大值为数据list长度的2倍,因此当
	 *当前的翻转数目 + 估计剩余的最小翻转数 > middleList.size() * 2,可以认为这次翻转已经没有意义了
	 */
	if (times + getMinSortNum() > maxSortNum)
	{
		return;
	}
	
	/*
	 * 既然不知道如何翻转数目最小,那我们就遍历,在当前已经部分翻转之后的list上,进行二次翻转,每次翻转的个数【i】进行遍历。
	 * 翻转完成之后将数据还原,方便下次翻转。
	 */
	for (int i = 0; i < middleList.size(); i++)
	{
		Collections.reverse( middleList.subList(0, i + 1) );
		internalSort(middleList, times + 1);
		Collections.reverse( middleList.subList(0, i + 1) );
	}
}

 为了加速计算,减少不必要的递归,我们计算出翻转次数的上下限。(下限是估计出来的)

//获取最小估计值,不准确。
public static int getMinSortNum()
{
	int num = 0;
	for (int i = 1; i < UnSortArr.length; i++)
	{
		//如果相邻的两个饼的大小也相邻,那么就可以认为这两个饼是一个整体
		if (UnSortArr[i] - UnSortArr[i-1] == 1 || UnSortArr[i] - UnSortArr[i-1] == -1)
		{
		}else
		{
			num++;
		}
	}
	return num;
}

 最后是入口测试函数:

public class SortTest
{
	private static final int[] UnSortArr = {1,5,3,4};//,6,2,9,8,7};
	
	//最小的翻转次数
	private static int minSortNum = Integer.MAX_VALUE;
	//最大的翻转次数
	private static int maxSortNum = -1;
	
	//在当前已经进行部分翻转的list上面进行下一次的翻转
	public static void testSort(  )
	{
		maxSortNum = getMaxSortNum();
		
		LinkedList<Integer> middleList = new LinkedList<Integer>();
		for (int item : UnSortArr)
		{
			middleList.add(item);
		}
		System.out.println("未排序:" + middleList.toString());
		internalSort(middleList, 0);
		
		System.out.println("最小数目:" + minSortNum);
		System.out.println("最大数目:" + maxSortNum);
	}
	
	//判断是否排序OK
	private static boolean isListSorted(LinkedList<Integer> middleList)
	{
	。。。。。。
	}

	/*
	 *在当前已经进行部分翻转的list上面进行下一次的翻转,并且对翻转的序号x【0,x】进行遍历
	 *times表示当前已经翻转的次数
	 */
	private static void internalSort(LinkedList<Integer> middleList, int times)
	{
	。。。。。。
	}
	
	
	//获取最小估计值,不准确。
	public static int getMinSortNum()
	{
	。。。。。。
	}
	
	//获取最大值
	public static int getMaxSortNum()
	{
	。。。。。。
	}
}

发表评论

18 − 3 =

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据