程序设计基础 (2)精选文档.ppt

《程序设计基础 (2)精选文档.ppt》由会员分享，可在线阅读，更多相关《程序设计基础 (2)精选文档.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、程序设计基础本讲稿第一页，共七十页11.1 算法的概念与特征算法的由来算法的由来解决问题的方法与步骤解决问题的方法与步骤演算过程的抽象表述演算过程的抽象表述算法的基本特征算法的基本特征有穷性：算法必须能够在有限步内终止有穷性：算法必须能够在有限步内终止确定性确定性：每一步骤的顺序和内容不能有二义性每一步骤的顺序和内容不能有二义性有效性：所有操作都有明确含义并能够实现有效性：所有操作都有明确含义并能够实现有零个或多个输入：算法应该接受处理数据有零个或多个输入：算法应该接受处理数据有一个或多个输出：算法必须能够输出结果有一个或多个输出：算法必须能够输出结果正确性不是算法的特征，算法正确性不是算法的

2、特征，算法正确性不是算法的特征，算法正确性不是算法的特征，算法的正确性由设计者保证！的正确性由设计者保证！的正确性由设计者保证！的正确性由设计者保证！本讲稿第二页，共七十页算法举例一3 3 幻方幻方用数字用数字19组成组成3 3方阵，各行各列各对角线的数方阵，各行各列各对角线的数字之和为字之和为15算法步骤算法步骤S1：把把1放在第一行中间的一格放在第一行中间的一格S2：在右上方斜对角线方向给出下一个自然数在右上方斜对角线方向给出下一个自然数 在此过程中，若该数已出方框，则将其写在该行或该在此过程中，若该数已出方框，则将其写在该行或该在此过程中，若该数已出方框，则将其写在该行或该在此过程中，若

3、该数已出方框，则将其写在该行或该列另一端列另一端列另一端列另一端S3：写完三个数后，将第四个数写在第三个数下写完三个数后，将第四个数写在第三个数下S4：重复上述操作，重复上述操作，直到格子填满为止直到格子填满为止本讲稿第三页，共七十页算法举例一1本讲稿第四页，共七十页算法举例一21本讲稿第五页，共七十页算法举例一212本讲稿第六页，共七十页算法举例一2132本讲稿第七页，共七十页算法举例一21332本讲稿第八页，共七十页算法举例一213342本讲稿第九页，共七十页算法举例一2135342本讲稿第十页，共七十页算法举例一21635342本讲稿第十一页，共七十页算法举例一216357342本讲稿第

4、十二页，共七十页算法举例一2168357342本讲稿第十三页，共七十页算法举例一28168357342本讲稿第十四页，共七十页算法举例一928168357342本讲稿第十五页，共七十页算法举例一9281683573492本讲稿第十六页，共七十页算法举例一816357492本讲稿第十七页，共七十页算法举例二查英文词典的算法步骤查英文词典的算法步骤S1：翻开词典任意一页翻开词典任意一页S2：若所查词汇在本页第一个单词前，则往前翻若所查词汇在本页第一个单词前，则往前翻页重复页重复S2；若所查词汇在本页最后一个单词后，若所查词汇在本页最后一个单词后，则往后翻页重复则往后翻页重复S2S3：若非若非S2的

5、情况，则依次比较本页单词，或者的情况，则依次比较本页单词，或者查出该单词，或者得出结论，查不到该单词查出该单词，或者得出结论，查不到该单词本讲稿第十八页，共七十页算法举例三素数判定的算法步骤素数判定的算法步骤S1：输入输入 n 的值的值S2：i=2S3：r=n/iS4：若若 r=0，则则 n 不是素数，结束；若不是素数，结束；若 r 0，执行执行S5S5：i=i+1S6：若若 i n 1，返回返回S3；否则判定；否则判定 n 为素数，为素数，结束结束本讲稿第十九页，共七十页11.2 算法的类型与结构数值算法与非数值算法数值算法与非数值算法算法的基本结构算法的基本结构顺序结构顺序结构分支结构分支

