《排序(冒泡、插入、选择、快速)》由会员分享，可在线阅读，更多相关《排序(冒泡、插入、选择、快速)（10页珍藏版）》请在金锄头文库上搜索。
1、基本算法介绍(一) -排序(冒泡、插入、选择、快速） 排序算法综述 v在很多数据处理的时候都用到了排序，排序 的算法较多。现在要求熟练掌握选择排序、 冒泡排序、插入排序。他们的时间复杂度为 O(N2),如果N比较大的时候这些算法的时间复 杂度就显的比较大,我们今天要学习一种改良 后的插入法排序方法,该算法的时间复杂度为 log2N*N ,效率大大增加,另外我们要学习一种 执行效率最高的快速排序法(分治的利用）它 的时间复杂度为（log2n)2。 （一）冒泡排序(paixu1.pas) /冒泡法：其实质是：先把数据存放在数组中，然后从第一个开始，分别与其后的数字比较将较大 的数换到后面去，然后再
2、比较下面的两个数字，这样一轮下来我们就可以得出最大的数放在 最后，整个数组就已经按从小到大的顺序排列了。 i:=n; 从数据的最后操作起 REPEAT 用直到循环，f控制排序趟数 i:=i-1; f:=True; 每排一趟,要排序的元素少一个，因最大数已排至最后 FOR j:=1 TO i DO 用计数循环进行一趟排序 IF bj+1bj THEN k:=j; 用k记下较小元素的坐标 IF ik THEN Swap(bi,bk) 把较小元素与i元素交换 END; Print(b); Readln 输出有序数据 END. 时间复杂度O（N2） 三）插入排序 插入法排序是把存放在数组中的未经排序的
3、数逐个插入到另外一个数组中。 如有下列未排序的数组A的元素： 49 38 65 97 76 13 27 45 用插入方法按升序排序为： 13 27 38 45 49 65 76 97 可把数据分成两部分前面的数据有序(开始时只有第1个数据)，后面的数据无序( 开始时2n个数据无序)，然后把无序的数据插入到有序的数据中去。无序数 据减少，有序数据增多。把无序数据全部插入为止， 程序分为查找插入的位置、移动数据、插入数据等。查找搜索的方法有三种： 无序表从头向后搜索，有序表从后向前搜索，一一插入(简称从头插入) 无序表从头向后搜索，有序表折半查找搜索，一一插入(简称折半插入) 1) 从尾插入(pa
4、ixu3a) 开始数据分成两部分：第n个数据有序，1n-1个数据无序 FOR i:=n-1 DOWNTO 1 DO BEGIN 从倒数二个到1数据一一插入 k:=ai; j:=i+1; k为要插入的数,j是有序数列的最小下标 WHILE (kaj) AND (j=k) or (ij); if ij; if j-x0 then dg(x,j);如果集合中不止一个数则进入下一层递归，X，J为新边界 if y-i0 then dg(i,y); 如果集合中不止一个数则进入下一层递归，I，Y为新边界 end; var n:array110 of integer; a:integer; procedure dg(x,y:integer); begin clrscr; for a:=1 to 10 do read(na); dg(1,10); for a:=1 to 10 do write(na:4); end.
