信息学竞赛常用算法与策略：排序标签：信息学-人人终身学习知识网~是各类综合知识资源信息分享，提升综合素质与提高知识技能的终身学习网络平台信息学奥数

meili 发表于 2022-10-21 20:47:17

信息学竞赛常用算法与策略：排序标签：信息学

优学合肥奥数网讯：信息学竞赛常用算法与策略：排序。排序就是将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程。4.1 简单排序1.选择排序选择排序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L中最小者与L交换位置，第2遍处理是将L中最小者与L交换位置，......，第i遍处理是将L中最小者与L交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。例1:输入序列数据按非减顺序输出.程序如下:program xzpx;const n=7;var a:array of integer;i,j,k,t:integer;beginwrite('Enter date:');for i:= 1 to n do read(a);writeln;for i:=1 to n-1 dobegink:=i;for j:=i+1 to n doif a<a then k:=j;if k<>i thenbegin t:=a;a:=a;a:=t;end;end;write('output data:');for i:= 1 to n do write(a:6);writeln;end.2.插入排序插入排序的基本思想:经过i-1遍处理后,L己排好序。第i遍处理仅将L插入L的适当位置p，原来p后的元素一一向右移动一个位置,使得L又是排好序的序列。例2:输入序列数据按非减顺序输出.程序1:program crpx;const n=7;var a:array of integer;i,j,k,t:integer;beginwrite('Enter date:');for i:= 1 to n do read(a);writeln;for i:=2 to n dobegink:=a;j:=i-1;while (k<a) and (j>0) dobegin a:=a;j:=j-1 end;a:=k;end;write('output data:');for i:= 1 to n do write(a:6);writeln;end.3.冒泡排序冒泡排序又称交换排序其基本思想是:对待排序的记录的关键字进行两两比较,如发现两个记录是反序的,则进行交换,直到无反序的记录为止。例:输入序列数据按非减顺序输出。程序1:program mppx;const n=7;var a:array of integer;i,j,k,t:integer;beginwrite('Enter date:');for i:= 1 to n do read(a);for i:=1 to n -1 dofor j:=n downto i+1 doif a<a thenbegin t:=a;a:=a;a:=t end;write('output data:');for i:= 1 to n do write(a:6);writeln;end.程序2：program mppx;const n=7;var a:array of integer;i,j,k,t:integer;bool:boolean;beginwrite('Enter date:');for i:= 1 to n do read(a);i:=1;bool:=true;while (i<n) and bool dobeginbool:=false;for j:=n downto i+1 doif a<a thenbegin t:=a;a:=a;a:=t;bool:=true end;i:=i+1;end;write('output data:');for i:= 1 to n do write(a:6);writeln;end.程序3：program mppx;const n=7;var a:array of integer;i,j,k,t:integer;beginwrite('Enter date:');for i:= 1 to n do read(a);writeln;k:=n;while k>0 dobeginj:=k-1;k:=0;for i:=1 to j doif a>a thenbegin t:=a;a:=a;a:=t;k:=i;end;end;write('output data:');for i:= 1 to n do write(a:6);writeln;end.4.2快速排序快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.例:输入一组数据小到大排序.程序1:program kspv;const n=7;typearr=array of integer;vara:arr;i:integer;procedure quicksort(var b:arr; s,t:integer);var i,j,x,t1:integer;begini:=s;j:=t;x:=b;repeatwhile (b>=x) and (j>i) do j:=j-1;if j>i then begin t1:=b; b:=b;b:=t1;end;while (b<=x) and (i<j) do i:=i+1;if i<j then begin t1:=b;b:=b;b:=t1; enduntil i=j;b:=x;i:=i+1;j:=j-1;if s<j then quicksort(b,s,j);if i<t then quicksort(b,i,t);end;beginwrite('input data:');for i:=1 to n do read(a);writeln;quicksort(a,1,n);write('output data:');for i:=1 to n do write(a:6);writeln;end.程序2:program kspv;const n=7;typearr=array of integer;vara:arr;i:integer;procedure quicksort(var b:arr; s,t:integer);var i,j,x:integer;begini:=s;j:=t;x:=b;repeatwhile (b>=x) and (j>i) do j:=j-1;if j>i then beginb:=b;i:=i+1;end;while (b<=x) and (i<j) do i:=i+1;if i<j then begin b:=b;j:=j-1; enduntil i=j;b:=x;i:=i+1;j:=j-1;if s<j then quicksort(b,s,j);if i<t then quicksort(b,i,t);end;beginwrite('input data:');for i:=1 to n do read(a);writeln;quicksort(a,1,n);write('output data:');for i:=1 to n do write(a:6);writeln;end.4.3希尔排序基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序或冒泡排序。序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序或冒泡排序，排序就完成。增量序列一般采用：d1=n div 2 ,di=di-1 div 2 ；i=2,3,4.....其中n为待排序序列的长度。程序1:(子序列是插入排序)program xepx;const n=7;typearr=array of integer;vara:arr;i,j,t,d:integer;bool:boolean;beginwrite('input data:');for i:=1 to n do read(a);writeln;d:=n;while d>1 dobegind:=d div 2;for j:=d+1 to n dobegint:=a;i:=j-d;while (i>0) and (a>t) dobegin a:=a;i:=i-d;end;a:=t;end;end;write('output data:');for i:=1 to n do write(a:6);writeln;end.程序2:(子序列是冒泡排序)program xepx;const n=7;typearr=array of integer;vara:arr;i,temp,d:integer;bool:boolean;beginwrite('input data:');for i:=1 to n do read(a);writeln;d:=nwhile d>1 dobegind:=d div 2;repeatbool:=true;for i:=1 to n-d doif a>a thenbegin temp:=a;a:=a;a:=temp; bool:=false end;until bool;end;write('output data:');for i:=1 to n do write(a:6);writeln;end.4.4 堆排序与二叉树排序1.堆排序堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有Ri<=R2i 和Ri<=R2i+1(或>=)堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。堆排序的思想是：1）建初始堆（将结点,[ n/2]-1,...3,2,1分别调成堆）2）当未排序完时输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。程序如下：program duipx;const n=8;type arr=array of integer;var a:arr;i:integer;procedure sift(var a:arr;l,m:integer);var i,j, t:integer;begini:=l;j:=2*i;t:=a;while j<=m dobeginif (j<m) and (a>a) then j:=j+1;if t>a thenbegin a:=a;i:=j;j:=2*i; endelse exit;a:=t;end;end;beginfor i:=1 to n do read(a);for i:=(n div 2) downto 1 dosift(a,i,n);for i:=n downto 2 dobeginwrite(a:4);a:=a;sift(a,1,i-1);end;writeln(a:4);end.2.二叉树排序排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下：program pxtree;consta:array of integer=(10,18,3,8,12,2,7,3);type point=^nod;nod=recordw:integer;right,left:point ;end;var root,first:point;k:boolean;i:integer;procedure hyt(d:integer;var p:point);beginif p=nil thenbeginnew(p);with p^ do begin w:=d;right:=nil;left:=nil end;if k then begin root:=p; k:=false end;endelse with p^ do if d>=w then hyt(d,right) else hyt(d,left);end;procedure hyt1(p:point);beginwith p^ dobeginif left<>nil then hyt1(left);write(w:4);if right<>nil then hyt1(right);endend;beginfirst:=nil;k:=true;for i:=1 to 8 do hyt(a,first);hyt1(root);writeln;end.4.5 归并排序归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge).归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。1.二路归并例1:将有序表L1=(1,5,7),L2=(2，3,4,6,8，9,10)合并一个有序表 L.program gb;const m=3;n=7;type arrl1=array of integer;arrl2=array of integer;arrl=array 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(a);write('Enter l2(sorted):');for i:=1 to n do read(b);i:=1;j:=1;k:=0;while (i<=m) and (j<=n) dobegink:=k+1;if a<=b then begin c:=a;i:=i+1; endelse begin c:=b;j:=j+1;end;end;if i<=m then for r:=i to m do c:=a;if j<=n thenfor r:=j to n do c:=b;writeln('Output data:');for i:=1 to m+n do write(c:5);writeln;end.2.归并排序program gbpx;const maxn=7;type arr=array 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<=m)and (j<=n) dobegink:=k+1;if r<=r then begin r2:=r;i:=i+1 endelse begin r2:=r;j:=j+1 endend;if i<=m thenfor p:=i to m do begin k:=k+1;r2:=r end;if j<=n thenfor p:=j to n do begin k:=k+1;r2:=r end;end;procedure mergesort( var r,r1:arr;s,t:integer);var k:integer; c:arr;beginif s=t then r1:=r elsebegink:=(s+t) div 2;mergesort(r,c,s,k);mergesort(r,c,k+1,t);merge(c,s,k,t,r1)end;end;beginwrite('Enter data:');for i:= 1 to maxn doread(a);mergesort(a,b,1,maxn);for i:=1 to maxn dowrite(b:9);writeln;end.4.6 线形排序以上我们讨论的算法均是基于比较的排序算法，在排序算法中有基于数字本身的算法：计数、桶、基数排序。1.计数排序基本思想是对于序列中的每一元素x,确定序列中小于x的元素的个数。例：n个整数序列且每个值在,排序之。program jspx;const m=6;n=8;var i,j:integer;a,b:array of integer;c:array of integer;beginwriteln('Enter data:');for i:=1 to n do read(a);for i:=1 to m do c:=0;for i:=1 to n do c]:=c]+1;for i:=2 to m do c:=c+c;for i:=n downto 1 dobeginb]]:=a;c]:=c]-1;end;writeln('Sorted data:');for i:= 1 to n dowrite(b:6);end.2.桶排序桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。例：输入n个0到100之间的整数，由小到大排序输出。program tpx;const n=7;var b:array of integer;k:0..100;i:integer;beginwrite('Enter date:(0-100)');for i:=0 to 100 do b:=0;for i:= 1 to n dobeginread(k);b:=b+1;end;writeln('Output data:');for i:=0 to 100 dowhile b>0 do begin write(i:6);b:=b-1 end;writeln;end.3.基数排序基本思想是对n个元素依次按k,k-1,...1位上的数字进行桶排序。program jspx;const n=8;type link=^node;node=recorddata:integer;next:link;end;var i,j,l,m,k:integer;a:array of integer;s:string;q,head:array of link;p,p1:link;beginwriteln('Enter data:');for i:=1 to n do read(a);for i:=5 downto 1 dobeginfor j:=0 to 9 dobeginnew(head);head^.next:=nil;q:=headend;for j:=1 to n dobeginstr(a,s);for k:=1 to 5-length(s) dos:='0'+ s;m:=ord(s)-48;new(p);p^.data:=a;p^.next:=nil;q^.next:=p;q:=p;end;l:=0;for j:=0 to 9 dobeginp:=head;while p^.next<>nil dobeginl:=l+1;p1:=p;p:=p^.next;dispose(p1);a:=p^.data;end;end;end;writeln('Sorted data:');for i:= 1 to n dowrite(a:6);end.4.7各种排序算法的比较1.稳定性比较插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的选择排序、希尔排序、快速排序、堆排序是不稳定的2.时间复杂性比较插入排序、冒泡排序、选择排序的时间复杂性为O(n2)其它非线形排序的时间复杂性为O(nlog2n)线形排序的时间复杂性为O(n);3.辅助空间的比较线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);4.其它比较插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。宜用归并排序。当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。关于合肥市青少年信息学竞赛更多的信息，请关注优学合肥奥数网“青少年信息学竞赛”频道。信息学竞赛常用算法与策略：回溯信息学竞赛常用算法与策略：递归信息学竞赛常用算法与策略：算法的概念青少年信息学竞赛Pascal语言：程序调试（十一）更多精彩内容推荐>>

页: [1]

人人终身学习知识网~是各类综合知识资源信息分享，提升综合素质与提高知识技能的终身学习网络平台's Archiver

信息学竞赛常用算法与策略：排序 标签：信息学

信息学竞赛常用算法与策略：排序标签：信息学