6、结构循环结构循环结构程序的结构化程序的结构化本讲稿第二十页，共七十页11.3 算法的描述方法流程图流程图使用流线表示程序控制流使用流线表示程序控制流程序逻辑清晰，绘制复杂程序逻辑清晰，绘制复杂N-S图图去除流线与箭头的流程图去除流线与箭头的流程图绘制复杂，逻辑不清晰绘制复杂，逻辑不清晰伪代码伪代码程序逻辑较不清晰，书写简单程序逻辑较不清晰，书写简单本讲稿第二十一页，共七十页11.4 算法的设计与实现算法实现过程算法实现过程问题分析问题分析按某种策略实现算法按某种策略实现算法验证上述实现确实为算法验证上述实现确实为算法证明算法的正确性证明算法的正确性选择合适的策略，提高算法效率选择合适的策略，提

7、高算法效率本讲稿第二十二页，共七十页素数判定问题函数原型函数原型int IsPrime(int n);素数判定问题的第二种算法素数判定问题的第二种算法检查检查 1 到到 n 的数中，是否存在可被的数中，是否存在可被 n 整除的数整除的数每找到一个因子，计数器自加每找到一个因子，计数器自加 1在所有数判断完毕后，查看计数器是否为在所有数判断完毕后，查看计数器是否为 2若为若为2则为素数，否则不是则为素数，否则不是本讲稿第二十三页，共七十页素数判定问题int IsPrimeIsPrime(int(int n)int int divisorsdivisors,i;divisors=0;=0;for(

8、for(i i=1;=1;i i=n;i i+)if(if(n%i i=0)=0)divisorsdivisors+;return(divisors divisors=2);本讲稿第二十四页，共七十页素数判定问题验证上述策略确为算法验证上述策略确为算法操作步骤的描述清楚，不存在二义性操作步骤的描述清楚，不存在二义性各操作确实可计算机实现各操作确实可计算机实现执行过程可终止执行过程可终止算法正确性的证明算法正确性的证明素数至少有两个因子素数至少有两个因子divisors 表示数的因子个数，初始为表示数的因子个数，初始为 0，每找到，每找到一个因子，其值递增一个因子，其值递增 1，循环依次查找全部

9、，循环依次查找全部 n 个个自然数，若只有两个因子，显然为素数自然数，若只有两个因子，显然为素数本讲稿第二十五页，共七十页素数判定问题提高算法效率提高算法效率只要在只要在 1 和和 n 之间存在一个因子就可终止，并返之间存在一个因子就可终止，并返回回 n 不是素数不是素数若若 n 可被可被 2 整除，不需检验其它数，程序终止并整除，不需检验其它数，程序终止并返回返回 n 不是素数；若否，则所有偶数都不是因子，不是素数；若否，则所有偶数都不是因子，程序只需检验奇数程序只需检验奇数程序不必检验因子一直到程序不必检验因子一直到 n，只需到只需到 即可即可本讲稿第二十六页，共七十页素数判定问题int

10、int IsPrimeIsPrime(int n n)int i i;if(n n%2%2 =0)return 0;return 0;for(for(i i=3;=3;i i=sqrtsqrt(n);i+=2)+=2)if(n%i i=0)return 0;return 1;return 1;问题：本算法效率确实好吗？问题：本算法效率确实好吗？问题：本算法效率确实好吗？问题：本算法效率确实好吗？每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时本讲稿第二十七页，共七十页素数判定问题int int IsPrime(in

11、t(int n n)int limitlimit,i;limit=sqrtsqrt(n););if(n%2 =0)return 0;return 0;for(i=3;i=limit;i i+=2)if(if(n n%i i=0)=0)return 0;return 1;return 1;问题：本算法确实正确吗？问题：本算法确实正确吗？问题：本算法确实正确吗？问题：本算法确实正确吗？浮点数的存储有误差，程序的正确性依浮点数的存储有误差，程序的正确性依浮点数的存储有误差，程序的正确性依浮点数的存储有误差，程序的正确性依赖机器的表示精度赖机器的表示精度赖机器的表示精度赖机器的表示精度本讲稿第二十八页

12、，共七十页素数判定问题int IsPrime(int n)int int limit,i;limit=sqrtsqrt(n n)+1;if(if(n n%2=0)=0)return 0;return 0;for(for(i i=3;=3;i i=limitlimit;i+=2)if(n%i=0)return 0;return 0;return 1;本讲稿第二十九页，共七十页如何选择合适的算法选择指标选择指标正确性正确性效率效率可读性可读性可维护性可维护性算法评估：在诸多因素中寻找平衡点算法评估：在诸多因素中寻找平衡点高效的算法可读性差，可读性好的算法效率一般高效的算法可读性差，可读性好的算法效

13、率一般不高不高本讲稿第三十页，共七十页最大公约数问题函数原型函数原型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 作为新作为新

14、作为新作为新 y y，返回第，返回第，返回第，返回第1 1步步步步本讲稿第三十一页，共七十页最大公约数问题穷举法实现穷举法实现int gcdgcd(int(int x x,int y)int int g;g g=x;while(while(x x%g!=0|!=0|y y%g!=0)g g;return return g;本讲稿第三十二页，共七十页最大公约数问题欧几里德算法欧几里德算法实现实现int gcd(int x x,int y)int r r;while(1)r r=x%y;if(if(r=0)break;=0)break;x x=y y;y y=r;return y y;本讲稿第三十

15、三页，共七十页11.5 算法分析与算法复杂度算法分析的目的算法分析的目的评估算法的执行效率评估算法的执行效率排序算法排序算法选择排序选择排序归并排序归并排序算法复杂度算法复杂度本讲稿第三十四页，共七十页选择排序函数原型函数原型void SortIntegerArray(int a,int n);基本原理基本原理依次找最小元，将最小元与数组未排序的第一位依次找最小元，将最小元与数组未排序的第一位互换互换重复上述步骤重复上述步骤本讲稿第三十五页，共七十页选择排序原始数组原始数组5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77第一趟第一

16、趟1925375895567330a a00a a11a a22a a33a a44a a55a a66a a77第二趟第二趟1925375895567330a a00a a11a a22a a33a a44a a55a a66a a77本讲稿第三十六页，共七十页选择排序#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(f

17、or(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

18、i+)+)printfprintf(“%(“%7d7d”,”,numbersnumbers i i););本讲稿第三十七页，共七十页选择排序算法的性能分析程序执行时间程序执行时间 T 随问题规模随问题规模 n 显著增加显著增加算法的主要执行时间在于循环算法的主要执行时间在于循环循环执行次数循环执行次数(n2+n)/2算法执行时间的估计与测量算法执行时间的估计与测量平方级算法执行时间：平方级算法执行时间：T n2本讲稿第三十八页，共七十页算法复杂度算法复杂度的定义算法复杂度的定义算法的执行效率随问题规模算法的执行效率随问题规模的变化趋势的变化趋势算法复杂度的分类算法复杂度的分类时间复杂度：算法执

19、行时间时间复杂度：算法执行时间空间复杂度：算法所需存储空间空间复杂度：算法所需存储空间本讲稿第三十九页，共七十页大 O 表达式算法复杂度的度量：大算法复杂度的度量：大 O 表达式表达式近似描述算法的本质近似描述算法的本质例：例：O(n2)表示算法复杂度与问题规模的平方近表示算法复杂度与问题规模的平方近似成正比似成正比原原 则则忽略所有对变化趋势影响较小的项忽略所有对变化趋势影响较小的项忽略所有常数因子忽略所有常数因子例：算法需要例：算法需要 2n+3n2 步骤才能完成，时间复杂度步骤才能完成，时间复杂度为为O(2n)本讲稿第四十页，共七十页算法时间复杂度的估计时间复杂度计算时间复杂度计算 to

20、tal 赋值赋值 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(retu

21、rn(totaltotal/n n););本讲稿第四十一页，共七十页最高复杂度与平均复杂度最高复杂度：算法在最坏情况下的复杂度最高复杂度：算法在最坏情况下的复杂度算法复杂度的上限：无论数据如何变化，算法的算法复杂度的上限：无论数据如何变化，算法的复杂度都不会差于最高复杂度复杂度都不会差于最高复杂度平均复杂度：算法在各种数据下的复杂度平平均复杂度：算法在各种数据下的复杂度平均值均值算法性能的最佳估计值算法性能的最佳估计值本讲稿第四十二页，共七十页最高复杂度与平均复杂度最高时间复杂度：最高时间复杂度：O(n)最好情况：最好情况：O(1)平均时间复杂度：平均时间复杂度：O(n)int int Lin

22、earSearch(int keykey,int a,int,int n n)int i;int i;for(for(i i=0;=0;i n;i+)if(key=a a i)return i;return 1;1;本讲稿第四十三页，共七十页归并排序问题：选择排序复杂度与问题规模的平方成问题：选择排序复杂度与问题规模的平方成正比正比问题规模增加一倍，时间消耗变为问题规模增加一倍，时间消耗变为 4 倍倍问题规模减为一半，时间消耗减为问题规模减为一半，时间消耗减为 分治法分治法思路：将原始数组分成两个子数组，分别排序，思路：将原始数组分成两个子数组，分别排序，然后合并然后合并只要数组合并的时间小于

23、排序算法的时间，分治只要数组合并的时间小于排序算法的时间，分治法就是有效的法就是有效的本讲稿第四十四页，共七十页归并排序原始数组原始数组5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77数组分解数组分解56253758a a00a a11a a22a a3395197330a a44a a55a a66a a77本讲稿第四十五页，共七十页归并排序原始数组原始数组5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77子数组排序子数组排序25375658a a00a a11a a

24、22a a3319307395a a44a a55a a66a a77本讲稿第四十六页，共七十页归并排序原始数组原始数组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本讲稿第四十七页，共七十页归并排序子数组归并子数组归

25、并25375658a a00a a11a a22a a3319307395a a44a a55a a66a a7719a a00a a11a a22a a33a a44a a55a a66a a77本讲稿第四十八页，共七十页归并排序子数组归并子数组归并25375658a a00a a11a a22a a3319307395a a44a a55a a66a a771925a a00a a11a a22a a33a a44a a55a a66a a77本讲稿第四十九页，共七十页归并排序子数组归并子数组归并25375658a a00a a11a a22a a3319307395a a44a a55a

26、 a66a a77192530a a00a a11a a22a a33a a44a a55a a66a a77本讲稿第五十页，共七十页归并排序子数组归并子数组归并25375658a a00a a11a a22a a3319307395a a44a a55a a66a a77192530a a00a a11a a22a a33a a44a a55a a66a a77本讲稿第五十一页，共七十页归并排序子数组归并子数组归并25375658a a00a a11a a22a a3319307395a a44a a55a a66a a771925303756587395a a00a a11a a22a a

27、33a a44a a55a a66a a77本讲稿第五十二页，共七十页归并排序 算法描述算法描述算法描述算法描述 判断数组是否为空或者只有单个元素。若是，则相当于已排序，函判断数组是否为空或者只有单个元素。若是，则相当于已排序，函判断数组是否为空或者只有单个元素。若是，则相当于已排序，函判断数组是否为空或者只有单个元素。若是，则相当于已排序，函数直接返回。否则数直接返回。否则数直接返回。否则数直接返回。否则 将该数组分割为两个子数组，每个子数组大小都是原数组的一半将该数组分割为两个子数组，每个子数组大小都是原数组的一半将该数组分割为两个子数组，每个子数组大小都是原数组的一半将该数组分割为两个子

28、数组，每个子数组大小都是原数组的一半左右左右左右左右 使用同样的方法排序两个子数组使用同样的方法排序两个子数组使用同样的方法排序两个子数组使用同样的方法排序两个子数组 合并两个已排序的子数组合并两个已排序的子数组合并两个已排序的子数组合并两个已排序的子数组函数原型函数原型 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 hi

29、ghhigh););本讲稿第五十三页，共七十页归并排序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+lowl

30、ow)/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 本讲稿第五十四页

31、，共七十页归并排序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

32、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););本讲稿第五十五页，共七十页归并排序算法复杂度：归并排序的执行时间算法复杂度：归并排序的执行时间 执行当前函数内部指令的时间：与执行当前函数内部指令的时间：与执行当前函数内部指令的时间

