最近在学习《 编程之美 》这本书,书中提到了很多很经典的算法问题和实现,学起来真是耗费脑细胞啊。书中的算法实现使用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() { 。。。。。。 } }
发表评论