第五章常用算法ppt课件.ppt

《第五章常用算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、常用算法--------------------------排序算法--〉比较互换选择法冒泡法查找算法--〉顺序查找折半查找素数的求法--〉定义法筛选法解一元方程--〉牛顿迭代法二分法数值积分--〉矩形法梯形法辛普生法数值转换--〉B<->O<->D<->H7.1常用的排序算法1：比较互换法基本过程（以降序为例）：将第一个元素顺序与其后面的元素比较，比第一个大则进行交换，第一轮完毕后，最大的元素被挪到了第一个位置，第二轮从第二个元素开始重复上面的过程，结束后得到第二个最大的元素，如此下去经过N-1轮的比较，可将N个数排好举例原

2、始数据：1，2，3，5，4要求：降序第一轮比较：1235421354312545123451234第一轮结束，找到最大值5第二轮比较：51234521345312454123第二轮结束，找到第二最大值4第三轮结果：54312第四轮结果：54321公式表示：(N为排序的维数,OP为操作，降序为“>”)for(i=1toN-1)‘外层循环N-1次for(j=i+1toN)‘内层依赖外层if（S(j)OPS(i)）thent=S(i):S(i)=S(j):S(j)=t‘交换EndifNextjNextIVB例7-1点此进入2：选择法排

3、序特点：比较後不立即互换元素，而是记下其位置并在每一轮比较完毕后和Ｓ（ｉ）互换．首先，比较的元素不同，以降序为例，是当前元素与上次比较後的最大元素进行比较，因此，在进行比较之前，要有一个初始化最大元素的过程．其次，确定完毕的元素的互换是在每一轮完成后进行的，而不是在比较後进行的．再次，互换元素的不同，为Ｓ（i）和Ｓ（iMax）:举例原始数据：1，2，3，5，4要求：降序第一轮比较，初始化最大元素为ｉＭａｘ＝１１　　２　　３　　５　　４iMax=1iMax=2１　　２　　３　　５　　４iMax=2iMax=3１　　２　　３　　５　

4、　４iMax=3iMax=4１　　２　　３　　５　　４iMax=4iMax=4S(1)S(iMax)的结果５２　　　３　　　１　　　４如此下去，第二轮找到４，第三轮３，．．．．选择法的公式表示：Fori=1toN-1iMax=I　　‘初始化iMax,在每轮比较开始处forj=I+1toNif(S(j)OPS(iMax))theniMax=jnextj‘注意比较对象的转变t=S(i):S(i)=S(iMax):S(iMax)=t‘注意互换的时间NextIVB例7-2点此进入３：冒泡法排序如果按升序排序，则方法为：将相邻两个数比较，

5、把小数对调到前边，如此进行一轮後，就会把最大的数互换到最后，再进行一次，则会把第二大数排在倒数第二的位置上，进行Ｎ－１次後，整个数列即可排好．在这种排序过程中，小数如同气泡一样逐层上伏，而大数逐个下沉，因此，被形象的喻为“冒泡”．特征：当数据的大小顺序与要求不符时（逆序），才进行互换操作．第一轮比较：第一轮结束，最大值9沉到最底9475249752479524759247529第二轮比较：第二轮结束，次大值7沉到倒数第二47529475294572945279冒泡法的公式表示：Fori=1toN-1forj=1toN-i‘比较次

6、数逐次减少if(S(j)OPS(j+1))thent=S(j):S(j)=S(j+1):S(j)=t　‘立即互换endifnextjnexti7.2常用的查找算法7.2.1顺序查找顺序查找表现是把待查找的数与数组中的数从头到尾逐一比较，用一变量P来表示当前比较的位置，初始为1，当待查找的数与数组中P位置的元素相等时即可结束,否则P=P+1继续比较，当P大于数组的最大长度,也应该结束．注意退出的两种情况，分别为找到和未找到（P大于数组的最大长度）．顺序查找的公式表示（ｘ为待查找的数）：P=1‘初始化比较位置Dowhilex<>S(

7、p)Andp

8、如果X小于S(Middle),因为是有序数列,则X必定落在Top和Middle-1的范围之内,下一步查找只需在此范围之内进行即可.即Top位置不动,Bottom变为Middle-1.重复1)即可.3)如果X不小于S(Middle),则X必定落在Middle+1和