July_algorithm 6.排序查找.pdf

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

1、排序查找七月算法邹博2015年11月1日10月算法在线班2/68主要内容与目标 排序 找到一个O(NlogN)的排序算法 插入排序、选择排序、希尔排序、冒泡排序 堆排序及其思考 快速排序及其思考 非比较方案的排序：记数排序、桶排序、基数排序 总结与思考 排序的目的是什么？10月算法在线班3/68排序问题的提法 给定n个元素的集合A，按照某种方法将A中的元素按非降或非增次序排列。分类：内排序，外排序 常见内排序方法 插入排序/希尔排序 选择排序/锦标赛排序/堆排序 冒泡排序/快速排序 归并排序 基数排序10月算法在线班4/68插入排序/将A(1：n)中的元素按非降次序分类，n1 procedur

2、e INSERTIONSORT(A,n)A(0)-/设置初始边界值for j2 to n do/A(1:j-1)已分类itemA(j);ij-1while itemA(i)do/0ijA(i+1)A(i);ii-1repeatA(i+1)item;repeat end INSERTIONSORT 10月算法在线班5/68锦标赛排序10月算法在线班6/68锦标赛排序10月算法在线班7/68归并排序 基本设计思想：将原始数组A0n-1中的元素分成两个子数组：A10,n/2和A2n/2+1,n-1。分别对这两个子数组单独排序，然后将已排序的两个子数组归并成一个含有n个元素的有序数组。10月算法在线班

3、8/68Code10月算法在线班9/68归并排序的时间复杂度性能分析算法的递推关系：，c为常数若，则有：若2kn2k+1，则T(2k)T(n)4-3-2-5-2和x=3，返回1-2-2-4-3-5。10月算法在线班38/68问题分析 分别申请两个指针p1和p2，小于x的添加到p1中，大于等于x的添加到p2中；最后，将p2链接到p1的末端即可。时间复杂度是O(N)，空间复杂度为O(1)；该问题其实说明：快速排序对于单链表存储结构仍然适用。注：不是所有排序都方便使用链表存储，如堆排序，将不断的查找数组的n/2和n的位置，用链表做存储结构会不太方便。10月算法在线班39/68Code10月算法在线班

4、40/68快速排序Code10月算法在线班41/68快速排序与归并排序的联系 都是分治的思想；经过一次划分后，实现了对A的调整：其中一个子集合的所有元素均小于等于另外一个子集合的所有元素；按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。10月算法在线班42/68快速排序的性能分析 在最好的情况，每次运行一次分区，我们会把一个数列分为两个几近相等的片段。然后，递归调用两个一半大小的数列。一次分区中，i、j一共遍历了n个数，即O(n)记：快速排序的时间复杂度为T(n)，有，T(n)=2*T(n/2)+cnc是某常数 T(n)=O(n

5、*logn)10月算法在线班43/68快速排序的性能分析 在最坏的情况下，两个子数组的长度为 1 和n-1 T(n)=T(1)+T(n-1)+cn 演示：计算得到T(n)=O(n2)思考：如果每次分区，都把数组分成1%和99%的两个子数组，时间复杂度是多少？10月算法在线班44/68附：根据前序中序，计算后序 前序遍历：GDAFEMHZ 中序遍历：ADEFGHMZ 根据前序遍历的特点得知，根结点为G；根结点将中序遍历结果ADEFGHMZ分成ADEF和HMZ两个左子树、右子树。递归确定中序遍历序列ADEF和前序遍历序列DAEF的子树结构；递归确定中序遍历序列HMZ和前序遍历序列MHZ的子树结构；

6、10月算法在线班45/68Code问：时间复杂度是多少？10月算法在线班46/68Heap VS Quick 快速排序的最直接竞争者是堆排序。堆排序通常比快速排序稍微慢，但是最坏情况的运行时间总是O(n log n)。快速排序是经常比较快，但仍然有最坏情况性能的机会。堆排序拥有重要的特点：仅使用固定额外的空间，即堆排序是原地排序，而快速排序需要O(log n)的空间。10月算法在线班47/68快速排序为什么这么快？乱数快速排序有一个值得注意的特性，在任意输入数据的状况下，它只需要O(n log n)的期望时间。是什么让随机的基准变成一个好的选择？假设我们排序一个数列，然后把它分为四个部份。在中

7、央的两个部份将会包含最好的基准值；他们的每一个至少都会比25%的元素大，且至少比25%的元素小。如果我们可以一致地从这两个中央的部份选出一个元素，在到达大小为1的数列前，我们可能最多仅需要把数列分区2log2n次，产生一个 O(nlogn)算法。不幸地，乱数选择只有一半的时间会从中间的部份选择。出人意外的事实是这样就已经足够好了。想像你正在投掷一枚硬币，直到有 k 次国徽朝上。尽管这需要很长的时间，平均来说只需要 2k 次投掷。且在 100k 次投掷中得不到 k 次国徽朝上的概率，是像天文数字一样的非常小注。借由同样的论证，快速排序的递归平均只要2(2log2n)的调用深度就会终止。注：该概率