33、：与执行当前函数内部指令的时间：与 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

34、)/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 本讲稿第五十六页，共七十页标准复杂度类型常数级时间复杂度：常数级时间复杂度：O(1)对数级时间复杂度：对数级时间复杂度：O(log2n)线性级时间复杂度：线性级时间复杂度：O(n)nlog2n 级时间复杂度：级时间复杂度：O(nlog2n)平方级时间复杂度

35、：平方级时间复杂度：O(n2)立方级时间复杂度：立方级时间复杂度：O(n3)指数级时间复杂度：指数级时间复杂度：O(2n)本讲稿第五十七页，共七十页11.6 常用算法设计与分析快速排序算法的基本原理：分解合并策略快速排序算法的基本原理：分解合并策略原始数组：一半元素大于原始数组：一半元素大于50，一半小于，一半小于505625375895197330a a00a a11a a22a a33a a44a a55a a66a a77通过运用合适的分解排序策略，将较小的元素放到通过运用合适的分解排序策略，将较小的元素放到数组前端，较大的元素放到数组的后端数组前端，较大的元素放到数组的后端253719

36、3056589573a a00a a11a a22a a33a a44a a55a a66a a77对子数组进行递归排序，不需要子数组合并操作对子数组进行递归排序，不需要子数组合并操作本讲稿第五十八页，共七十页11.6 常用算法设计与分析快速排序算法的基本原理：分解合并策略快速排序算法的基本原理：分解合并策略如何恰当选择数组分解的基准值，使数组基本平如何恰当选择数组分解的基准值，使数组基本平均分成两部分？均分成两部分？5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77 所选基准值应尽可能接近数组中间的某个值所选基准值应尽可能接近数组

