【2013-12-23】《编程之美》读书笔记：烙饼排序问题

[历史归档]本文原发布于 cstriker1407.info 个人博客内容为历史存档仅供参考。发布时间2013-12-23 标题《编程之美》读书笔记烙饼排序问题分类编程 / java / 编程之美 标签java·编程之美·烙饼排序《编程之美》读书笔记烙饼排序问题第1.3节烙饼排序问题解法1每次翻转最大的拿张通过枚举方法来获取最小的数目最近在学习《 编程之美 》这本书书中提到了很多很经典的算法问题和实现学起来真是耗费脑细胞啊。书中的算法实现使用C编写的这里作者自己写了一部分java的实现如果有错误还请各位读者批评指正。截图版权属于原作者。github【 https://github.com/cstriker1407/think_in_java 】第1.3节烙饼排序问题解法1每次翻转最大的拿张代码如下privatestaticfinalint[]UnSortArr{1,5,3,4};//,6,2,9,8,7};//获取最大值publicstaticintgetMaxSortNum(){LinkedListIntegermiddleListnewLinkedListInteger();for(intitem:UnSortArr){middleList.add(item);}System.out.println(未排序middleList.toString());intreverseTime0;inttotalNummiddleList.size();intnumNoSorttotalNum;while(numNoSort0){/* sublist * 返回列表中指定的 fromIndex包括 和 toIndex不包括之间的部分视图。如果 fromIndex 和 toIndex 相等则返回的列表为空。 * 返回的列表由此列表支持因此返回列表中的非结构性更改将反映在此列表中反之亦然。返回的列表支持此列表支持的所有可选列表操作。 *///从没有排序的list里面找到最大的一个数以及它的IDintmaxNumCollections.max(middleList.subList(0,numNoSort));intmaxNumIdxmiddleList.indexOf(maxNum);//翻转最大数到第一个数之间的所有的数据Collections.reverse(middleList.subList(0,maxNumIdx1));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);returnreverseTime;}Java的关于list的工具类比较多也比较好用实现起来相对容易一点。通过枚举方法来获取最小的数目首先备份下用到的工具函数//判断是否排序OKprivatestaticbooleanisListSorted(LinkedListIntegermiddleList){for(inti1;imiddleList.size();i){if(middleList.get(i-1)middleList.get(i)){returnfalse;}}returntrue;}使用递归的方法在上一次翻转的基础上进行二次翻转/* *在当前已经进行部分翻转的list上面进行下一次的翻转并且对翻转的序号x【0x】进行遍历 *times表示当前已经翻转的次数 */privatestaticvoidinternalSort(LinkedListIntegermiddleList,inttimes){//已经排序OK不用再测试了。if(isListSorted(middleList)){//记录最小值minSortNumtimesminSortNum?times:minSortNum;return;}/* *加速判断根据getMaxSortNum函数的测试可以发现最大值为数据list长度的2倍因此当 *当前的翻转数目 估计剩余的最小翻转数 middleList.size() * 2可以认为这次翻转已经没有意义了 */if(timesgetMinSortNum()maxSortNum){return;}/* * 既然不知道如何翻转数目最小那我们就遍历在当前已经部分翻转之后的list上进行二次翻转每次翻转的个数【i】进行遍历。 * 翻转完成之后将数据还原方便下次翻转。 */for(inti0;imiddleList.size();i){Collections.reverse(middleList.subList(0,i1));internalSort(middleList,times1);Collections.reverse(middleList.subList(0,i1));}}为了加速计算减少不必要的递归我们计算出翻转次数的上下限。下限是估计出来的//获取最小估计值不准确。publicstaticintgetMinSortNum(){intnum0;for(inti1;iUnSortArr.length;i){//如果相邻的两个饼的大小也相邻那么就可以认为这两个饼是一个整体if(UnSortArr-UnSortArr1||UnSortArr-UnSortArr-1){}else{num;}}returnnum;}最后是入口测试函数publicclassSortTest{privatestaticfinalint[]UnSortArr{1,5,3,4};//,6,2,9,8,7};//最小的翻转次数privatestaticintminSortNumInteger.MAX_VALUE;//最大的翻转次数privatestaticintmaxSortNum-1;//在当前已经进行部分翻转的list上面进行下一次的翻转publicstaticvoidtestSort(){maxSortNumgetMaxSortNum();LinkedListIntegermiddleListnewLinkedListInteger();for(intitem:UnSortArr){middleList.add(item);}System.out.println(未排序middleList.toString());internalSort(middleList,0);System.out.println(最小数目minSortNum);System.out.println(最大数目maxSortNum);}//判断是否排序OKprivatestaticbooleanisListSorted(LinkedListIntegermiddleList){。。。。。。}/* *在当前已经进行部分翻转的list上面进行下一次的翻转并且对翻转的序号x【0x】进行遍历 *times表示当前已经翻转的次数 */privatestaticvoidinternalSort(LinkedListIntegermiddleList,inttimes){。。。。。。}//获取最小估计值不准确。publicstaticintgetMinSortNum(){。。。。。。}//获取最大值publicstaticintgetMaxSortNum(){。。。。。。}}