8、小于7.9E-31如果它的平均调用深度是O(log n)且每一阶的调用树状过程最多有 n 个元素，则全部完成的工作量就是 O(n log n)。10月算法在线班48/68BFPRT算法 题目：求第k大的数，如何解决？得到了前k大的数，显然顺便得到第k大的数，即：该问题至少存在O(Nlogk)的算法 事实上，通过快速排序的Partition思想，第k大的数可以在期望是O(N)的算法内解决 最坏情况是O(N2)，但可以使用二次取中的办法避免最坏情况的发生 借鉴第k大的数的思想，如何解决前k大的数 Partition之后的前面的k个即为所求。Blum、Floyd、Pratt、Rivest、Tarja

9、n10月算法在线班49/68n个数中，选择第k大的数 数组a0n-1，选择第k大的数 利用快速排序的思想，随机选择划分元素t，将数组分成大于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月算法在线班50/68如果遇到相等的数，怎么处理 数组中M出现次数很多，而恰好选了M作为PivotKey

10、，那么，将导致Partition之后，一部分很长，一部分很短。(比如：极限情况：数组中都是M，划分后，一部分是整体本身，一部分为0)数据分成“大于M、小于M、等于M”三部分，可类比荷兰国旗问题。10月算法在线班51/68考虑相等元素的O(N)时间选择算法10月算法在线班52/68各种排序算法的时间复杂度10月算法在线班53/68排序算法效率比较注：该数据来自网络，可信度低10月算法在线班54/68稳定性 一般的说，如果排序过程中，只有相邻元素进行比较，是稳定的，如冒泡排序、归并排序；如果间隔元素进行了比较，往往是非稳定的，如堆排序、快速排序。归并排序是指针逐次后移，姑且算相邻元素的比较直接插入

11、排序可以将新增数据放在排序的相等数据的后面，使得直接插入排序是稳定的；但二分插入排序本身不稳定，如果要稳定，需要向后探测 一般的说，如果能够方便整理数据，对于不稳定的排序，可以使用(Ai,i)键对来进行算法，可以使得不稳定排序变成稳定排序。10月算法在线班55/68计数排序 计数排序的核心思想，是用空间换取时间，本质是建立了基于元素的Hash表。10月算法在线班56/68计数排序10月算法在线班57/68桶排序/基数排序 将元素分到若干个桶中，每个桶分别排序，然后归并 由于桶之间往往是有序的(如：洗牌中的1-13个点数，整数按照数位0-9基数排序等)，所以，它们的时间复杂度不是(完全)基于比较

12、的，时间复杂度下限不是O(NlogN)如果桶的个数和待排序数目相同，则退化为记数排序。每个桶内只有1个元素 思考：如果每个桶内最多有2个元素呢？求给定N个数的最大间距，要求O(N)的时间复杂度如：8,3,17,6,14,4的最大间距为610月算法在线班58/68附：最大间隔 给定整数数组A0N-1，求这N个数排序后最大间隔。如：1,7,14,9,4,13的最大间隔为4。排序后：1,4,7,9,13,14，最大间隔是13-9=4 显然，对原数组排序，然后求后项减前项的最大值，即为解。可否有更好的方法？10月算法在线班59/68附：Code10月算法在线班60/68寻找和为定值的两个数 输入一个数

13、组A0N-1和一个数字Sum，在数组中查找两个数Ai,Aj，使得Ai+Aj=Sum。10月算法在线班61/68暴力求解 从数组中任意选取两个数x,y，判定它们的和是否为输入的数字Sum。时间复杂度为O(N2)，空间复杂度O(1)。10月算法在线班62/68稍好一点的方法 两头扫如果数组是无序的，先排序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-；数组无序

14、的时候，时间复杂度最终为O(NlogN+N)=O(NlogN)。10月算法在线班63/68Code10月算法在线班64/68讨论：Hash方案的可行性 算法步骤 选择适当的Hash函数，对原数组建立Hash结构 遍历数组ai，计算Hash(Sum-ai)是否存在 算法可行性 时间复杂度，空间复杂度10月算法在线班65/68排序的目的 排序本身：得到有序的序列 方便查找 如：体会“2-sum问题”的求解过程。长度为N的有序数组，查找某元素的时间复杂度是多少？长度为N的有序链表，查找某元素的时间复杂度是多少？单链表、双向链表 如何解决该问题？10月算法在线班66/68跳跃链表(Skip List)

15、AVL-Tree/RB-Tree/BTree 跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(logn)平均时间)。具有简单、高效、动态(Simple、Effective、Dynamic)的特点。基本上，跳跃列表是对有序的链表附加辅助链表，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分结点(因此得名)。查找结点、增加结点、删除结点操作的期望时间都是logN的(with high probability1-1/(n),W.H.P.)。将在后面的课程中详细阐述。10月算法在线班67/68我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班68/68感谢大家恳请大家批评指正！