《常用算法》PPT课件(I)

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

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‘交换EndifNextjNextI

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

4、４iMax=2iMax=33　　　579　　　４iMax=3iMax=43　　　5　　　79４iMax=4iMax=4S(1)S(iMax)的结果95　　　7　　　3　　　４如此下去，第二轮找到7，第三轮5，．．．．选择法的公式表示：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例题点此进入３：冒

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

6、法的公式表示：Fori=1toN-1forj=1toN-i‘比较次数逐次减少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大于数组的最大长度．用DoWhil

7、e进行顺序查找（ｘ为待查找的数）：P=1‘初始化比较位置Dowhilex<>S(p)AndpNThen‘没找到，处理Else‘找到，处理EndIfVB例题点此进入7.2.2折半查找折半查找法是对有序数列进行查找的一种高效查找办法，其基本思想是逐步缩小

8、查找范围，因为是有序数列，所以采取半分作为分割范围可使比较次数最少.比较过程:（设数列已做降序排序处理）设置三个指针,分别指向数组序列S的Top,Bottom和Middle,其中Middle=(Top+Bottom)/2,进行下列判断13468101215182025BottomTopMiddleX=151)若待查找的数X等于S(Middle),则已经找到,位置就是Mid