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

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

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

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

3、，若该数已出方框，则将其写在该行或该列另一端列另一端列另一端列另一端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页哦算法举例一2

4、16357342第12页，此课件共70页哦算法举例一2168357342第13页，此课件共70页哦算法举例一28168357342第14页，此课件共70页哦算法举例一928168357342第15页，此课件共70页哦算法举例一9281683573492第16页，此课件共70页哦算法举例一816357492第17页，此课件共70页哦算法举例二查英文词典的算法步骤查英文词典的算法步骤S1：翻开词典任意一页翻开词典任意一页S2：若所查词汇在本页第一个单词前，则往前翻若所查词汇在本页第一个单词前，则往前翻页重复页重复S2；若所查词汇在本页最后一个单词后，若所查词汇在本页最后一个单词后，则往后翻页重复则

5、往后翻页重复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 算法的类型与结构数值算法与非数值算法数值算法与非数值算法算法的基本结构算

6、法的基本结构顺序结构顺序结构分支结构分支结构循环结构循环结构程序的结构化程序的结构化第20页，此课件共70页哦11.3 算法的描述方法流程图流程图使用流线表示程序控制流使用流线表示程序控制流程序逻辑清晰，绘制复杂程序逻辑清晰，绘制复杂N-S图图去除流线与箭头的流程图去除流线与箭头的流程图绘制复杂，逻辑不清晰绘制复杂，逻辑不清晰伪代码伪代码程序逻辑较不清晰，书写简单程序逻辑较不清晰，书写简单第21页，此课件共70页哦11.4 算法的设计与实现算法实现过程算法实现过程问题分析问题分析按某种策略实现算法按某种策略实现算法验证上述实现确实为算法验证上述实现确实为算法证明算法的正确性证明算法的正确性选择

7、合适的策略，提高算法效率选择合适的策略，提高算法效率第22页，此课件共70页哦素数判定问题函数原型函数原型int IsPrime(int n);素数判定问题的第二种算法素数判定问题的第二种算法检查检查 1 到到 n 的数中，是否存在可被的数中，是否存在可被 n 整除的数整除的数每找到一个因子，计数器自加每找到一个因子，计数器自加 1在所有数判断完毕后，查看计数器是否为在所有数判断完毕后，查看计数器是否为 2若为若为2则为素数，否则不是则为素数，否则不是第23页，此课件共70页哦素数判定问题int IsPrime(int n)int int divisors,i i;divisors=0;for

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

9、只有两个因子，显然为素数自然数，若只有两个因子，显然为素数第25页，此课件共70页哦素数判定问题提高算法效率提高算法效率只要在只要在 1 和和 n 之间存在一个因子就可终止，并返之间存在一个因子就可终止，并返回回 n 不是素数不是素数若若 n 可被可被 2 整除，不需检验其它数，程序终止并整除，不需检验其它数，程序终止并返回返回 n 不是素数；若否，则所有偶数都不是因子，不是素数；若否，则所有偶数都不是因子，程序只需检验奇数程序只需检验奇数程序不必检验因子一直到程序不必检验因子一直到 n，只需到只需到 即可即可第26页，此课件共70页哦素数判定问题int IsPrimeIsPrime(int

10、n)int int i i;if(n n%2%2 =0)=0)return 0;return 0;for(for(i i=3;=3;i i=sqrtsqrt(n);i+=2)if(n%i i=0)return 0;return 1;return 1;问题：本算法效率确实好吗？问题：本算法效率确实好吗？问题：本算法效率确实好吗？问题：本算法效率确实好吗？每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时每次迭代都需要计算平方根，很费时第27页，此课件共70页哦素数判定问题int IsPrimeIsPrime(int(int n n)int limit

11、,i;limitlimit=sqrt(n););if(n%2 =0)=0)return 0;for(for(i=3;i i=limitlimit;i+=2)+=2)if(n%i=0)=0)return 0;return 1;return 1;问题：本算法确实正确吗？问题：本算法确实正确吗？问题：本算法确实正确吗？问题：本算法确实正确吗？浮点数的存储有误差，程序的正确性依赖浮点数的存储有误差，程序的正确性依赖浮点数的存储有误差，程序的正确性依赖浮点数的存储有误差，程序的正确性依赖机器的表示精度机器的表示精度机器的表示精度机器的表示精度第28页，此课件共70页哦素数判定问题int IsPrime(

12、int(int n n)int limitlimit,i i;limit=sqrt(n n)+1;)+1;if(n%2%2=0)return 0;for(i i=3;i=limitlimit;i+=2)+=2)if(n%i i=0)=0)return 0;return 1;return 1;第29页，此课件共70页哦如何选择合适的算法选择指标选择指标正确性正确性效率效率可读性可读性可维护性可维护性算法评估：在诸多因素中寻找平衡点算法评估：在诸多因素中寻找平衡点高效的算法可读性差，可读性好的算法效率一般高效的算法可读性差，可读性好的算法效率一般不高不高第30页，此课件共70页哦最大公约数问题函数

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 作为新作为新作为新作为新 y y，返回第，返回第，返回第，返回第1