37、中间的某个值所选基准值应尽可能接近数组中间的某个值所选基准值应尽可能接近数组中间的某个值 合理地选择非常困难，一般直接使用数组的第一个元素，这合理地选择非常困难，一般直接使用数组的第一个元素，这合理地选择非常困难，一般直接使用数组的第一个元素，这合理地选择非常困难，一般直接使用数组的第一个元素，这里为里为里为里为 56 56；或取三四个数，使用中间的某个值；或取三四个数，使用中间的某个值；或取三四个数，使用中间的某个值；或取三四个数，使用中间的某个值本讲稿第五十九页，共七十页11.6 常用算法设计与分析 快速排序算法描述快速排序算法描述快速排序算法描述快速排序算法描述 选择一个充当划分较小和较

38、大元素的界线的元素，称为基准值选择一个充当划分较小和较大元素的界线的元素，称为基准值选择一个充当划分较小和较大元素的界线的元素，称为基准值选择一个充当划分较小和较大元素的界线的元素，称为基准值 将数组中的元素重新排列使得较大的元素向数组的末端移动，将数组中的元素重新排列使得较大的元素向数组的末端移动，将数组中的元素重新排列使得较大的元素向数组的末端移动，将数组中的元素重新排列使得较大的元素向数组的末端移动，较小的元素向数组的始端移动。如此在形式上将数组分成了两较小的元素向数组的始端移动。如此在形式上将数组分成了两较小的元素向数组的始端移动。如此在形式上将数组分成了两较小的元素向数组的始端移动。

