pascal高精度與排序 noip競賽材料

1、排 序排序就是將雜亂無章的數(shù)據(jù)元素，通過一定的方法按關(guān)鍵字順序排列的過程。1.插入排序其核心思想是將一個記錄插入到已經(jīng)排好順序的有序表中，從而得到一個新的有序表。假設(shè)準備排序的記錄如下：R(2,R(-1,R(34,R(10,R(45,R(3經(jīng)過排序，前三個記錄的排序如下R(-1,R(2, R(34現(xiàn)在需要將第四個記錄R(10插入到當前的序列中。首先確定R(10在新序列中的位置，其次進行插入操作。假設(shè)從左向右排序，則R(10應(yīng)當插入到R(2和R(34之間構(gòu)成新的有序序列。R(-1,R(2, R(10，R(34依次類推完成排序過程。一般描述如下，第次的插入操作為：在含有個有序子序列R1,.,i-1

2、中插入一個記錄R后變成含有個有序子序列R1,.,i。為了避免在插入過程中的數(shù)組下標越界問題，一般不使用R0,僅僅作為臨時存儲區(qū)。自-1記錄起向前搜索的過程中，可以同時向后移動記錄。描述如下：先將序列看成是一個有序的子序列，然后從第個記錄逐個進行插入，直到整個序列變成按關(guān)鍵字排序的有序序列為止。例 :輸入序列數(shù)據(jù)按非減順序輸出.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冒泡排序由于此算法中小的數(shù)據(jù)像水中的氣泡一樣向上浮動，而大的數(shù)據(jù)像石頭一樣沉入水底，因此形象的稱此算法為起泡法排序。例:輸入序列數(shù)據(jù)按非減順序輸出。程序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快速排序快速排序的思想是:先從數(shù)據(jù)序列中選一個元素,并將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每一個待處理

5、的序列的長度為1, 處理結(jié)束.1）、設(shè)置兩個變量I、J，排序開始的時候I：=1，J：=N； 2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A1； 3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個小于X的值，兩者交換； 4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個大于X的值，兩者交換； 5）、重復(fù)第3、4步，直到I=J；例:輸入一組數(shù)據(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.例如：待排序的數(shù)組A的值分別是：（初始關(guān)鍵數(shù)據(jù)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、( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開始找 進行第四次交換后： 27 38 13 49 76 97 65 ( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時J：=4 此時再執(zhí)行第三不的時候就發(fā)現(xiàn)I=J，從而結(jié)束一躺快速排序，那么經(jīng)過一躺快速排序之后的結(jié)果是：27 38 13 49 76 97 65，即所以大于49的數(shù)全部在49的后面，所以小于49的數(shù)全部在49的前面。 快速排序就是遞歸調(diào)用此過程在以49為中點分割這個數(shù)據(jù)序列，分別對前面一部分和后面一部分進行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個有序的序列3.選擇排序選擇排

9、序的基本思想是：對待排序的記錄序列進行n-1遍的處理，第1遍處理是將L1.n中最大者與L1交換位置，第2遍處理是將L2.n中最大者與L2交換位置，.，第i遍處理是將Li.n中最大者與Li交換位置。這樣，經(jīng)過i遍處理之后，前i個記錄的位置就已經(jīng)按從大到小的順序排列好了。例1:輸入序列數(shù)據(jù)按遞減順序輸出.程序如下: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 歸并排序歸并就是將多個有序的數(shù)列合成一個有序的數(shù)列。將兩個有序序列合并為一個有序序列叫二路歸并(merge.歸并排序就是n長度為1的子序列,兩兩歸并最后變?yōu)橛行虻男蛄小?.二路歸并例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.例如數(shù)組A有7個數(shù)據(jù)，分別是： 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.穩(wěn)定性比較插入排序、冒泡排序、二叉樹排序、二路歸并排序及其他線形排序是穩(wěn)定的選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的2.時間復(fù)雜性比較插入排序、冒泡排序、選擇排序的時間復(fù)雜性為O(n2其它非線形排序的時間復(fù)雜性為O(nlog2n線形排序的時間復(fù)雜性為O(n;3.輔助空間的比較線形排序、二路歸并排序的輔助空間為O(n,其它排序的輔助空間為O(1;4.其它比較插入