14、1步步步步第31页，此课件共70页哦最大公约数问题穷举法实现穷举法实现int int gcd(int(int x x,int ,int y y)int int g g;g g=x x;while(x%g!=0|y y%g g!=0)g g;return return g g;第32页，此课件共70页哦最大公约数问题欧几里德算法欧几里德算法实现实现int gcd(int x,int y)int r r;while(1)r=x%y y;if(if(r=0)break;=0)break;x=y y;y=r;return return y;第33页，此课件共70页哦11.5 算法分析与算法复杂度算法分

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

16、11a 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;

17、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(“%(“%7d

18、7d”,”,numbersnumbers i i););第37页，此课件共70页哦选择排序算法的性能分析程序执行时间程序执行时间 T 随问题规模随问题规模 n 显著增加显著增加算法的主要执行时间在于循环算法的主要执行时间在于循环循环执行次数循环执行次数(n2+n)/2算法执行时间的估计与测量算法执行时间的估计与测量平方级算法执行时间：平方级算法执行时间：T n2第38页，此课件共70页哦算法复杂度算法复杂度的定义算法复杂度的定义算法的执行效率随问题规模算法的执行效率随问题规模的变化趋势的变化趋势算法复杂度的分类算法复杂度的分类时间复杂度：算法执行时间时间复杂度：算法执行时间空间复杂度：算法所需

19、存储空间空间复杂度：算法所需存储空间第39页，此课件共70页哦大 O 表达式算法复杂度的度量：大算法复杂度的度量：大 O 表达式表达式近似描述算法的本质近似描述算法的本质例：例：O(n2)表示算法复杂度与问题规模的平方近表示算法复杂度与问题规模的平方近似成正比似成正比原原 则则忽略所有对变化趋势影响较小的项忽略所有对变化趋势影响较小的项忽略所有常数因子忽略所有常数因子例：算法需要例：算法需要 2n+3n2 步骤才能完成，时间复杂度步骤才能完成，时间复杂度为为O(2n)第40页，此课件共70页哦算法时间复杂度的估计时间复杂度计算时间复杂度计算 total 赋值赋值 1 次次i 赋值赋值 1 次；

20、次；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

21、页，此课件共70页哦最高复杂度与平均复杂度最高复杂度：算法在最坏情况下的复杂度最高复杂度：算法在最坏情况下的复杂度算法复杂度的上限：无论数据如何变化，算法的算法复杂度的上限：无论数据如何变化，算法的复杂度都不会差于最高复杂度复杂度都不会差于最高复杂度平均复杂度：算法在各种数据下的复杂度平平均复杂度：算法在各种数据下的复杂度平均值均值算法性能的最佳估计值算法性能的最佳估计值第42页，此课件共70页哦最高复杂度与平均复杂度最高时间复杂度：最高时间复杂度：O(n)最好情况：最好情况：O(1)平均时间复杂度：平均时间复杂度：O(n)int int LinearSearchLinearSearch(in

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

23、于排序算法的时间，分治只要数组合并的时间小于排序算法的时间，分治法就是有效的法就是有效的第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

24、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页哦归并排序子数组归并子数组

25、归并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 a55

26、a 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

27、 a33a a44a a55a a66a a77第52页，此课件共70页哦归并排序算法描述算法描述 判断数组是否为空或者只有单个元素。若是，则相当于已排序，判断数组是否为空或者只有单个元素。若是，则相当于已排序，判断数组是否为空或者只有单个元素。若是，则相当于已排序，判断数组是否为空或者只有单个元素。若是，则相当于已排序，函数直接返回。否则函数直接返回。否则函数直接返回。否则函数直接返回。否则 将该数组分割为两个子数组，每个子数组大小都是原数组的一半将该数组分割为两个子数组，每个子数组大小都是原数组的一半将该数组分割为两个子数组，每个子数组大小都是原数组的一半将该数组分割为两个子数组，每个子数

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 highhigh)

29、;);第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;)

30、/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页哦归并

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 n)*q*q+

32、=+=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页哦归并排序算法复杂度：归并排序的执行时间算法复杂度：归并排序的执行时间 执行当前函数内部指令的时间：与执行当前函数内部指令的时间：与执行当前函数内部指令的时间：与执行当前函

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)/4)，T

34、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)平方级时间复杂度：平方级时间复

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

36、元素放到数组前端，较大的元素放到数组的后端前端，较大的元素放到数组的后端前端，较大的元素放到数组的后端前端，较大的元素放到数组的后端2537193056589573a a00a a11a a22a a33a a44a a55a a66a a77对子数组进行递归排序，不需要子数组合并操作对子数组进行递归排序，不需要子数组合并操作第58页，此课件共70页哦11.6 常用算法设计与分析快速排序算法的基本原理：分解合并策略快速排序算法的基本原理：分解合并策略如何恰当选择数组分解的基准值，使数组基本平如何恰当选择数组分解的基准值，使数组基本平均分成两部分？均分成两部分？5625375895197330a

