文档介绍：常用算法-------------------------- ?排序算法--〉比较互换选择法冒泡法?查找算法--〉顺序查找折半查找?素数的求法--〉定义法筛选法?解一元方程--〉牛顿迭代法二分法?数值积分--〉矩形法梯形法辛普生法?数值转换--〉 B<->O<->D<->H 常用的排序算法常用的排序算法 1:比较互换法基本过程(以降序为例):将第一个元素顺序与其后面的元素比较,比第一个大则进行交换,第一轮完毕后,最大的元素被挪到了第一个位置,第二轮从第二个元素开始重复上面的过程,结束后得到第二个最大的元素,如此下去经过 N-1 轮的比较,可将 N个数排好:举例原始数据: 1,2,3,5,4 要求:降序第一轮比较:1 2 3 5 4 2 1 3 5 4 3 1 2 5 4 5 1 2 3 4 5 5 1 2 3 4 第一轮结束,找到最大值 5 第二轮比较:5 1 2 3 4 5 2 1 3 4 5 3 1 2 4 54 1 2 3 第二轮结束,找到第二最大值 4 第三轮结果: 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 VB 例题点此进入 2:选择法排序特点:比较後不立即互换元素,而是记下其位置并在每一轮比较完毕后和S(i)互换. 首先,比较的元素不同,以降序为例,是当前元素与上次比较後的最大元素进行比较,因此,在进行比较之前,要有一个初始化最大元素的过程. 其次,确定完毕的元素的互换是在每一轮完成后进行的,而不是在比较後进行的. 再次,互换元素的不同,为S( i)和S( iMax ) :举例原始数据: 3,5,7,9,4 要求:降序第一轮比较,初始化设最大元素下标为 iMax=1 3579 4 iMax =1 iMax =2 3579 4 iMax =2 iMax =3 3579 4 iMax =3 iMax =4 3579 4 iMax =4 iMax =4 S(1) S(iMax )的结果 9573 4 如此下去,第二轮找到 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 VB 例题点此进入 3:冒泡法排序如果按升序排序,则方法为: 将相邻两个数比较,把小数对调到前边,如此进行一轮後,就会把最大的数互换到最后,再进行一次, 则会把第二大数排在倒数第二的位置上,进行N-1 次後,整个数列即可排好. 在这种排序过程中,小数如气泡一样逐层上伏, 而大数逐个下沉,因此,被形象的喻为“冒泡”. 特征: 当数据的大小顺序与要求不符时(逆序),才进行互换操作. 第一轮比较:9 4 7 5 2 4 9 7 5 2 4 7 9 5 2 4 7