39、如此在形式上将数组分成了两个部分，界线左边的元素都小于基准值，界线右边的元素都大个部分，界线左边的元素都小于基准值，界线右边的元素都大个部分，界线左边的元素都小于基准值，界线右边的元素都大个部分，界线左边的元素都小于基准值，界线右边的元素都大于基准值。此过程称为分解于基准值。此过程称为分解于基准值。此过程称为分解于基准值。此过程称为分解 排序各个子数组排序各个子数组排序各个子数组排序各个子数组 因为基准值左边的元素都小于基准值右边的元素，所以排序各个子因为基准值左边的元素都小于基准值右边的元素，所以排序各个子因为基准值左边的元素都小于基准值右边的元素，所以排序各个子因为基准值左边的元素都小于基

40、准值右边的元素，所以排序各个子数组后即使得整个数组有序数组后即使得整个数组有序数组后即使得整个数组有序数组后即使得整个数组有序 算法思路仍然为分解合并策略，故可用递归实现算法思路仍然为分解合并策略，故可用递归实现算法思路仍然为分解合并策略，故可用递归实现算法思路仍然为分解合并策略，故可用递归实现本讲稿第六十页，共七十页11.6 常用算法设计与分析快速排序算法的执行模拟：基准值取首元素快速排序算法的执行模拟：基准值取首元素原始数组：一半元素大于或等于原始数组：一半元素大于或等于56，一半小于，一半小于565625375895197330a a00a a11a a22a a33a a44a a55

