July_algorithm 6.1排序查找.pdf

《July_algorithm 6.1排序查找.pdf》由会员分享，可在线阅读，更多相关《July_algorithm 6.1排序查找.pdf（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排序查找七月算法邹博2015年11月1日10月算法在线班2/85八皇后问题 在88格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种解法。10月算法在线班3/85八皇后问题算法分析 分析：显然任意一行有且仅有1个皇后，使用数组queen07表示第i行的皇后位于哪一列。对于“12345678”这个字符串，调用全排列问题的代码，并且加入分支限界的条件判断是否相互攻击即可；10月算法在线班4/85八皇后问题算法分析 深度优先搜索：将第i个皇后放置在第j列上，如果当前位置与其他皇后相互攻击，则剪枝掉该结点。分析对角线：主对角线上(i-j)为定值

2、，取值范围是-(N-1)(i-j)N-1，从而：0(i-j+N-1)2*N-2；次对角线上(i+j)为定值，取值范围是0(i+j)2*N-2；使用m102N-2、m202N-2记录皇后占据的对角线 上述数据结构与剪枝过程适用于N皇后问题。10月算法在线班5/85Code10月算法在线班6/85Code10月算法在线班7/85数独Sudoku 解数独问题，初始化时的空位用.表示。每行、每列、每个九宫内，都是1-9这9个数字。10月算法在线班8/85数独Sudoku分析 若当前位置是空格，则尝试从1到9的所有数；如果对于1到9的某些数字，当前是合法的，则继续尝试下一个位置调用自身即可。10月算法在

3、线班9/85Code10月算法在线班10/85Code10月算法在线班11/85非递归数独Sudoku10月算法在线班12/85马踏棋盘 给定mn的棋盘，将棋子“马”放在任意位置上，按照走棋规则将“马”移动，要求每个方格只能进入一次，最终使得“马”走遍棋盘的所有位置。如给定88的国际象棋棋盘(右)如给定89的中国象棋棋盘(左)10月算法在线班13/85问题分析 显然，如果从A点能够跳到B点，则从B点也能够跳到A点。所以，马的起始位置可以从任意一点开始，不妨从左上角开始。若当前位置为(i,j)，则遍历(i,j)的八邻域，如果邻域尚未经过，则跳转。深度优先搜索10月算法在线班14/85Code10

4、月算法在线班15/85启发式搜索 若棋盘规模较大，则在较深的棋位才能发现“无路可走”而不得不回溯。贪心的启发式策略：最多情况下，每个棋位有8个后继。由于棋盘边界和已经遍历的原因，往往是少于8个的。当前棋位可以跳转的后继棋位记为x个，这x个棋位的后继棋位数目记做h1h2hx，优先选择最小的hi。策略：优先选择孙结点数目最少的那个子结点原因：孙结点最少的子结点，如果当前不跳转则最容易在后期无法跳转。10月算法在线班16/85Code10月算法在线班17/85Code10月算法在线班18/85Code10月算法在线班19/85主要内容与目标 排序 找到一个O(NlogN)的排序算法 插入排序、选择排

5、序、希尔排序、冒泡排序 堆排序及其思考 快速排序及其思考 非比较方案的排序：记数排序、桶排序、基数排序 总结与思考 排序的目的是什么？10月算法在线班20/85排序问题的提法 给定n个元素的集合A，按照某种方法将A中的元素按非降或非增次序排列。分类：内排序，外排序 常见内排序方法 插入排序/希尔排序 选择排序/锦标赛排序/堆排序 冒泡排序/快速排序 归并排序 基数排序10月算法在线班21/85插入排序/将A(1：n)中的元素按非降次序分类，n1 procedure INSERTIONSORT(A,n)A(0)-/设置初始边界值for j2 to n do/A(1:j-1)已分类itemA(j)

6、;ij-1while itemA(i)do/0ijA(i+1)A(i);ii-1repeatA(i+1)item;repeat end INSERTIONSORT 10月算法在线班22/85锦标赛排序10月算法在线班23/85锦标赛排序10月算法在线班24/85归并排序 基本思想：将数组A0n-1中的元素分成两个子数组：A10n/2和A2n/2+1n-1。分别对这两个子数组单独排序，然后将已排序的两个子数组归并成一个含有n个元素的有序数组。10月算法在线班25/85Code10月算法在线班26/85归并排序的时间复杂度性能分析算法的递推关系：，c为常数若，则有：若2kn2k+1，则T(2k)T

