pascal高精度与排序 noip竞赛材料

1、排 序排序就是将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程。1.插入排序其核心思想是将一个记录插入到已经排好顺序的有序表中，从而得到一个新的有序表。假设准备排序的记录如下：R(2,R(-1,R(34,R(10,R(45,R(3经过排序，前三个记录的排序如下R(-1,R(2, R(34现在需要将第四个记录R(10插入到当前的序列中。首先确定R(10在新序列中的位置，其次进行插入操作。假设从左向右排序，则R(10应当插入到R(2和R(34之间构成新的有序序列。R(-1,R(2, R(10，R(34依次类推完成排序过程。一般描述如下，第次的插入操作为：在含有个有序子序列R1,.,i-1

2、中插入一个记录R后变成含有个有序子序列R1,.,i。为了避免在插入过程中的数组下标越界问题，一般不使用R0,仅仅作为临时存储区。自-1记录起向前搜索的过程中，可以同时向后移动记录。描述如下：先将序列看成是一个有序的子序列，然后从第个记录逐个进行插入，直到整个序列变成按关键字排序的有序序列为止。例 :输入序列数据按非减顺序输出.program crpx;const n=7;var a:array1.n of integer;i,j,k,t:integer;beginwrite('Enter date:'for i:= 1 to n do read(ai;writeln;for i

3、:=2 to n dobegink:=ai;j:=i-1;while (k 0 do begin aj+1:=aj;j:=j-1 end;aj+1:=k;end;write('output data:'for i:= 1 to n do write(ai:6;writeln;end.2.快速排序2.1冒泡排序由于此算法中小的数据像水中的气泡一样向上浮动，而大的数据像石头一样沉入水底，因此形象的称此算法为起泡法排序。例:输入序列数据按非减顺序输出。程序1:program mppx;const n=7;var a:array1.n of integer;i,j,k,t:intege

4、r;beginwrite('Enter date:'for i:= 1 to n do read(ai;for i:=1 to n -1 dofor j:=n downto i+1 doif aj-1>aj thenbegin t:=aj-1;aj-1:=aj;aj:=t end;write('output data:'for i:= 1 to n do write(ai:6;writeln;end.2.2快速排序快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理

5、的序列的长度为1, 处理结束.1）、设置两个变量I、J，排序开始的时候I：=1，J：=N； 2）以第一个数组元素作为关键数据，赋值给X，即X：=A1； 3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换； 4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换； 5）、重复第3、4步，直到I=J；例:输入一组数据小到大排序.程序1:program kspv;const n=7;typearr=array1.n of integer;vara:arr;i:integer;procedure quicksort(var b

6、:arr; s,t:integer;var i,j,x,t1:integer;begini:=s;j:=t;x:=bi;repeatwhile (bj>=x and (j>i do j:=j-1;if j>i then begin t1:=bi; bi:=bj;bj:=t1;end;while (bi<=x and (i if i until i=j;bi:=x;i:=i+1;j:=j-1;if s if i end;beginwrite('input data:'for i:=1 to n do read(ai;writeln;quicksort(a,

7、1,n;write('output data:'for i:=1 to n do write(ai:6;writeln;end.例如：待排序的数组A的值分别是：（初始关键数据X：=49） A1 A2 A3 A4 A5 A6 A7： 49 38 65 97 76 13 27 进行第一次交换后： 27 38 65 97 76 13 49 ( 按照算法的第三步从后面开始找 进行第二次交换后： 27 38 49 97 76 13 65 ( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 进行第三次交换后： 27 38 13 97 76 49 65

8、( 按照算法的第五步将又一次执行算法的第三步从后开始找 进行第四次交换后： 27 38 13 49 76 97 65 ( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。 快速排序就是递归调用此过程在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列3.选择排序选择排

9、序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L1.n中最大者与L1交换位置，第2遍处理是将L2.n中最大者与L2交换位置，.，第i遍处理是将Li.n中最大者与Li交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从大到小的顺序排列好了。例1:输入序列数据按递减顺序输出.程序如下:program xzpx;const n=7;var a:array1.n of integer;i,j,k,t:integer;beginwrite('Enter date:'for i:= 1 to n do read(ai;writeln;for i:=1 to n

10、-1 dobegink:=i;for j:=i+1 to n doif aj>ak then k:=j;if k<>i thenbegin t:=ai;ai:=ak;ak:=t;end;end;write('output data:'for i:= 1 to n do write(ai:6;writeln;end.4 归并排序归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge.归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。1.二路归并例1:将有序表L1=(1,5,7,L2=(2，3,4,6,8，9,

11、10合并一个有序表 L.program gb;const m=3;n=7;type arrl1=array1.m of integer;arrl2=array1.n of integer;arrl=array1.m+n of integer;var a:arrl1;b:arrl2;c:arrl;i,j,k,r:integer;beginwrite('Enter l1(sorted:'for i:=1 to m do read(ai;write('Enter l2(sorted:'for i:=1 to n do read(bi;i:=1;j:=1;k:=0;wh

12、ile (i<=m and (j<=n dobegink:=k+1;if ai<=bj then begin ck:=ai;i:=i+1; endelse begin ck:=bj;j:=j+1;end;end; if i<=m then for r:=i to m do cm+r:=ar;if j<=n then for r:=j to n do cn+r:=br;writeln('Output data:'for i:=1 to m+n do write(ci:5;writeln;end.2.归并排序program gbpx;const max

13、n=7;type arr=array1.maxn of integer;var a,b,c:arr;i:integer;procedure merge(r:arr;l,m,n:integer;var r2:arr;var i,j,k,p:integer;begini:=l;j:=m+1;k:=l-1;while (i<=mand (j<=n dobegink:=k+1;if ri<=rj then begin r2k:=ri;i:=i+1 endelse begin r2k:=rj;j:=j+1 endend;if i<=m thenfor p:=i to m do b

14、egin k:=k+1;r2k:=rp end;if j<=n thenfor p:=j to n do begin k:=k+1;r2k:=rp end;end;procedure mergesort( var r,r1:arr;s,t:integer;var k:integer; c:arr;beginif s=t then r1s:=rs elsebegink:=(s+t div 2;mergesort(r,c,s,k;mergesort(r,c,k+1,t;merge(c,s,k,t,r1end;end;beginwrite('Enter data:'for i:

15、= 1 to maxn doread(ai;mergesort(a,b,1,maxn;for i:=1 to maxn dowrite(bi:9;writeln;end.例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示： 初始值 49 38 65 97 76 13 27 看成由长度为1的7个子序列组成 第一次合并之后 38 49 65 97 13 76 27 看成由长度为1或2的4个子序列组成 第二次合并之后 38 49 65 97 13 27 76 看成由长度为4或3的2个子序列组成 第三次合并之后 13 27 38 49 65 76 975各种排序算法的比较1.稳定性比较插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的选择排序、希尔排序、快速排序、堆排序是不稳定的2.时间复杂性比较插入排序、冒泡排序、选择排序的时间复杂性为O(n2其它非线形排序的时间复杂性为O(nlog2n线形排序的时间复杂性为O(n;3.辅助空间的比较线形排序、二路归并排序的辅助空间为O(n,其它排序的辅助空间为O(1;4.其它比较插入