常用算法 排序算法—〉比较互换选择法冒泡法 查找算法一〉顺序查找折半查找 素数的求法—〉定义法筛选法 解一元方程一〉牛顿迭代法二分法 数值积分一〉矩形法梯形法辛普生法 数值转换-〉B0<>D<>H
常 用 算 法 -------------------------- • 排序算法 --〉比较互换 选择法 冒泡法 • 查找算法 --〉顺序查找 折半查找 • 素数的求法 --〉定义法 筛选法 • 解一元方程 --〉牛顿迭代法 二分法 • 数值积分 --〉矩形法 梯形法 辛普生法 • 数值转换 --〉BODH
71常用的排序算法 1:比较互换法 基本过程(以降序为例):将第一个元素顺序与其后 面的元素比较,比第一个大则进行交换,第一轮完毕 后,最大的元素被挪到了第一个位置,第二轮从第 个元素开始重复上面的过程,结束后得到第二个最大 的元素,如此下去经过N-1轮的比较,可将N个数 排好 举例 原始数据:1,2,3,5,4要求:降序
7.1 常用的排序算法 1：比较互换法 基本过程（以降序为例）：将第一个元素顺序与其后 面的元素比较，比第一个大则进行交换，第一轮完毕 后，最大的元素被挪到了第一个位置，第二轮从第二 个元素开始重复上面的过程，结束后得到第二个最大 的元素，如此下去经过 N-1 轮的比较，可将 N 个数 排好 :举例 原始数据： 1，2，3，5，4 要求：降序
第一轮比较: 2 235↓5 1111 33222 55533 4444|4 第一轮结束,找到最大值5
第 一 轮 比 较 ： 1 2 3 5 4 2 1 3 5 4 3 1 2 5 4 5 1 2 3 4 5 1 2 3 4 第一轮结束，找到最大值 5
第二轮比较: 5555 234 33.2_2 444 第二轮结束,找到第二最大值4
第 二 轮 比 较 ： 5 1 2 3 4 5 2 1 3 4 5 3 1 2 4 5 4 1 2 3 第二轮结束，找到第二最大值 4
第三轮结果:54312 第四轮结果:5432 公式表示:(N为排序的个数,OP为操作,降序为“>) for(i-l to N-1) 外层循环N-次 for (=i+l to N) 内层依赖外层 if (S( OP S(i))then t=S(i): S(1=SO: S( 交换 End if Next Next i 例题见7-1.vbp
第三轮结果：5 4 3 1 2 第四轮结果：5 4 3 2 1 公式表示：(N为排序的个数, OP为操作，降序为 “>”) for (i=1 to N-1) ‘外层循环N-1次 for (j=i+1 to N) ‘内层依赖外层 if （S(j) OP S(i)）then t=S(i):S(i)=S(j):S(j)=t ‘交换 End if Next j Next I 例题见7-1.vbp
2:选择法排序 特点:比较後不立即互换元素,而是记下其位置并 在每一轮比较完毕后和S(i)互换 首先,比较的元素不同,以降序为例,是当前元素 与上次比较後的最大元素进行比较,因此,在进行 比较之前,要有一个初始化最大元素的过程 其次,确定完毕的元素的互换是在每一轮完成后进 行的,而不是在比较後进行的 再次,互换元素的不同,为S(i)和S(iMax) 举例 原始数据:3,5,7,9,4要求:降序
2：选择法排序 特点：比较後不立即互换元素，而是记下其位置并 在每一轮比较完毕后和Ｓ（ｉ）互换． 首先，比较的元素不同，以降序为例，是当前元素 与上次比较後的最大元素进行比较，因此，在进行 比较之前，要有一个初始化最大元素的过程． 其次，确定完毕的元素的互换是在每一轮完成后进 行的，而不是在比较後进行的． 再次，互换元素的不同，为Ｓ（i）和Ｓ（iMax） :举例 原始数据： 3，5，7，9，4 要求：降序
第一轮比较,初始化设最大元素下标为iMax=1 iMax=1 9 4 IMax iMax3 7 4 iMax=3→iMax=4 iMax=4→iMax=4 S(1)S(iMax)的结果 4
第一轮比较，初始化设最大元素下标为ｉＭａｘ＝１ 3 5 7 9 ４ iMax=1 iMax=2 3 5 7 9 ４ iMax=2 iMax=3 3 5 7 9 ４ iMax=3 iMax=4 3 5 7 9 ４ iMax=4 iMax=4 S(1) S(iMax)的结果 9 5 7 3 ４
如此下去,第二轮找到7,第三轮5, 选择法的公式表示: For i=l to N-1 iMax 初始化iax在每轮比较开始处 for j=I+l to N if(S( OP S(iMax)then iMax-j next 注意比较对象的转变 t-S(i): S(1=S(iMax): S(IMax=t 注意互换的时间 Next I 例题见7-2.vbp
如此下去，第二轮找到7，第三轮5，．．．． 选择法的公式表示： For i=1 to N-1 iMax=I ‘初始化iMax,在每轮比较开始处 for j=I+1 to N if(S(j) OP S(iMax)) then iMax=j next j ‘注意比较对象的转变 t=S(i):S(i)=S(iMax):S(iMax)=t ‘注意互换的时间 Next I 例题见7-2.vbp
3:冒泡法排序 如果按升序排序,则方法为: 将相邻两个数比较,把小数对调到前边,如此进 行一轮後,就会把最大的数互换到最后,再进行一次 则会把第二大数排在倒数第二的位置上,进行N-1 次後,整个数列即可排好. 在这种排序过程中,小数如果气泡一样逐层上伏, 而大数逐个下沉,因此,被形象的喻为“冒泡” 特征: 当数据的大小顺序与要求不符时(逆序),才进 互换操作
３：冒泡法排序 如果按升序排序，则方法为： 将相邻两个数比较，把小数对调到前边，如此进 行一轮後，就会把最大的数互换到最后，再进行一次， 则会把第二大数排在倒数第二的位置上，进行Ｎ－１ 次後，整个数列即可排好． 在这种排序过程中，小数如果气泡一样逐层上伏， 而大数逐个下沉，因此，被形象的喻为“冒泡”． 特征： 当数据的大小顺序与要求不符时（逆序），才进 行互换操作．
第一轮比较: 9777 77955 555、92 2222、9 第一轮结束,最大值9沉到最底
第 一 轮 比 较 ： 9 4 7 5 2 4 9 7 5 2 4 7 9 5 2 4 7 5 9 2 4 7 5 2 9 第一轮结束，最大值 9沉到最底