第1章 算法分析基本概念.ppt

1第第1章章 算法分析基本概念算法分析基本概念20092009年年年年2 2月月月月2323日日日日2引言引言历史背景历史背景算法复杂性算法复杂性时间复杂性时间复杂性时间复杂性时间复杂性空间复杂性空间复杂性空间复杂性空间复杂性排序排序选择排序选择排序选择排序选择排序插入排序插入排序插入排序插入排序自底向上合并排序自底向上合并排序自底向上合并排序自底向上合并排序冒泡排序冒泡排序冒泡排序冒泡排序希尔排序希尔排序希尔排序希尔排序快速排序快速排序快速排序快速排序3引言引言计算机科学就是计算机科学就是算法研究算法研究4算法（算法（Algorithm）解题方案的准确完整的描述，是解题方案的准确完整的描述，是在有限步骤内求解某一问题所使用在有限步骤内求解某一问题所使用的一组定义明确的规则。的一组定义明确的规则。无论是解题思路还是编写程序，无论是解题思路还是编写程序，都是在实施某种算法。前者是推理都是在实施某种算法。前者是推理实现，后者是操作实现；实现，后者是操作实现；算法不是程序，但算法是用程序算法不是程序，但算法是用程序或伪代码来描述的。或伪代码来描述的。5算法分析（算法分析（Algorithm Analysis）算法分析研究的目标为：算法一算法分析研究的目标为：算法一旦转换成某种语言的程序，该程序旦转换成某种语言的程序，该程序在计算机上运行，需要多少时间和在计算机上运行，需要多少时间和存储空间才能完成解题方案。存储空间才能完成解题方案。确定一个程序的运行效率，既可确定一个程序的运行效率，既可使用数学分析方法，也可使用实验使用数学分析方法，也可使用实验测试方法，可以在理论和实践二个测试方法，可以在理论和实践二个方面作出评估。方面作出评估。算法特征算法特征一个算法应具有以下五个重要的特征：一个算法应具有以下五个重要的特征：有穷性有穷性：一个算法必须保证执行有限点之后结束；：一个算法必须保证执行有限点之后结束；确切性确切性：算法的每一步骤须有确切的定义；：算法的每一步骤须有确切的定义；输入输入：一个算法有：一个算法有0个或多个输入，以刻画运算对象个或多个输入，以刻画运算对象的初始情况，这里的初始情况，这里0个输入是指算法本身定义了初始个输入是指算法本身定义了初始条件；条件；输出：输出：一个算法有一个或多个输出，以反映对输入一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法毫无意义；数据加工后的结果。没有输出的算法毫无意义；可行性可行性：算法原则上能够精确地运行，而且人们用：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。笔和纸做有限次运算后即可完成。671.2 历史背景历史背景 2020世纪早期，能否用一种有效的过程（算法）来求解世纪早期，能否用一种有效的过程（算法）来求解世纪早期，能否用一种有效的过程（算法）来求解世纪早期，能否用一种有效的过程（算法）来求解问题，受到广泛的关注。人们的注意力是放在问题的可问题，受到广泛的关注。人们的注意力是放在问题的可问题，受到广泛的关注。人们的注意力是放在问题的可问题，受到广泛的关注。人们的注意力是放在问题的可解和不可解的分类上。解和不可解的分类上。解和不可解的分类上。解和不可解的分类上。问题的可判定性和可解性的研究领域，称为问题的可判定性和可解性的研究领域，称为问题的可判定性和可解性的研究领域，称为问题的可判定性和可解性的研究领域，称为“可计算可计算可计算可计算理论理论理论理论”。数字计算机出现以后，由于有限的资源，提出了尽可数字计算机出现以后，由于有限的资源，提出了尽可数字计算机出现以后，由于有限的资源，提出了尽可数字计算机出现以后，由于有限的资源，提出了尽可能少用资源的有效算法的需求，导致出现计算复杂性的能少用资源的有效算法的需求，导致出现计算复杂性的能少用资源的有效算法的需求，导致出现计算复杂性的能少用资源的有效算法的需求，导致出现计算复杂性的新领域。新领域。新领域。新领域。“计算复杂性计算复杂性计算复杂性计算复杂性”是研究可解类问题的效率。效率是用是研究可解类问题的效率。效率是用是研究可解类问题的效率。效率是用是研究可解类问题的效率。效率是用解决问题所需的时间和空间来描述的。解决问题所需的时间和空间来描述的。解决问题所需的时间和空间来描述的。解决问题所需的时间和空间来描述的。历史背景历史背景要使计算机完成人们预定的工作，首先必要使计算机完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详对问题的每个对象和处理规则给出正确详尽的描述，其中程序的尽的描述，其中程序的数据结构数据结构和和变量变量用用来描述问题的对象，来描述问题的对象，程序结构程序结构，函数函数和和语语句句用来描述问题的算法、用来描述问题的算法、算法算法和和数据结构数据结构是程序的两个重要方面。是程序的两个重要方面。8算法是问题求解过程的精确描述。一个算法由有算法是问题求解过程的精确描述。一个算法由有限条可完成或机械地执行的，有结果指令组成。限条可完成或机械地执行的，有结果指令组成。指令正确地描述了要完成的任务和它们所执行的指令正确地描述了要完成的任务和它们所执行的顺序。计算机按算法指令所描述的顺序使得算法顺序。计算机按算法指令所描述的顺序使得算法的指令能在有限的步骤内终止，或终止于给出问的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。题的解，或终止于指出问题对此输入数据无解。通常求解一个问题可能会有多种算法可供选择，通常求解一个问题可能会有多种算法可供选择，选择的主要标准首先是算法的选择的主要标准首先是算法的正确性和可靠性，正确性和可靠性，简单性和易理解性简单性和易理解性。其次是算法所需要的。其次是算法所需要的存储空存储空间少和执行更快间少和执行更快等。等。9历史背景历史背景算法复杂性算法复杂性算法的复杂性是算法效率的质量，是评价算算法的复杂性是算法效率的质量，是评价算法优劣的重要依据。一个算法的复杂性的高法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的低体现在运行该算法所需要的计算机资源的多少。所需的资源越多，该算法的复杂性越多少。所需的资源越多，该算法的复杂性越高；反之，所需的资源越低，该算法的复杂高；反之，所需的资源越低，该算法的复杂性越低。性越低。计算机的资源。最重要的是计算机的资源。最重要的是时间和空间时间和空间（即（即存储器）资源。因而算法的复杂性有时间复存储器）资源。因而算法的复杂性有时间复杂性和空间复杂性之分。杂性和空间复杂性之分。10对于任意给定的问题，设计出复杂性尽可能低对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法过程中追求的一个重的算法是我们在设计算法过程中追求的一个重要目标责任制，另一方面，当给定的问题已经要目标责任制，另一方面，当给定的问题已经有多种算法时，选择其中之复杂性最低者，是有多种算法时，选择其中之复杂性最低者，是我们在选用算法适应遵循的一个重要准则，因我们在选用算法适应遵循的一个重要准则，因此，算法的复杂性分析对算法的设计或选用有此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。着重要的指导意义和实用价值。关于算法的复杂性，有两个问题要弄清楚：关于算法的复杂性，有两个问题要弄清楚：用怎样的一个量表达一个算法的复杂性；用怎样的一个量表达一个算法的复杂性；对于一个对定的一个算法，怎样具体计算它的复对于一个对定的一个算法，怎样具体计算它的复杂性杂性11算法复杂性算法复杂性问题：已知不重复且已经按从小到大排好的问题：已知不重复且已经按从小到大排好的n个整数的数组个整数的数组A1.n。对于给定的整数。对于给定的整数x，要，要求寻找一个下标，使得求寻找一个下标，使得Aj=x，若找不到，则，若找不到，则返回一个返回一个0.该问题的一个简单算法是：从头到尾扫描数该问题的一个简单算法是：从头到尾扫描数组组A。按照该方法，或者扫到。按照该方法，或者扫到A的第的第i个分量时个分量时发现满足发现满足Aj=x，或者扫到，或者扫到A的最后一个分量，的最后一个分量，经检测仍不满足经检测仍不满足Aj=x12算法复杂性算法复杂性13出循环分析：出循环分析：x=Aj，此时，此时jn；j等于等于n，但，但An与与x尚未比较（或相等或不相等）尚未比较（或相等或不相等）。算法算法1.1 LinearSearch（Page 3）输入：输入：n个元素的数组个元素的数组A1.n和元素和元素x输出：如果输出：如果x=Aj（1jn），则输出），则输出 j，否则输，否则输出出0。1.j12.while(jAmid，如果，如果x在在A中，则它必定是中，则它必定是Amid+1，Amid+2，Ahigh中的一个，接下来只需在中的一个，接下来只需在Amid+1.high中搜索中搜索x。换句话说，换句话说，Alow.mid中的项目在后续比较中被中的项目在后续比较中被掉弃了。类似地，如果掉弃了。类似地，如果xA7xA7，可以把，可以把，可以把，可以把A1.7A1.7掉弃。掉弃。掉弃。掉弃。在剩余元素在剩余元素在剩余元素在剩余元素A8.14A8.14中搜索中搜索中搜索中搜索x=22x=22，AA (8+14)/2(8+14)/2 =A11=23=A11=23，由于由于由于由于xA11xA9xA9，可以把，可以把，可以把，可以把A8.9A8.9掉弃。掉弃。掉弃。掉弃。留在序列中仅剩一个项目留在序列中仅剩一个项目留在序列中仅剩一个项目留在序列中仅剩一个项目A10=22A10=22，最后找到，最后找到，最后找到，最后找到x=A10 x=A10，搜索，搜索，搜索，搜索成功完毕（若成功完毕（若成功完毕（若成功完毕（若xA10 xA10，则，则，则，则lowlow highhigh条件不成立，出循环）。条件不成立，出循环）。条件不成立，出循环）。条件不成立，出循环）。10101212 1515 2222A8.10=A8.10=8 9 8 9 10 1018二分搜索法分析二分搜索法分析二分搜索法分析二分搜索法分析 假定每个三向比较假定每个三向比较假定每个三向比较假定每个三向比较(if-then-else)(if-then-else)计为一次比较，显然最小比较次计为一次比较，显然最小比较次计为一次比较，显然最小比较次计为一次比较，显然最小比较次数为数为数为数为1 1，即搜索元素，即搜索元素，即搜索元素，即搜索元素x x在序列中间位置。为了计算最大比较次数，在序列中间位置。为了计算最大比较次数，在序列中间位置。为了计算最大比较次数，在序列中间位置。为了计算最大比较次数，不失一般性，可假定不失一般性，可假定不失一般性，可假定不失一般性，可假定xAhigh xAhigh。第第第第2 2次迭代（循环）前数组次迭代（循环）前数组次迭代（循环）前数组次迭代（循环）前数组A A中剩余元素中剩余元素中剩余元素中剩余元素若若若若n n是偶数，是偶数，是偶数，是偶数，AAmid+1mid+1.n.n共有共有共有共有n/2n/2个元素。个元素。个元素。个元素。若若若若n n是奇数，是奇数，是奇数，是奇数，AAmid+1mid+1.n.n共有共有共有共有(n-1)/2(n-1)/2个元素。个元素。个元素。个元素。二种情况都有：二种情况都有：二种情况都有：二种情况都有：AAmid+1mid+1.n=.n=n/2n/2 =n/2n/22-12-1 第第第第3 3次迭代（循环）前数组次迭代（循环）前数组次迭代（循环）前数组次迭代（循环）前数组A A中剩余元素中剩余元素中剩余元素中剩余元素 n/2n/2 /2/2 =n/4n/4 =n/2n/22 2 =n/2n/23-13-1 第第第第j j次迭代（循环）前数组次迭代（循环）前数组次迭代（循环）前数组次迭代（循环）前数组A A中剩余元素中剩余元素中剩余元素中剩余元素 n/2n/2j-1j-1 不管找到与否，搜索不管找到与否，搜索不管找到与否，搜索不管找到与否，搜索x x的终止条件是余下元素仅仅为的终止条件是余下元素仅仅为的终止条件是余下元素仅仅为的终止条件是余下元素仅仅为1 1个，即个，即个，即个，即 n/2n/2j-1j-1 =1=1n=10,mid=n=10,mid=(10+1)/2(10+1)/2 =5,=5,剩余元素剩余元素剩余元素剩余元素A6.10A6.10，共计，共计，共计，共计5 5个个个个(10/210/2 )。n=11,mid=n=11,mid=(11+1)/2(11+1)/2 =6,=6,剩余元素剩余元素剩余元素剩余元素A7.11A7.11，共计，共计，共计，共计5 5个个个个(11/211/2 )。19 当当当当 n/2n/2j-1j-1 =1=1，j j为最大迭代次数（或称最大循环次数、或称为最大迭代次数（或称最大循环次数、或称为最大迭代次数（或称最大循环次数、或称为最大迭代次数（或称最大循环次数、或称最大比较次数）最大比较次数）最大比较次数）最大比较次数）n/2n/2j-1j-1 1 1等价于等价于等价于等价于1n/21n/2j-1j-12 2等价于等价于等价于等价于2 2j-1j-1nn2 2j j等价于（取对数）等价于（取对数）等价于（取对数）等价于（取对数）j-1Logj-1Log2 2n nj j考虑考虑考虑考虑 LogLog2 2n n LogLog2 2n n LogLog2 2n n +1+1因为因为因为因为j j是整数，故有是整数，故有是整数，故有是整数，故有j-1j-1 LogLog2 2n n 或或或或 j j LogLog2 2n n +1+1二者均有二者均有二者均有二者均有j j LogLog2 2n n +1+120107 7 5 23111111 18159 932 4 7 91222101027351414 可将二分搜索法的执行描述为决策树，红色的结点是与可将二分搜索法的执行描述为决策树，红色的结点是与可将二分搜索法的执行描述为决策树，红色的结点是与可将二分搜索法的执行描述为决策树，红色的结点是与x=22x=22相比较的数字。相比较的数字。相比较的数字。相比较的数字。序列：序列：序列：序列：1 4 5 7 8 9 10 12 15 22 23 27 32 351 4 5 7 8 9 10 12 15 22 23 27 32 35 loglog2 21414 +1+1=4=421uu比较次数是指元素比较次数，所以在比较次数是指元素比较次数，所以在比较次数是指元素比较次数，所以在比较次数是指元素比较次数，所以在whilewhile语句中的非元素比较语句中的非元素比较语句中的非元素比较语句中的非元素比较次数，通常不予计入次数，通常不予计入次数，通常不予计入次数，通常不予计入 ；uu确切讲，比较次数是指布尔表达式确切讲，比较次数是指布尔表达式确切讲，比较次数是指布尔表达式确切讲，比较次数是指布尔表达式“x=Amid”x=Amid”的执行次数；的执行次数；的执行次数；的执行次数；uu由于由于由于由于if-then-elseif-then-else嵌套使用，实际元素比较最大次数应为循环（迭嵌套使用，实际元素比较最大次数应为循环（迭嵌套使用，实际元素比较最大次数应为循环（迭嵌套使用，实际元素比较最大次数应为循环（迭代）次数的代）次数的代）次数的代）次数的2 2倍，即倍，即倍，即倍，即2(2(LogLog2 2n n +1)+1)。x x首先与首先与首先与首先与1010比较，由于比较，由于比较，由于比较，由于2222比比比比1010大，故下一步在右子树中寻找；大，故下一步在右子树中寻找；大，故下一步在右子树中寻找；大，故下一步在右子树中寻找；以此类推，直至；以此类推，直至；以此类推，直至；以此类推，直至2222。由于决策树的高度为。由于决策树的高度为。由于决策树的高度为。由于决策树的高度为 LogLog2 2n n ，所以，所以，所以，所以二分搜索法的最大比较次数为二分搜索法的最大比较次数为二分搜索法的最大比较次数为二分搜索法的最大比较次数为 LogLog2 2n n +1+1。定理定理1.1（Page 6）对于一个大小为对于一个大小为n的已排序数组，算法的已排序数组，算法BinarySearch 执行比较的最大次数为执行比较的最大次数为:Log2n +1容易看出，在最坏的情况下，第一个算法要检测容易看出，在最坏的情况下，第一个算法要检测A的所有的所有n个分量才能判断在个分量才能判断在A中找不到等于中找不到等于x的的分量；分量；在第二个算法中，最坏的情况下最多只要测在第二个算法中，最坏的情况下最多只要测A中中的的j+1(j=log2n)个分量，就判断个分量，就判断x是否在是否在A中，第中，第一个算法和第二个算法解决的是同一个问题，但一个算法和第二个算法解决的是同一个问题，但在最坏的情况下（所给定的在最坏的情况下（所给定的x不在不在A中），两个中），两个算法所检测的分量个数却大不相同，前者要算法所检测的分量个数却大不相同，前者要n=2j个，后者只要个，后者只要j+1个，可见第二个算法比第一个个，可见第二个算法比第一个算法高效得多。算法高效得多。因此，解决同一个问题，算法不同，计算的工作因此，解决同一个问题，算法不同，计算的工作量也不同，所需的计算时间随之不同，即算法的量也不同，所需的计算时间随之不同，即算法的时间复杂性不同。时间复杂性不同。2223选择排序法选择排序法选择算法选择算法 假定有一个数组假定有一个数组假定有一个数组假定有一个数组A1.nA1.n，Ai.nAi.n是它的一个子数组，是它的一个子数组，是它的一个子数组，是它的一个子数组，1i1in n。编。编。编。编写一函数，作用为：从写一函数，作用为：从写一函数，作用为：从写一函数，作用为：从Ai.n Ai.n 中选择一个最小的数中选择一个最小的数中选择一个最小的数中选择一个最小的数AkAk（i i knkn），将，将，将，将AiAi和和和和AkAk互换（若互换（若互换（若互换（若k ki i，无需交换）。，无需交换）。，无需交换）。，无需交换）。过程过程过程过程SelectionSelection（参见（参见（参见（参见Page 8Page 8）输入：输入：输入：输入：Ai.nAi.n输出：输出：输出：输出：Ai.nAi.n，其中，其中，其中，其中AiAi为为为为Ai.nAi.n中的最小的数。中的最小的数。中的最小的数。中的最小的数。0.procedure Selection(i)0.procedure Selection(i)1.1.kiki2.2.for ji+1 to nfor ji+1 to n3.3.if AjAk then kjif Aj0)and(Ajx)4.Aj+1Aj 5.jj-16.end while 7.Aj+1x8.end procedure29插入排序算法插入排序算法 设设设设A1.nA1.n为为为为n n个元素的数组，插入排序算法描述如下：个元素的数组，插入排序算法描述如下：个元素的数组，插入排序算法描述如下：个元素的数组，插入排序算法描述如下：从子数组从子数组从子数组从子数组A1A1开始，单个数可认为有序；开始，单个数可认为有序；开始，单个数可认为有序；开始，单个数可认为有序；接下来，将接下来，将接下来，将接下来，将A2A2插入到插入到插入到插入到A1A1的前面或后面，使得的前面或后面，使得的前面或后面，使得的前面或后面，使得A1.2A1.2有序；有序；有序；有序；然后，再将然后，再将然后，再将然后，再将A3A3插入到插入到插入到插入到A1.2A1.2中，使得中，使得中，使得中，使得A1.3A1.3有序；有序；有序；有序；直到直到直到直到AnAn插入到插入到插入到插入到A1.A1.n-1n-1，使得，使得，使得，使得A1.nA1.n有序。有序。有序。有序。算法算法算法算法1.6 InsertionSort(1.6 InsertionSort(参见参见参见参见Page 8-9)Page 8-9)输入：数组输入：数组输入：数组输入：数组A1.nA1.n输出：按升序排列的数组输出：按升序排列的数组输出：按升序排列的数组输出：按升序排列的数组A1.nA1.n1.1.for i2 to nfor i2 to n2.2.Insertion(i)Insertion(i)3 end for3 end for30插入排序算法分析插入排序算法分析 执行执行执行执行InsertionSortInsertionSort，元素比较次数取决于输入元素的，元素比较次数取决于输入元素的，元素比较次数取决于输入元素的，元素比较次数取决于输入元素的顺序。顺序。顺序。顺序。当元素已按升序排列时，元素比较次数最小，仅为当元素已按升序排列时，元素比较次数最小，仅为当元素已按升序排列时，元素比较次数最小，仅为当元素已按升序排列时，元素比较次数最小，仅为n-1n-1，每个元素，每个元素，每个元素，每个元素AiAi（2in2in）只和）只和）只和）只和Ai-1Ai-1比较。比较。比较。比较。当元素已按降序排列，并且所有元素各不相同，比较当元素已按降序排列，并且所有元素各不相同，比较当元素已按降序排列，并且所有元素各不相同，比较当元素已按降序排列，并且所有元素各不相同，比较次数为最大。如下所示：次数为最大。如下所示：次数为最大。如下所示：次数为最大。如下所示：因为每个元素因为每个元素因为每个元素因为每个元素Ai(2in)Ai(2in)都和子序列都和子序列都和子序列都和子序列A1.A1.i-1i-1 中的每中的每中的每中的每个元素比较，这一结果与算法个元素比较，这一结果与算法个元素比较，这一结果与算法个元素比较，这一结果与算法SelectionSortSelectionSort相一致。相一致。相一致。相一致。31观察结论观察结论1.4（Page 9）执行算法执行算法InsertionSort的元素比较次数在的元素比较次数在n-1到到n(n-1)/2之间。之间。元素赋值次数等于元素比较次数加上元素赋值次数等于元素比较次数加上n-1，即，即2(n-1)至至n(n-1)/2+(n-1)之间。之间。32“选择排序法选择排序法”和和“插入排序法插入排序法”小结小结(1)(1)选择排序法（往后选择）选择排序法（往后选择）选择排序法（往后选择）选择排序法（往后选择）Seletion(i)Seletion(i)从从从从AAi.ni.n 中选择一个最小的数（中选择一个最小的数（中选择一个最小的数（中选择一个最小的数（1 1 in-1in-1），将其和），将其和），将其和），将其和AiAi交换，显然交换，显然交换，显然交换，显然AiAi-1AiAi-1（当（当（当（当i2i2时），故时），故时），故时），故A1.iA1.i有序。然有序。然有序。然有序。然后后后后i i增增增增1 1，排序过程直至，排序过程直至，排序过程直至，排序过程直至i=n-1i=n-1结束。结束。结束。结束。(2)(2)插入排序法（向前插入）插入排序法（向前插入）插入排序法（向前插入）插入排序法（向前插入）Insertion(i)Insertion(i)A A1.1.i-1i-1 已有序（已有序（已有序（已有序（2 2 i i n n），将），将），将），将AiAi中的元素插入到中的元素插入到中的元素插入到中的元素插入到A1.A1.i-1i-1 中一个的合适位置，使得中一个的合适位置，使得中一个的合适位置，使得中一个的合适位置，使得A1.iA1.i有序。然后有序。然后有序。然后有序。然后i i增增增增1 1，排序过程直至，排序过程直至，排序过程直至，排序过程直至i=ni=n结束。结束。结束。结束。33合并二个已排序的表合并二个已排序的表算法描述算法描述 假定有一个数组假定有一个数组假定有一个数组假定有一个数组A1.mA1.m，p p，q q，r r是它的三个索引，并有是它的三个索引，并有是它的三个索引，并有是它的三个索引，并有1pqrm1pqrm，二个子数组，二个子数组，二个子数组，二个子数组Ap.qAp.q和和和和Aq+1.rAq+1.r各自按升序排列，重各自按升序排列，重各自按升序排列，重各自按升序排列，重新排列新排列新排列新排列A A中元素的位置，使得子数组中元素的位置，使得子数组中元素的位置，使得子数组中元素的位置，使得子数组Ap.rAp.r按升序排列。按升序排列。按升序排列。按升序排列。使用二个指针使用二个指针使用二个指针使用二个指针s s和和和和t t，初始化时，初始化时，初始化时，初始化时s=ps=p、t=q+1t=q+1，s s和和和和t t各自指向各自指向各自指向各自指向ApAp和和和和Aq+1Aq+1，空数组，空数组，空数组，空数组Bp.rBp.r用作暂存器；用作暂存器；用作暂存器；用作暂存器；每一次比较元素每一次比较元素每一次比较元素每一次比较元素AsAs和和和和AtAt，将小的元素添加到，将小的元素添加到，将小的元素添加到，将小的元素添加到B B中。然后更新中。然后更新中。然后更新中。然后更新指针，若指针，若指针，若指针，若AsAtAsAt，则，则，则，则s s加加加加1 1，否则，否则，否则，否则t t加加加加1 1；当当当当s=q+1s=q+1，说明子数组，说明子数组，说明子数组，说明子数组Ap.qAp.q的全部元素已进入的全部元素已进入的全部元素已进入的全部元素已进入B B，无需再比较，无需再比较，无需再比较，无需再比较，此时把子数组余下部分此时把子数组余下部分此时把子数组余下部分此时把子数组余下部分At.rAt.r添加到添加到添加到添加到B B中；中；中；中；当当当当t=r+1t=r+1，说明子数组，说明子数组，说明子数组，说明子数组Aq+1.rAq+1.r的全部元素已进入的全部元素已进入的全部元素已进入的全部元素已进入B B，无需再比，无需再比，无需再比，无需再比较，此时把子数组余下部分较，此时把子数组余下部分较，此时把子数组余下部分较，此时把子数组余下部分As.qAs.q添加到添加到添加到添加到B B中；中；中；中；最后将最后将最后将最后将Bp.rBp.r复制到复制到复制到复制到Ap.rAp.r。34过程过程过程过程Merge(A1.m,p,q,r)Merge(A1.m,p,q,r)（Page 6-7Page 6-7）输入：数组输入：数组输入：数组输入：数组A1.mA1.m和它的三个索引和它的三个索引和它的三个索引和它的三个索引p,q,rp,q,r（1pq1pqrmrm），二个子），二个子），二个子），二个子数组数组数组数组Ap.qAp.q和和和和AAq+1q+1.r.r各自按升序排列。各自按升序排列。各自按升序排列。各自按升序排列。输出：子数组输出：子数组输出：子数组输出：子数组Ap.rAp.r按升序排列。按升序排列。按升序排列。按升序排列。ment:Bp.rcomment:Bp.r为辅助数组为辅助数组为辅助数组为辅助数组/或或或或B1.mB1.m2.2.sp:tq+1:kp sp:tq+1:kp/s/s和和和和t t分别指向数组分别指向数组分别指向数组分别指向数组A A二个子数组元素二个子数组元素二个子数组元素二个子数组元素3.3.while(sq)and(tr)while(sq)and(tr)/k/k指向数组指向数组指向数组指向数组B B当前空白元素位置当前空白元素位置当前空白元素位置当前空白元素位置4.4.if AsAt then BkAs:ss+1if AsAt then BkAs:ss+15.5.else BkAt:tt+1else BkAt:tt+16.6.end ifend if7.7.kk+1kk+1/指向数组指向数组指向数组指向数组B B下一个空白位置下一个空白位置下一个空白位置下一个空白位置8.8.end whileend while9.9.if s=q+1 then Bk.rAt.r if s=q+1 then Bk.rAt.r /子数组子数组子数组子数组Ap.qAp.q元素已处理完元素已处理完元素已处理完元素已处理完10.10.else Bk.rAs.q else Bk.rAs.q/否则否则否则否则t=r+1,t=r+1,子数组子数组子数组子数组AAq+1q+1.r.r已处理完。已处理完。已处理完。已处理完。11.11.end ifend if12.12.Ap.r Bp.rAp.r Bp.r/复制复制复制复制352 2 3 3 1616 7 7 1111 1313 4545 5757q qr=8r=8k=1k=1t=4t=4s=1s=1p pAp.r=Ap.q+AAp.r=Ap.q+Aq+1q+1.r.r =2,3,16+7,11,13,45,57 =2,3,16+7,11,13,45,57Bp.r=2,3,7,11,13,16,45,57Bp.r=2,3,7,11,13,16,45,5736算法分析算法分析 设有个数分别为设有个数分别为设有个数分别为设有个数分别为n n1 1和和和和n n2 2的二个子数组的二个子数组的二个子数组的二个子数组n n1 1+n+n2 2=n=n，如果，如果，如果，如果子数组子数组子数组子数组Ap.qAp.q中每个元素均小于另一个子数组中每个元素均小于另一个子数组中每个元素均小于另一个子数组中每个元素均小于另一个子数组Aq+1,rAq+1,r中的所有元素，例，要合并下面二个子数组：中的所有元素，例，要合并下面二个子数组：中的所有元素，例，要合并下面二个子数组：中的所有元素，例，要合并下面二个子数组：2 2 3 3 6 67 7 1111 1313 4545 5757 该算法只需执行该算法只需执行该算法只需执行该算法只需执行3 3次比较，即次比较，即次比较，即次比较，即n n1 1次比较。次比较。次比较。次比较。另一方面，比较次数最多为另一方面，比较次数最多为另一方面，比较次数最多为另一方面，比较次数最多为n-1=nn-1=n1 1+n+n2 2-1-1次。例如要次。例如要次。例如要次。例如要合并下面二个子数组：合并下面二个子数组：合并下面二个子数组：合并下面二个子数组：2 2 3 3 66667 7 1111 1313 4545 5757就需要就需要就需要就需要7 7次比较。所以，算法次比较。所以，算法次比较。所以，算法次比较。所以，算法MergeMerge的最少比较次数是的最少比较次数是的最少比较次数是的最少比较次数是n n1 1，最大比较次数为，最大比较次数为，最大比较次数为，最大比较次数为n-1n-1。37观察结论观察结论1.1（Page 7）执行算法执行算法Merge，将个数分别为，将个数分别为n1和和n2的非的非空数组合并成一个为空数组合并成一个为n=n1+n2的排序数组。设的排序数组。设n1n2，元素的比较次数在，元素的比较次数在n1和和n-1之间。特例，之间。特例，如果二个数组大小为如果二个数组大小为 n/2 和和 n/2 ，需要比较的，需要比较的最大次数在最大次数在 n/2 和和n-1之间。之间。观察结论观察结论1.2（Page 7）执行算法执行算法Merge，将个数分别为，将个数分别为n1和和n2的非的非空数组合并成一个为空数组合并成一个为n=n1+n2的排序数组，元的排序数组，元素的赋值次数恰好是素的赋值次数恰好是2n。382 2 4 4 5 5 9 99 94 45 52 21 17 74 46 64 4 9 92 2 5 51 1 7 74 4 6 61 1 4 4 6 6 7 71 1 2 2 4 4 4 4 5 5 6 6 7 7 9 9自底向上合并排序自底向上合并排序引入引入 插入和选择排序法的最大比较次数都与插入和选择排序法的最大比较次数都与插入和选择排序法的最大比较次数都与插入和选择排序法的最大比较次数都与n n2 2成正比，成正比，成正比，成正比，从这个意义上来说二种算法的效率都是比较低的，考虑从这个意义上来说二种算法的效率都是比较低的，考虑从这个意义上来说二种算法的效率都是比较低的，考虑从这个意义上来说二种算法的效率都是比较低的，考虑下面的排序方法：下面的排序方法：下面的排序方法：下面的排序方法：39自底向上合并排序算法自底向上合并排序算法 设设设设A1.nA1.n为需排序的为需排序的为需排序的为需排序的n n个元素的数组个元素的数组个元素的数组个元素的数组第第第第1 1次迭代次迭代次迭代次迭代 生成个数为生成个数为生成个数为生成个数为2 2（=2=21 1）的排序序列，该序列共有）的排序序列，该序列共有）的排序序列，该序列共有）的排序序列，该序列共有 =个。若剩余个。若剩余个。若剩余个。若剩余1 1个元素，则让它进入下一轮合并。个元素，则让它进入下一轮合并。个元素，则让它进入下一轮合并。个元素，则让它进入下一轮合并。9 94 45 52 21 17 74 46 64 4 9 92 2 5 51 1 7 74 4 6 69 94 45 52 21 17 74 44 4 9 92 2 5 51 1 7 74 440第第第第2 2次迭代次迭代次迭代次迭代 生成个数为生成个数为生成个数为生成个数为4 4（=2=22 2）的排序序列，共有）的排序序列，共有）的排序序列，共有）的排序序列，共有 =个。若个。若个。若个。若剩余剩余剩余剩余1 1或或或或2 2个，则让它进入下一轮合并。如果剩余个，则让它进入下一轮合并。如果剩余个，则让它进入下一轮合并。如果剩余个，则让它进入下一轮合并。如果剩余3 3个，个，个，个，则将则将则将则将2 2个元素（已排序）和另外个元素（已排序）和另外个元素（已排序）和另外个元素（已排序）和另外1 1个元素合并成一个个元素合并成一个个元素合并成一个个元素合并成一个3 3元元元元素的排序序列。素的排序序列。素的排序序列。素的排序序列。2 2 4 4 5 5 9 94 4 9 92 2 5 51 1 7 74 4 6 61 1 4 4 6 6 7 72 2 4 4 5 5 9 94 4 9 92 2 5 51 1 7 74 41 1 4 4 7 741剩余元素为剩余元素为剩余元素为剩余元素为7 7个个个个 第第第第j j次迭代（假设次迭代（假设次迭代（假设次迭代（假设j=3j=3）生成元素个数为生成元素个数为生成元素个数为生成元素个数为2 2j j个的排序序列，该序列共有个的排序序列，该序列共有个的排序序列，该序列共有个的排序序列，该序列共有 个。个。个。个。可能剩余的元素个数可能剩余的元素个数可能剩余的元素个数可能剩余的元素个数r r，其大小在，其大小在，其大小在，其大小在1 1至至至至2 2j j-1-1之间之间之间之间(j=3,r=1-7)(j=3,r=1-7)。u若若若若1r 21r 2j j-1(j=3,r=1-4)-1(j=3,r=1-4)，则让它们进入下一次合并（局，则让它们进入下一次合并（局，则让它们进入下一次合并（局，则让它们进入下一次合并（局部已有序）。部已有序）。部已有序）。部已有序）。u若若若若2 2j j-1-1r r2 2j j(j=3,r=5-7)(j=3,r=5-7)，则将，则将，则将，则将2 2j j-1-1个元素（局部已有序）个元素（局部已有序）个元素（局部已有序）个元素（局部已有序）和另外和另外和另外和另外r-2r-2j j-1-1个元素（局部已有序）合并成个数为个元素（局部已有序）合并成个数为个元素（局部已有序）合并成个数为个元素（局部已有序）合并成个数为r r的的的的排序序列。排序序列。排序序列。排序序列。2 2 4 4 5 5 9 91 1 4 4 6 6 7 71 1 2 2 4 4 4 4 5 5 6 6 7 7 9 92 2 4 4 5 5 9 91 1 4 4 7 71 1 2 2 4 4 4 4 5 5 7 7 9 9总的迭代次数总的迭代次数总的