基本算法介绍一.PPT

马鞍山成功学校noi2006赛前训练　　　 基本算法介绍(一) ---排序(冒泡、插入、选择、快速） 排序算法综述 在很多数据处理的时候都用到了排序，排序的算法较多。现在要求熟练掌握选择排序、冒泡排序、插入排序。他们的时间复杂度为O(N2),如果N比较大的时候这些算法的时间复杂度就显的比较大,我们今天要学习一种改良后的插入法排序方法,该算法的时间复杂度为log2N*N ,效率大大增加,另外我们要学习一种执行效率最高的快速排序法(分治的利用）它的时间复杂度为（log2n)2。 （一）冒泡排序(paixu1.pas) //冒泡法：其实质是：先把数据存放在数组中，然后从第一个开始，分别与其后的数字比较将较大的数换到后面去，然后再比较下面的两个数字，这样一轮下来我们就可以得出最大的数放在最后，整个数组就已经按从小到大的顺序排列了。 i:=n; {从数据的最后操作起} REPEAT {用直到循环，f控制排序趟数} i:=i-1; f:=True; {每排一趟,要排序的元素少一个，因最大数已排至最后} FOR j:=1 TO i DO {用计数循环进行一趟排序} IF b[j+1]b[j] THEN {如后一个小于前一个,就交换移前} BEGIN Swap(b[j+1],b[j]); f:=False END; {如有交换f为假,还要循环} UNTIL f; {如这趟排序中没有交换, f一直为真，排序结束} 说明：swap(I,j)交换两个数的值 利用f变量的使用来提高算法的执行效率； 冒泡法的时间复杂度为O（N2） （二）选择排序(Paixu1.pas) //设数组中有N个数，取I=1，2，3，……N-1，每次找出后N-I+1个数字中最大的与第I个数字交换位置 BEGIN FOR i:=1 TO n DO b[i]:=a[i]; {读入数据} Print(b); {输出无序的原始数据} FOR i:=1 TO n-1 DO BEGIN {用两重循环排序} k:=i; {用k先记下要交换的元素的坐标} FOR j:=i+1 TO n DO {用i的下一元素至n,逐一与k元素比较} IF b[k]b[j] THEN k:=j; {用k记下较小元素的坐标} IF ik THEN Swap(b[i],b[k]) {把较小元素与i元素交换} END; Print(b); Readln {输出有序数据} END. 时间复杂度O（N2） 三）插入排序 插入法排序是把存放在数组中的未经排序的数逐个插入到另外一个数组中。 如有下列未排序的数组A的元素： 　　　　49 38 65 97 76 13 27 45 用插入方法按升序排序为： 13 27 38 45 49 65 76 97 可把数据分成两部分前面的数据有序(开始时只有第1个数据)，后面的数据无序(开始时2～n个数据无序)，然后把无序的数据插入到有序的数据中去。无序数据减少，有序数据增多。把无序数据全部插入为止， 程序分为查找插入的位置、移动数据、插入数据等。查找有哪些信誉好的足球投注网站的方法有三种： ⑴无序表从头向后有哪些信誉好的足球投注网站，有序表从后向前有哪些信誉好的足球投注网站，一一插入(简称从头插入) ⑶无序表从头向后有哪些信誉好的足球投注网站，有序表折半查找有哪些信誉好的足球投注网站，一一插入(简称折半插入) 1) 从尾插入(paixu3a) 开始数据分成两部分：第n个数据有序，1～n-1个数据无序 FOR i:=n-1 DOWNTO 1 DO BEGIN {从倒数二个到1数据一一插入} k:=a[i]; j:=i+1; {k为要插入的数,j是有序数列的最小下标} WHILE (ka[j]) AND (j=n) DO {当k大于此数,且有序数列后面还有数,就} BEGIN a[j-1]:=a[j]; j:=j+1; END; {将此数前移,拿后面的数再与k比} a[j-1]:=k {当k小于等于有序数列的某数就退出当循环,将k插入此数之