程序设计基础 (2)优秀PPT.ppt

程序设计基础现在学习的是第1页，共70页11.1 算法的概念与特征算法的由来算法的由来解决问题的方法与步骤解决问题的方法与步骤演算过程的抽象表述演算过程的抽象表述算法的基本特征算法的基本特征有穷性：算法必须能够在有限步内终止有穷性：算法必须能够在有限步内终止确定性确定性：每一步骤的顺序和内容不能有二义性每一步骤的顺序和内容不能有二义性有效性：所有操作都有明确含义并能够实现有效性：所有操作都有明确含义并能够实现有零个或多个输入：算法应该接受处理数据有零个或多个输入：算法应该接受处理数据有一个或多个输出：算法必须能够输出结果有一个或多个输出：算法必须能够输出结果正确性不是算法的特征，算法的正确性不是算法的特征，算法的正确性不是算法的特征，算法的正确性不是算法的特征，算法的正确性由设计者保证！正确性由设计者保证！正确性由设计者保证！正确性由设计者保证！现在学习的是第2页，共70页算法举例一3 3 幻方幻方用数字用数字19组成组成3 3方阵，各行各列各对角线的数方阵，各行各列各对角线的数字之和为字之和为15算法步骤算法步骤S1：把把1放在第一行中间的一格放在第一行中间的一格S2：在右上方斜对角线方向给出下一个自然数在右上方斜对角线方向给出下一个自然数 在此过程中，若该数已出方框，则将其写在该行或该在此过程中，若该数已出方框，则将其写在该行或该在此过程中，若该数已出方框，则将其写在该行或该在此过程中，若该数已出方框，则将其写在该行或该列另一端列另一端列另一端列另一端S3：写完三个数后，将第四个数写在第三个数下写完三个数后，将第四个数写在第三个数下S4：重复上述操作，重复上述操作，直到格子填满为止直到格子填满为止现在学习的是第3页，共70页算法举例一1现在学习的是第4页，共70页算法举例一21现在学习的是第5页，共70页算法举例一212现在学习的是第6页，共70页算法举例一2132现在学习的是第7页，共70页算法举例一21332现在学习的是第8页，共70页算法举例一213342现在学习的是第9页，共70页算法举例一2135342现在学习的是第10页，共70页算法举例一21635342现在学习的是第11页，共70页算法举例一216357342现在学习的是第12页，共70页算法举例一2168357342现在学习的是第13页，共70页算法举例一28168357342现在学习的是第14页，共70页算法举例一928168357342现在学习的是第15页，共70页算法举例一9281683573492现在学习的是第16页，共70页算法举例一816357492现在学习的是第17页，共70页算法举例二查英文词典的算法步骤查英文词典的算法步骤S1：翻开词典任意一页翻开词典任意一页S2：若所查词汇在本页第一个单词前，则往前翻若所查词汇在本页第一个单词前，则往前翻页重复页重复S2；若所查词汇在本页最后一个单词后，若所查词汇在本页最后一个单词后，则往后翻页重复则往后翻页重复S2S3：若非若非S2的情况，则依次比较本页单词，或者的情况，则依次比较本页单词，或者查出该单词，或者得出结论，查不到该单词查出该单词，或者得出结论，查不到该单词现在学习的是第18页，共70页算法举例三素数判定的算法步骤素数判定的算法步骤S1：输入输入 n 的值的值S2：i=2S3：r=n/iS4：若若 r=0，则则 n 不是素数，结束；若不是素数，结束；若 r 0，执行执行S5S5：i=i+1S6：若若 i n 1，返回返回S3；否则判定；否则判定 n 为素数，为素数，结束结束现在学习的是第19页，共70页11.2 算法的类型与结构数值算法与非数值算法数值算法与非数值算法算法的基本结构算法的基本结构顺序结构顺序结构分支结构分支结构循环结构循环结构程序的结构化程序的结构化现在学习的是第20页，共70页11.3 算法的描述方法流程图流程图使用流线表示程序控制流使用流线表示程序控制流程序逻辑清晰，绘制复杂程序逻辑清晰，绘制复杂N-S图图去除流线与箭头的流程图去除流线与箭头的流程图绘制复杂，逻辑不清晰绘制复杂，逻辑不清晰伪代码伪代码程序逻辑较不清晰，书写简单程序逻辑较不清晰，书写简单现在学习的是第21页，共70页11.4 算法的设计与实现算法实现过程算法实现过程问题分析问题分析按某种策略实现算法按某种策略实现算法验证上述实现确实为算法验证上述实现确实为算法证明算法的正确性证明算法的正确性选择合适的策略，提高算法效率选择合适的策略，提高算法效率现在学习的是第22页，共70页素数判定问题函数原型函数原型int IsPrime(int n);素数判定问题的第二种算法素数判定问题的第二种算法检查检查 1 到到 n 的数中，是否存在可被的数中，是否存在可被 n 整除的数整除的数每找到一个因子，计数器自加每找到一个因子，计数器自加 1在所有数判断完毕后，查看计数器是否为在所有数判断完毕后，查看计数器是否为 2若为若为2则为素数，否则不是则为素数，否则不是现在学习的是第23页，共70页素数判定问题int int IsPrime(int n)int int divisors,i i;divisors=0;for(i i=1;i=n;i+)+)if(if(n%i=0)=0)divisorsdivisors+;+;return(return(divisors divisors=2);现在学习的是第24页，共70页素数判定问题验证上述策略确为算法验证上述策略确为算法操作步骤的描述清楚，不存在二义性操作步骤的描述清楚，不存在二义性各操作确实可计算机实现各操作确实可计算机实现执行过程可终止执行过程可终止算法正确性的证明算法正确性的证明素数至少有两个因子素数至少有两个因子divisors 表示数的因子个数，初始为表示数的因子个数，初始为 0，每找到，每找到一个因子，其值递增一个因子，其值递增 1，循环依次查找全部，循环依次查找全部 n 个个自然数，若只有两个因子，显然为素数自然数，若只有两个因子，显然为素数现在学习的是第25页，共70页素数判定问题提高算法效率提高算法效率只要在只要在 1 和和 n 之间存在一个因子就可终止，并返之间存在一个因子就可终止，并返回回 n 不是素数不是素数若若 n 可被可被 2 整除，不需检验其它数，程序终止并整除，不需检验其它数，程序终止并返回返回 n 不是素数；若否，则所有偶数都不是因子，不是素数；若否，则所有偶数都不是因子，程序只需检验奇数程序只需检验奇数程序不必检验因子一直到程序不必检验因子一直到 n，只需到只需到 即可即可现在学习的是第26页，共70页素数判定问题int int IsPrimeIsPrime(int n)int int i i;if(n n%2%2 =0)return 0;for(for(i=3;=3;i i=sqrtsqrt(n n););i i+=2)if(if(n n%i=0)=0)return 0;return 1;return 1;问题：本算法效率确实好吗？问题：本算法效率确实好吗？问题：本算法效率确实好吗？问题：本算法效率确实好吗？每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时现在学习的是第27页，共70页素数判定问题int int IsPrimeIsPrime(int(int n)int limitlimit,i;limitlimit=sqrt(n););if(if(n%2=0)return 0;return 0;for(i=3;i=limitlimit;i i+=2)if(if(n%i i=0)=0)return 0;return 0;return 1;问题：本算法确实正确吗？问题：本算法确实正确吗？问题：本算法确实正确吗？问题：本算法确实正确吗？浮点数的存储有误差，程序的正确性依赖机浮点数的存储有误差，程序的正确性依赖机浮点数的存储有误差，程序的正确性依赖机浮点数的存储有误差，程序的正确性依赖机器的表示精度器的表示精度器的表示精度器的表示精度现在学习的是第28页，共70页素数判定问题int IsPrimeIsPrime(int(int n)int limitlimit,i i;limit=sqrtsqrt(n)+1;if(n%2=0)=0)return 0;for(i i=3;i=limit;i i+=2)if(if(n%i=0)=0)return 0;return 0;return 1;现在学习的是第29页，共70页如何选择合适的算法选择指标选择指标正确性正确性效率效率可读性可读性可维护性可维护性算法评估：在诸多因素中寻找平衡点算法评估：在诸多因素中寻找平衡点高效的算法可读性差，可读性好的算法效率一般高效的算法可读性差，可读性好的算法效率一般不高不高现在学习的是第30页，共70页最大公约数问题函数原型函数原型int gcd(int x,int y);两种算法实现策略两种算法实现策略穷举法：逐一尝试所有可能值穷举法：逐一尝试所有可能值欧几里德算法欧几里德算法 步骤步骤步骤步骤1 1：x x 除以除以除以除以 y y，余数为，余数为，余数为，余数为 r r 步骤步骤步骤步骤2 2：若：若：若：若 r r 为为为为 0 0，则，则，则，则 n n 为所求，算法终止；否则为所求，算法终止；否则为所求，算法终止；否则为所求，算法终止；否则 步骤步骤步骤步骤3 3：将：将：将：将 y y 作为新作为新作为新作为新 x x，r r 作为新作为新作为新作为新 y y，返回第，返回第，返回第，返回第1 1步步步步现在学习的是第31页，共70页最大公约数问题穷举法实现穷举法实现int gcd(int(int x,int y y)int g g;g g=x;while(x%g g!=0|!=0|y%g!=0)!=0)g g;return g g;现在学习的是第32页，共70页最大公约数问题欧几里德算法欧几里德算法实现实现int gcd(int(int x,int ,int y)int int r;while(1)r r=x x%y;if(r=0)break;x x=y;y=r;return return y y;现在学习的是第33页，共70页11.5 算法分析与算法复杂度算法分析的目的算法分析的目的评估算法的执行效率评估算法的执行效率排序算法排序算法选择排序选择排序归并排序归并排序算法复杂度算法复杂度现在学习的是第34页，共70页选择排序函数原型函数原型void SortIntegerArray(int a,int n);基本原理基本原理依次找最小元，将最小元与数组未排序的第一位依次找最小元，将最小元与数组未排序的第一位互换互换重复上述步骤重复上述步骤现在学习的是第35页，共70页选择排序原始数组原始数组5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77第一趟第一趟1925375895567330a a00a a11a a22a a33a a44a a55a a66a a77第二趟第二趟1925375895567330a a00a a11a a22a a33a a44a a55a a66a a77现在学习的是第36页，共70页选择排序#include#includevoid void SortIntergeArraySortIntergeArray(int(int a a,int,int n n)int int lhlh,rhrh,i i,temptemp;for(for(lhlh=0;=0;lhlh n n;lhlh+)+)rhrh=lhlh;for(for(i i=lhlh+1;+1;i i n n;i i+)if(+)if(a a i i a a rhrh)rhrh=i i;temptemp=a a lhlh;a a lhlh=a a rhrh;a a rhrh=temptemp;void void mainmain()()int int i i,numbersnumbers8=56,25,37,58,95,19,73,30;8=56,25,37,58,95,19,73,30;SortIntegerArraySortIntegerArray(numbersnumbers,8);,8);for(for(i i=0;=0;i i 8;8;i i+)+)printfprintf(“%(“%7d7d”,”,numbersnumbers i i););现在学习的是第37页，共70页选择排序算法的性能分析程序执行时间程序执行时间 T 随问题规模随问题规模 n 显著增加显著增加算法的主要执行时间在于循环算法的主要执行时间在于循环循环执行次数循环执行次数(n2+n)/2算法执行时间的估计与测量算法执行时间的估计与测量平方级算法执行时间：平方级算法执行时间：T n2现在学习的是第38页，共70页算法复杂度算法复杂度的定义算法复杂度的定义算法的执行效率随问题规模算法的执行效率随问题规模的变化趋势的变化趋势算法复杂度的分类算法复杂度的分类时间复杂度：算法执行时间时间复杂度：算法执行时间空间复杂度：算法所需存储空间空间复杂度：算法所需存储空间现在学习的是第39页，共70页大 O 表达式算法复杂度的度量：大算法复杂度的度量：大 O 表达式表达式近似描述算法的本质近似描述算法的本质例：例：O(n2)表示算法复杂度与问题规模的平方近表示算法复杂度与问题规模的平方近似成正比似成正比原原 则则忽略所有对变化趋势影响较小的项忽略所有对变化趋势影响较小的项忽略所有常数因子忽略所有常数因子例：算法需要例：算法需要 2n+3n2 步骤才能完成，时间复杂度步骤才能完成，时间复杂度为为O(2n)现在学习的是第40页，共70页算法时间复杂度的估计时间复杂度计算时间复杂度计算 total 赋值赋值 1 次次i 赋值赋值 1 次；次；i n 执行执行 n+1 次；次；i+执行执行 n 次次循环体内部代码执行循环体内部代码执行 n 次次返回值执行返回值执行 1 次次总计：总计：3n+4 次；时间复杂度：次；时间复杂度：O(n)double double AverageAverage(double(double a a,int,int n n)int int i i;double;double totaltotal;totaltotal=0;=0;for(for(i i=0;=0;i i n n;i i+)+)totaltotal+=+=a a i i;return(return(totaltotal/n n););现在学习的是第41页，共70页最高复杂度与平均复杂度最高复杂度：算法在最坏情况下的复杂度最高复杂度：算法在最坏情况下的复杂度算法复杂度的上限：无论数据如何变化，算法的算法复杂度的上限：无论数据如何变化，算法的复杂度都不会差于最高复杂度复杂度都不会差于最高复杂度平均复杂度：算法在各种数据下的复杂度平平均复杂度：算法在各种数据下的复杂度平均值均值算法性能的最佳估计值算法性能的最佳估计值现在学习的是第42页，共70页最高复杂度与平均复杂度最高时间复杂度：最高时间复杂度：O(n)最好情况：最好情况：O(1)平均时间复杂度：平均时间复杂度：O(n)int int LinearSearch(int(int key,int,int a a,int,int n n)int i;for(i i=0;=0;i n;i+)if(key key=a ai)return i;return 1;1;现在学习的是第43页，共70页归并排序问题：选择排序复杂度与问题规模的平方成问题：选择排序复杂度与问题规模的平方成正比正比问题规模增加一倍，时间消耗变为问题规模增加一倍，时间消耗变为 4 倍倍问题规模减为一半，时间消耗减为问题规模减为一半，时间消耗减为 分治法分治法思路：将原始数组分成两个子数组，分别排序，思路：将原始数组分成两个子数组，分别排序，然后合并然后合并只要数组合并的时间小于排序算法的时间，分治只要数组合并的时间小于排序算法的时间，分治法就是有效的法就是有效的现在学习的是第44页，共70页归并排序原始数组原始数组5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77数组分解数组分解56253758a a00a a11a a22a a3395197330a a44a a55a a66a a77现在学习的是第45页，共70页归并排序原始数组原始数组5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77子数组排序子数组排序25375658a a00a a11a a22a a3319307395a a44a a55a a66a a77现在学习的是第46页，共70页归并排序原始数组原始数组5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77子数组排序（问题：子数组如何排序？）子数组排序（问题：子数组如何排序？）25375658a a00a a11a a22a a3319307395a a44a a55a a66a a77子数组归并子数组归并1925303756587395a a00a a11a a22a a33a a44a a55a a66a a77现在学习的是第47页，共70页归并排序子数组归并子数组归并25375658a a00a a11a a22a a3319307395a a44a a55a a66a a7719a a00a a11a a22a a33a a44a a55a a66a a77现在学习的是第48页，共70页归并排序子数组归并子数组归并25375658a a00a a11a a22a a3319307395a a44a a55a a66a a771925a a00a a11a a22a a33a a44a a55a a66a a77现在学习的是第49页，共70页归并排序子数组归并子数组归并25375658a a00a a11a a22a a3319307395a a44a a55a a66a a77192530a a00a a11a a22a a33a a44a a55a a66a a77现在学习的是第50页，共70页归并排序子数组归并子数组归并25375658a a00a a11a a22a a3319307395a a44a a55a a66a a77192530a a00a a11a a22a a33a a44a a55a a66a a77现在学习的是第51页，共70页归并排序子数组归并子数组归并25375658a a00a a11a a22a a3319307395a a44a a55a a66a a771925303756587395a a00a a11a a22a a33a a44a a55a a66a a77现在学习的是第52页，共70页归并排序 算法描述算法描述算法描述算法描述 判断数组是否为空或者只有单个元素。若是，则相当于已排序，判断数组是否为空或者只有单个元素。若是，则相当于已排序，判断数组是否为空或者只有单个元素。若是，则相当于已排序，判断数组是否为空或者只有单个元素。若是，则相当于已排序，函数直接返回。否则函数直接返回。否则函数直接返回。否则函数直接返回。否则 将该数组分割为两个子数组，每个子数组大小都是原数组的一半将该数组分割为两个子数组，每个子数组大小都是原数组的一半将该数组分割为两个子数组，每个子数组大小都是原数组的一半将该数组分割为两个子数组，每个子数组大小都是原数组的一半左右左右左右左右 使用同样的方法排序两个子数组使用同样的方法排序两个子数组使用同样的方法排序两个子数组使用同样的方法排序两个子数组 合并两个已排序的子数组合并两个已排序的子数组合并两个已排序的子数组合并两个已排序的子数组函数原型函数原型 void void SortIntegerArraySortIntegerArray(int(int a a,int,int lowlow,int,int highhigh););void void MergeMerge(int(int a a,int,int lowlow,int,int midmid,int,int highhigh););现在学习的是第53页，共70页归并排序void void SortIntegerArraySortIntegerArray(int(int a a,int,int lowlow,int,int high high)int int i i,tmptmp,midmid;if(if(high high=low low+1)+1)/only two numbers/only two numbers if(if(a a highhigh low low)/more than two numbers/more than two numbers midmid=(=(highhigh+lowlow)/2;)/2;/divide into two subarrays/divide into two subarrays SortIntegerArraySortIntegerArray(a a,lowlow,mid mid););/sort them respectively/sort them respectively SortIntegerArraySortIntegerArray(a a,midmid+1,+1,high high););MergeMerge(a a,lowlow,midmid,high high););/merge them/merge them 现在学习的是第54页，共70页归并排序void void MergeMerge(int(int a a,int,int lowlow,int,int midmid,int,int high high)int int i i,mm,n n;int*int*p p,*,*q q;p p=(int*)=(int*)mallocmalloc(sizeof(int)*(sizeof(int)*(high high low low+1);+1);m m=lowlow;n n=mid mid+1;+1;q q=p p;while(while(mm=midmid&n n=high high)if(if(a a mm a a n n)*q*q+=+=a a mm+;else +;else *q*q+=+=a a n n+;+;while(while(mm=mid mid)*q*q+=+=a a mm+;+;while(while(n n=highhigh)*)*q q+=+=a a n n+;+;for(for(i i=lowlow;i i=highhigh;i i+)+)a a i i=*=*p p+;+;freefree(p p););现在学习的是第55页，共70页归并排序 算法复杂度：归并排序的执行时间算法复杂度：归并排序的执行时间算法复杂度：归并排序的执行时间算法复杂度：归并排序的执行时间 执行当前函数内部指令的时间：与执行当前函数内部指令的时间：与执行当前函数内部指令的时间：与执行当前函数内部指令的时间：与 n n 成正比成正比成正比成正比 执行各层函数递归调用的时间执行各层函数递归调用的时间执行各层函数递归调用的时间执行各层函数递归调用的时间 算法复杂度的计算算法复杂度的计算算法复杂度的计算算法复杂度的计算 记总时间为记总时间为记总时间为记总时间为 T T(n n)，则，则，则，则 T T(1)=(1)=1 1；T T(n n)=)=n n+2+2T T(n n/2)/2)T T(n n/2)=/2)=n n/2+2/2+2T T(n n/4)/4)，即即即即 2 2T T(n n/2)=/2)=n n+4+4T T(n n/4)/4)T T(n n)=2)=2n n+4+4T T(n n/4)/4)，T T(n n)=3)=3n n+8+8T T(n n/8)/8)，T T(n n)=)=knkn+2+2k kT T(n n/2/2k k)2 2k k=n n，即即即即 k k=log=log2 2n n T T(n n)=)=n nloglog2 2n n+n n；故故故故 OO(n n)=)=n nloglog2 2n n 现在学习的是第56页，共70页标准复杂度类型常数级时间复杂度：常数级时间复杂度：O(1)对数级时间复杂度：对数级时间复杂度：O(log2n)线性级时间复杂度：线性级时间复杂度：O(n)nlog2n 级时间复杂度：级时间复杂度：O(nlog2n)平方级时间复杂度：平方级时间复杂度：O(n2)立方级时间复杂度：立方级时间复杂度：O(n3)指数级时间复杂度：指数级时间复杂度：O(2n)现在学习的是第57页，共70页11.6 常用算法设计与分析快速排序算法的基本原理：分解合并策略快速排序算法的基本原理：分解合并策略原始数组：一半元素大于原始数组：一半元素大于50，一半小于，一半小于505625375895197330a a00a a11a a22a a33a a44a a55a a66a a77通过运用合适的分解排序策略，将较小的元素放到通过运用合适的分解排序策略，将较小的元素放到数组前端，较大的元素放到数组的后端数组前端，较大的元素放到数组的后端2537193056589573a a00a a11a a22a a33a a44a a55a a66a a77对子数组进行递归排序，不需要子数组合并操作对子数组进行递归排序，不需要子数组合并操作现在学习的是第58页，共70页11.6 常用算法设计与分析快速排序算法的基本原理：分解合并策略快速排序算法的基本原理：分解合并策略如何恰当选择数组分解的基准值，使数组基本平如何恰当选择数组分解的基准值，使数组基本平均分成两部分？均分成两部分？5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77所选基准值应尽可能接近数组中间的某个值所选基准值应尽可能接近数组中间的某个值 合理地选择非常困难，一般直接使用数组的第一个元素，这合理地选择非常困难，一般直接使用数组的第一个元素，这合理地选择非常困难，一般直接使用数组的第一个元素，这合理地选择非常困难，一般直接使用数组的第一个元素，这里为里为里为里为 56 56；或取三四个数，使用中间的某个值；或取三四个数，使用中间的某个值；或取三四个数，使用中间的某个值；或取三四个数，使用中间的某个值现在学习的是第59页，共70页11.6 常用算法设计与分析快速排序算法描述快速排序算法描述 选择一个充当划分较小和较大元素的界线的元素，称为基准选择一个充当划分较小和较大元素的界线的元素，称为基准选择一个充当划分较小和较大元素的界线的元素，称为基准选择一个充当划分较小和较大元素的界线的元素，称为基准值值值值 将数组中的元素重新排列使得较大的元素向数组的末端移动，将数组中的元素重新排列使得较大的元素向数组的末端移动，将数组中的元素重新排列使得较大的元素向数组的末端移动，将数组中的元素重新排列使得较大的元素向数组的末端移动，较小的元素向数组的始端移动。如此在形式上将数组分成了较小的元素向数组的始端移动。如此在形式上将数组分成了较小的元素向数组的始端移动。如此在形式上将数组分成了较小的元素向数组的始端移动。如此在形式上将数组分成了两个部分，界线左边的元素都小于基准值，界线右边的元素两个部分，界线左边的元素都小于基准值，界线右边的元素两个部分，界线左边的元素都小于基准值，界线右边的元素两个部分，界线左边的元素都小于基准值，界线右边的元素都大于基准值。此过程称为分解都大于基准值。此过程称为分解都大于基准值。此过程称为分解都大于基准值。此过程称为分解 排序各个子数组排序各个子数组排序各个子数组排序各个子数组 因为基准值左边的元素都小于基准值右边的元素，所以排序各个子因为基准值左边的元素都小于基准值右边的元素，所以排序各个子因为基准值左边的元素都小于基准值右边的元素，所以排序各个子因为基准值左边的元素都小于基准值右边的元素，所以排序各个子数组后即使得整个数组有序数组后即使得整个数组有序数组后即使得整个数组有序数组后即使得整个数组有序 算法思路仍然为分解合并策略，故可用递归实现算法思路仍然为分解合并策略，故可用递归实现算法思路仍然为分解合并策略，故可用递归实现算法思路仍然为分解合并策略，故可用递归实现现在学习的是第60页，共70页11.6 常用算法设计与分析快速排序算法的执行模拟：基准值取首元素快速排序算法的执行模拟：基准值取首元素原始数组：一半元素大于或等于原始数组：一半元素大于或等于56，一半小于，一半小于565625375895197330a a00a a11a a22a a33a a44a a55a a66a a77现在学习的是第61页，共70页5625375895197330a a00a a11a a22a a33a a44a a55a a66a a7711.6 常用算法设计与分析 第一步：忽略基准值，用两个变量第一步：忽略基准值，用两个变量第一步：忽略基准值，用两个变量第一步：忽略基准值，用两个变量 lh 和和 rh 存放数组其存放数组其他部分的首下标和尾下标他部分的首下标和尾下标5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh现在学习的是第62页，共70页5625375895197330a a00a a11a a22a a33a a44a a55a a66a a7711.6 常用算法设计与分析 第二步：向左移动下标第二步：向左移动下标第二步：向左移动下标第二步：向左移动下标 rh 直到与直到与直到与直到与 lhlh 重叠或者其对应的重叠或者其对应的重叠或者其对应的重叠或者其对应的元素值小于基准值。本例中，元素值小于基准值。本例中，元素值小于基准值。本例中，元素值小于基准值。本例中，a7 7=30 为较小值，下为较小值，下标标 rh 不需移动不需移动5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh现在学习的是第63页，共70页11.6 常用算法设计与分析 第三步：向右移动下标第三步：向右移动下标第三步：向右移动下标第三步：向右移动下标 lh 直到与直到与 rhrh 重叠或者其对应重叠或者其对应的元素值大于基准值。本例中，向右移动下标的元素值大于基准值。本例中，向右移动下标 lhlh 直到指向了一个大于直到指向了一个大于 56 的元素的元素5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh现在学习的是第64页，共70页11.6 常用算法设计与分析 第四步：若下标第四步：若下标第四步：若下标第四步：若下标 lh 和和 rh 还没有指向同一个位置，交还没有指向同一个位置，交还没有指向同一个位置，交还没有指向同一个位置，交换它们所指向位置中的元素换它们所指向位置中的元素换它们所指向位置中的元素换它们所指向位置中的元素5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh5625373095197358a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh现在学习的是第65页，共70页11.6 常用算法设计与分析第五步：重复第二到第四步直到第五步：重复第二到第四步直到 lhlh 和和和和 rh 重合，如接重合，如接重合，如接重合，如接下来的操作中，第四步交换下来的操作中，第四步交换下来的操作中，第四步交换下来的操作中，第四步交换1919和和和和9595，再次执行时第二步，再次执行时第二步，再次执行时第二步，再次执行时第二步向左移动下标向左移动下标向左移动下标向左移动下标 rhrh，并且停在，并且停在 lh 处处处处5625373095197358a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh5625373019957358a a00a a11a a22a a33a a44a a55a a66a a77lhlh rhrh现在学习的是第66页，共70页11.6 常用算法设计与分析在大多数情况下，在大多数情况下，lhlh 和和 rhrh 重合处为较小元素，若该元重合处为较小元素，若该元重合处为较小元素，若该元重合处为较小元素，若该元素较大，则基准值必为最小值，界线在位置素较大，则基准值必为最小值，界线在位置素较大，则基准值必为最小值，界线在位置素较大，则基准值必为最小值，界线在位置0 0；若重合处；若重合处；若重合处；若重合处为较小元素，将其与基准值互换为较小元素，将其与基准值互换为较小元素，将其与基准值互换为较小元素，将其与基准值互换5625373019957358a a00a a11a a22a a33a a44a a55a a66a a77lhlh rhrh1925373056957358a a00a a11a a22a a33a a44a a55a a66a a77boundaryboundary现在学习的是第67页，共70页11.6 常用算法设计与分析static int static int PartitionPartition(int(int a a,int,int n n););void void SortIntegerArraySortIntegerArray(int(int a a,int,int n n)int int boundaryboundary;if(if(n n 2)return;2)return;boundaryboundary=ParititonParititon(a a,n n););SortIntegerArraySortIntegerArray(a a,boundaryboundary););SortIntegerArraySortIntegerArray(a a+boundary boundary+1,+1,n n boundaryboundary 1);1);现在学习的是第68页，共70页11.6 常用算法设计与分析static int static int PartitionPartition(int(int a a,int,int n n)int int lhlh,rhrh,pivotpivot,temptemp;pivotpivot=a a0;0;lhlh=1;=1;rhrh=n n 1;1;while(1)while(1)while(while(lhlh =pivot pivot)rhrh;while(while(lhlh rhrh&a a lhlh =pivot pivot)return 0;)return 0;a a0=0=a a lhlh;a a lhlh=pivotpivot;return;return lhlh;现在学习的是第69页，共70页作 业第第335335页：第二题（编程题）页：第二题（编程题）第第7 7小题小题第第336336页：第二题（编程题）页：第二题（编程题）第第1313、1414小题小题现在学习的是第70页，共70页