41、a a66a a77本讲稿第六十一页，共七十页5625375895197330a a00a a11a a22a a33a a44a a55a a66a a7711.6 常用算法设计与分析 第一步：忽略基准值，用两个变量第一步：忽略基准值，用两个变量第一步：忽略基准值，用两个变量第一步：忽略基准值，用两个变量 lh 和和和和 rh 存放数组其存放数组其他部分的首下标和尾下标他部分的首下标和尾下标5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh本讲稿第六十二页，共七十页5625375895197330a a00a a1

42、1a a22a a33a a44a a55a a66a a7711.6 常用算法设计与分析第二步：向左移动下标第二步：向左移动下标 rhrh 直到与直到与直到与直到与 lh 重叠或者其对应重叠或者其对应重叠或者其对应重叠或者其对应的元素值小于基准值。本例中，的元素值小于基准值。本例中，的元素值小于基准值。本例中，的元素值小于基准值。本例中，a7 7=30 为较小值，为较小值，下标下标 rh 不需移动不需移动5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh本讲稿第六十三页，共七十页11.6 常用算法设计与分析 第三步

43、：向右移动下标第三步：向右移动下标第三步：向右移动下标第三步：向右移动下标 lh 直到与直到与 rh 重叠或者其对应重叠或者其对应的元素值大于基准值。本例中，向右移动下标的元素值大于基准值。本例中，向右移动下标 lhlh 直直直直到指向了一个大于到指向了一个大于到指向了一个大于到指向了一个大于 56 56 的元素的元素的元素的元素5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh本讲稿第六十

44、四页，共七十页11.6 常用算法设计与分析 第四步：若下标第四步：若下标第四步：若下标第四步：若下标 lh 和和 rh 还没有指向同一个位置，交还没有指向同一个位置，交换它们所指向位置中的元素换它们所指向位置中的元素5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh5625373095197358a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh本讲稿第六十五页，共七十页11.6 常用算法设计与分析 第五步：重复第二到第四步直到第五步：重复第二到第四步直到第五步：重复第二

45、到第四步直到第五步：重复第二到第四步直到 lhlh 和和 rhrh 重合，如接下重合，如接下来的操作中，第四步交换来的操作中，第四步交换19和和95，再次执行时第二，再次执行时第二步向左移动下标步向左移动下标 rh，并且停在，并且停在，并且停在，并且停在 lh 处处处处5625373095197358a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh5625373019957358a a00a a11a a22a a33a a44a a55a a66a a77lhlh rhrh本讲稿第六十六页，共七十页11.6 常用算法设计与分析 在大多数情况下，

46、在大多数情况下，在大多数情况下，在大多数情况下，lh 和和 rh 重合处为较小元素，若该重合处为较小元素，若该元素较大，则基准值必为最小值，界线在位置元素较大，则基准值必为最小值，界线在位置0；若重合处为较小元素，将其与基准值互换若重合处为较小元素，将其与基准值互换5625373019957358a a00a a11a a22a a33a a44a a55a a66a a77lhlh rhrh1925373056957358a a00a a11a a22a a33a a44a a55a a66a a77boundaryboundary本讲稿第六十七页，共七十页11.6 常用算法设计与分析sta

47、tic 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););SortInteger

48、ArraySortIntegerArray(a a+boundary boundary+1,+1,n n boundaryboundary 1);1);本讲稿第六十八页，共七十页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;本讲稿第六十九页，共七十页作 业第第335335页：第二题（编程题）页：第二题（编程题）第第7 7小题小题第第336336页：第二题（编程题）页：第二题（编程题）第第1313、1414小题小题本讲稿第七十页，共七十页