37、 a00a a11a a22a a33a a44a a55a a66a a77 所选基准值应尽可能接近数组中间的某个值所选基准值应尽可能接近数组中间的某个值所选基准值应尽可能接近数组中间的某个值所选基准值应尽可能接近数组中间的某个值 合理地选择非常困难，一般直接使用数组的第一个元素，合理地选择非常困难，一般直接使用数组的第一个元素，合理地选择非常困难，一般直接使用数组的第一个元素，合理地选择非常困难，一般直接使用数组的第一个元素，这里为这里为这里为这里为 56 56；或取三四个数，使用中间的某个值；或取三四个数，使用中间的某个值；或取三四个数，使用中间的某个值；或取三四个数，使用中间的某个值第

38、59页，此课件共70页哦11.6 常用算法设计与分析快速排序算法描述快速排序算法描述 选择一个充当划分较小和较大元素的界线的元素，称为基准选择一个充当划分较小和较大元素的界线的元素，称为基准选择一个充当划分较小和较大元素的界线的元素，称为基准选择一个充当划分较小和较大元素的界线的元素，称为基准值值值值 将数组中的元素重新排列使得较大的元素向数组的末端移动，将数组中的元素重新排列使得较大的元素向数组的末端移动，将数组中的元素重新排列使得较大的元素向数组的末端移动，将数组中的元素重新排列使得较大的元素向数组的末端移动，较小的元素向数组的始端移动。如此在形式上将数组分成了较小的元素向数组的始端移动。

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

40、素，所以排序因为基准值左边的元素都小于基准值右边的元素，所以排序因为基准值左边的元素都小于基准值右边的元素，所以排序各个子数组后即使得整个数组有序各个子数组后即使得整个数组有序各个子数组后即使得整个数组有序各个子数组后即使得整个数组有序 算法思路仍然为分解合并策略，故可用递归实现算法思路仍然为分解合并策略，故可用递归实现算法思路仍然为分解合并策略，故可用递归实现算法思路仍然为分解合并策略，故可用递归实现第60页，此课件共70页哦11.6 常用算法设计与分析快速排序算法的执行模拟：基准值取首元素快速排序算法的执行模拟：基准值取首元素原始数组：一半元素大于或等于原始数组：一半元素大于或等于56，一

41、半小于，一半小于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

42、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页

43、，此课件共70页哦11.6 常用算法设计与分析 第三步：向右移动下标第三步：向右移动下标第三步：向右移动下标第三步：向右移动下标 lh 直到与直到与直到与直到与 rh 重叠或者其对应重叠或者其对应的元素值大于基准值。本例中，向右移动下标的元素值大于基准值。本例中，向右移动下标 lhlh 直到指向了一个大于直到指向了一个大于直到指向了一个大于直到指向了一个大于 56 56 的元素的元素的元素的元素5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh5625375895197330a a00a a11a a22a a33a

44、 a44a a55a a66a a77lhlhrhrh第64页，此课件共70页哦11.6 常用算法设计与分析第四步：若下标第四步：若下标第四步：若下标第四步：若下标 lhlh 和和和和 rh 还没有指向同一个位置，交还没有指向同一个位置，交换它们所指向位置中的元素换它们所指向位置中的元素5625375895197330a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh5625373095197358a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh第65页，此课件共70页哦11.6 常用算法设计与分析第

45、五步：重复第二到第四步直到第五步：重复第二到第四步直到 lh 和和 rh 重合，如接重合，如接重合，如接重合，如接下来的操作中，第四步交换下来的操作中，第四步交换下来的操作中，第四步交换下来的操作中，第四步交换1919和和和和9595，再次执行时第二，再次执行时第二，再次执行时第二，再次执行时第二步向左移动下标步向左移动下标步向左移动下标步向左移动下标 rh，并且停在，并且停在 lh lh 处处处处5625373095197358a a00a a11a a22a a33a a44a a55a a66a a77lhlhrhrh5625373019957358a a00a a11a a22a a3

46、3a a44a a55a a66a a77lhlh rhrh第66页，此课件共70页哦11.6 常用算法设计与分析在大多数情况下，在大多数情况下，lh 和和 rh 重合处为较小元素，若该重合处为较小元素，若该重合处为较小元素，若该重合处为较小元素，若该元素较大，则基准值必为最小值，界线在位置元素较大，则基准值必为最小值，界线在位置元素较大，则基准值必为最小值，界线在位置元素较大，则基准值必为最小值，界线在位置0 0；若重；若重；若重；若重合处为较小元素，将其与基准值互换合处为较小元素，将其与基准值互换合处为较小元素，将其与基准值互换合处为较小元素，将其与基准值互换562537301995735

47、8a 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 boundary

48、boundary;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(

49、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页哦