7、(n)4-3-2-5-2和x=3，返回1-2-2-4-3-5。10月算法在线班55/85问题分析 分别申请两个指针p1和p2，小于x的添加到p1中，大于等于x的添加到p2中；最后，将p2链接到p1的末端即可。时间复杂度是O(N)，空间复杂度为O(1)；该问题其实说明：快速排序对于单链表存储结构仍然适用。注：不是所有排序都方便使用链表存储，如堆排序，将不断的查找数组的n/2和n的位置，用链表做存储结构会不太方便。10月算法在线班56/85Code10月算法在线班57/85快速排序Code10月算法在线班58/85快速排序与归并排序的联系 都是分治的思想；经过一次划分后，实现了对A的调整：其中一个

8、子集合的所有元素均小于等于另外一个子集合的所有元素；按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。10月算法在线班59/85快速排序的性能分析 在最好的情况，每次运行一次分区，我们会把一个数列分为两个几近相等的片段。然后，递归调用两个一半大小的数列。一次分区中，i、j一共遍历了n个数，即O(n)记：快速排序的时间复杂度为T(n)，有，T(n)=2*T(n/2)+cnc是某常数 T(n)=O(n*logn)10月算法在线班60/85快速排序的性能分析 在最坏的情况下，两个子数组的长度为 1 和n-1 T(n)=T(1)+T(n-

9、1)+cn 演示：计算得到T(n)=O(n2)思考：如果每次分区，都把数组分成1%和99%的两个子数组，时间复杂度是多少？10月算法在线班61/85附：根据前序中序，计算后序 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ 根据前序遍历的特点得知，根结点为G；根结点将中序遍历结果ADEFGHMZ分成ADEF和HMZ两个左子树、右子树。递归确定中序遍历序列ADEF和前序遍历序列DAEF的子树结构；递归确定中序遍历序列HMZ和前序遍历序列MHZ的子树结构；10月算法在线班62/85Code问：时间复杂度是多少？10月算法在线班63/85Heap VS Quick 快速排序的最直接竞争者是堆

10、排序。堆排序通常比快速排序稍微慢，但是最坏情况的运行时间总是O(n log n)。快速排序是经常比较快，但仍然有最坏情况性能的机会。堆排序拥有重要的特点：仅使用固定额外的空间，即堆排序是原地排序，而快速排序需要O(log n)的空间。10月算法在线班64/85快速排序为什么这么快？乱数快速排序有一个值得注意的特性，在任意输入数据的状况下，它只需要O(n log n)的期望时间。是什么让随机的基准变成一个好的选择？假设我们排序一个数列，然后把它分为四个部份。在中央的两个部份将会包含最好的基准值；他们的每一个至少都会比25%的元素大，且至少比25%的元素小。如果我们可以一致地从这两个中央的部份选出

11、一个元素，在到达大小为1的数列前，我们可能最多仅需要把数列分区2log2n次，产生一个 O(nlogn)算法。不幸地，乱数选择只有一半的时间会从中间的部份选择。出人意外的事实是这样就已经足够好了。想像你正在投掷一枚硬币，直到有 k 次国徽朝上。尽管这需要很长的时间，平均来说只需要 2k 次投掷。且在 100k 次投掷中得不到 k 次国徽朝上的概率，是像天文数字一样的非常小注。借由同样的论证，快速排序的递归平均只要2(2log2n)的调用深度就会终止。注：该概率小于7.9E-31如果它的平均调用深度是O(log n)且每一阶的调用树状过程最多有 n 个元素，则全部完成的工作量就是 O(n log

12、 n)。10月算法在线班65/85BFPRT算法 题目：求第k大的数，如何解决？得到了前k大的数，显然顺便得到第k大的数，即：该问题至少存在O(Nlogk)的算法 事实上，通过快速排序的Partition思想，第k大的数可以在期望是O(N)的算法内解决 最坏情况是O(N2)，但可以使用二次取中的办法避免最坏情况的发生 借鉴第k大的数的思想，如何解决前k大的数 Partition之后的前面的k个即为所求。Blum、Floyd、Pratt、Rivest、Tarjan10月算法在线班66/85n个数中，选择第k大的数 数组a0n-1，选择第k大的数 利用快速排序的思想，随机选择划分元素t，将数组分成

13、大于t和小于等于t两部分。记为a0m-1和am+1n-1，若m=k-1，则t即为所求；若mk-1，则递归计算a0m-1中第k大的数；若mk-1，则递归计算am+1n-1中第k-m大的数。平均时间复杂度O(n)，最差O(n2)。快排的时候,左右两个分支都要进行递归，找k大的时候只需要对其中一边进行递归。可使用“二次取中”的规则得到最坏情况是O(n)的算法。10月算法在线班67/85如果遇到相等的数，怎么处理 数组中M出现次数很多，而恰好选了M作为PivotKey，那么，将导致Partition之后，一部分很长，一部分很短。(比如：极限情况：数组中都是M，划分后，一部分是整体本身，一部分为0)数据

14、分成“大于M、小于M、等于M”三部分，可类比荷兰国旗问题。10月算法在线班68/85考虑相等元素的O(N)时间选择算法10月算法在线班69/85各种排序算法的时间复杂度10月算法在线班70/85排序算法效率比较注：该数据来自网络，可信度低10月算法在线班71/85稳定性 一般的说，如果排序过程中，只有相邻元素进行比较，是稳定的，如冒泡排序、归并排序；如果间隔元素进行了比较，往往是非稳定的，如堆排序、快速排序。归并排序是指针逐次后移，姑且算相邻元素的比较直接插入排序可以将新增数据放在排序的相等数据的后面，使得直接插入排序是稳定的；但二分插入排序本身不稳定，如果要稳定，需要向后探测 一般的说，如果

15、能够方便整理数据，对于不稳定的排序，可以使用(Ai,i)键对来进行算法，可以使得不稳定排序变成稳定排序。10月算法在线班72/85计数排序 计数排序的核心思想，是用空间换取时间，本质是建立了基于元素的Hash表。10月算法在线班73/85计数排序10月算法在线班74/85桶排序/基数排序 将元素分到若干个桶中，每个桶分别排序，然后归并 由于桶之间往往是有序的(如：洗牌中的1-13个点数，整数按照数位0-9基数排序等)，所以，它们的时间复杂度不是(完全)基于比较的，时间复杂度下限不是O(NlogN)如果桶的个数和待排序数目相同，则退化为记数排序。每个桶内只有1个元素 思考：如果每个桶内最多有2个

16、元素呢？求给定N个数的最大间距，要求O(N)的时间复杂度如：8,3,17,6,14,4的最大间距为610月算法在线班75/85附：最大间隔 给定整数数组A0N-1，求这N个数排序后最大间隔。如：1,7,14,9,4,13的最大间隔为4。排序后：1,4,7,9,13,14，最大间隔是13-9=4 显然，对原数组排序，然后求后项减前项的最大值，即为解。可否有更好的方法？10月算法在线班76/85附：Code10月算法在线班77/85寻找和为定值的两个数 输入一个数组A0N-1和一个数字Sum，在数组中查找两个数Ai,Aj，使得Ai+Aj=Sum。10月算法在线班78/85暴力求解 从数组中任意选取

17、两个数x,y，判定它们的和是否为输入的数字Sum。时间复杂度为O(N2)，空间复杂度O(1)。10月算法在线班79/85稍好一点的方法 两头扫如果数组是无序的，先排序O(NlogN)，然后用两个指针i，j，各自指向数组的首尾两端，令i=0，j=n-1，然后i+，j-，逐次判断ai+aj是否等于Sum：若ai+ajsum，则i不变，j-；若ai+ajsum，则i+，j不变；若ai+aj=sum，如果只要求输出一个结果，则退出；否则，输出结果后i+，j-；数组无序的时候，时间复杂度最终为O(NlogN+N)=O(NlogN)。10月算法在线班80/85Code10月算法在线班81/85讨论：Has

18、h方案的可行性 算法步骤 选择适当的Hash函数，对原数组建立Hash结构 遍历数组ai，计算Hash(Sum-ai)是否存在 算法可行性 时间复杂度，空间复杂度10月算法在线班82/85排序的目的 排序本身：得到有序的序列 方便查找 如：体会“2-sum问题”的求解过程。长度为N的有序数组，查找某元素的时间复杂度是多少？长度为N的有序链表，查找某元素的时间复杂度是多少？单链表、双向链表 如何解决该问题？10月算法在线班83/85跳跃链表(Skip List)AVL-Tree/RB-Tree/BTree 跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(logn)平均时间)。具有简单、高效、动态(Simple、Effective、Dynamic)的特点。基本上，跳跃列表是对有序的链表附加辅助链表，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分结点(因此得名)。查找结点、增加结点、删除结点操作的期望时间都是logN的(with high probability1-1/(n),W.H.P.)。将在后面的课程中详细阐述。10月算法在线班84/85我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班85/85感谢大家恳请大家批评指正！