pascal排序算法1

1、排序算法1、選擇排序、選擇排序2、冒泡排序、冒泡排序3、插入排序、插入排序4、快速排序、快速排序什么是排序？什么是排序？ 排序是處理數(shù)據(jù)過程中一種很常用的運(yùn)算，是將一組原本無序的數(shù)據(jù)元素，通過一定的方法，按照某個域的值（關(guān)鍵字）遞增或遞減的次序重新排列的過程。下面主要討論幾種常見的內(nèi)排序算法：選擇排序、冒泡排序、插入排序、快速排序。什么是穩(wěn)定性？穩(wěn)定性：待排序列中的關(guān)鍵字先后出現(xiàn)多次，采用某種排序方法排序后，它們的相對次序不變，那么該排序方法是穩(wěn)定的，否則就是不穩(wěn)定的。例如：有一組記錄的關(guān)鍵字為（23，85，72，58，23，40），其中關(guān)鍵字同為23的記錄有兩個（為了區(qū)分，后一個23帶有下劃

2、線）。如果一種排序算法使排序后的結(jié)果是（23，23，40，58，72，85），則此方法是穩(wěn)定的；如果另一種排序算法使排序后的結(jié)果是（23，23，40，58，72，85），則此方法是不穩(wěn)定的。1. 選擇排序 基本思想：待排序的n個元素由一個有序部分和一個無序部分。 開始時有序部分為空，無序部分包含n個元素。 每一趟從無序部分中選出最小的元素，把它與無序部分的第一個元素交換位置，從而使有序部分元素個數(shù)增1，無序部分元素個數(shù)減1。 經(jīng)過n-1次選擇和交換后，有序部分有n-1個元素，無序部分只有1個元素，且該元素大于（或等于）有序部分中的所有元素，整個排序過程結(jié)束。 22522041190242185

3、4223141220225 1902421854223141220225 190242185422314142225 190242185220 2314142225 190242185220 2314142185 190242225220 2314142185 190242225220 2314142185 190242225220 2314142185 190220225242 2314142185 190220225242 2314142185 190220225242 2314142185 190220225231 242program selectsort;const mx=1000;

4、var d:array1.mxof longint; n,i,j,k:longint;begin readln(n); for i:=1 to n do read(di); for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do /dk為di.dn的最小元素 if djdk then k:=j; j:=dk; dk:=di; di:=j; /交換 end; for i:=1 to n do writeln(di);end.選擇排序的時間復(fù)雜度為O(n2)的，需要進(jìn)行n*(n-1)/2次比較和n-1次交換。優(yōu)化：如果di就是di.dn中的最小值，即k=

5、i,那么不需要交換dk和di。program selectpro;const mx=1000;var d:array1.mxof longint; n,i,j,k:longint;begin readln(n); for i:=1 to n do read(di); for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do /dk為di.dn的最小元素 if djdk then k:=j; if ki then /交換 begin j:=dk; dk:=di; di:=j; end; end; for i:=1 to n do writeln(di);

6、end.選擇排序至多需要n-1次交換。2.冒泡排序 冒泡排序也是一種簡單的排序方法。其操作過程是：首先比較第一個和第二個數(shù)據(jù)，將其中較小的數(shù)據(jù)放到第一個位置，較大的放到第二個位置；然后比較第二個和第三個數(shù)據(jù)，仍將較小放到后一個位置。依此類推，直到比較第n-1和第n個數(shù)據(jù)。這樣，就將待排序序列中的最大的一個放到了第n個數(shù)據(jù)，這個過程稱為第一趟排序。此時第n個數(shù)據(jù)已經(jīng)是最大的了，下面對前N-1個數(shù)據(jù)重復(fù)這個過程，又將次大的數(shù)據(jù)放到了第n-1個位置。一般地，第i趟冒泡排序是對第1個到第n-i+1個數(shù)據(jù)進(jìn)行操作，選出原序列第i大的數(shù)據(jù)放到數(shù)組的第n-i+1位置。重復(fù)這個過程，直到i=n-1為止。 初始

7、關(guān)鍵字：225 220 41 190 242 185 42 231第一趟排序后：220 41 190 225 185 42 231 242第二趟排序后：41 190 220 185 42 225 231 242第三趟排序后：41 190 185 42 220 225 231 242第四趟排序后：41 185 42 190 220 225 231 242第五趟排序后：41 42 185 190 220 225 231 242第六趟排序后：41 42 185 190 220 225 231 242第七趟排序后：41 42 185 190 220 225 231 242program maopaos

8、ort;const mx=10000;var d:array1.mxof longint; n,i,j,k:longint;begin readln(n); for i:=1 to n do read(di); for i:=1 to n-1 do for j:=2 to n-i+1 do if djdj-1 then begin /相鄰元素交換 k:=dj; dj:=dj-1; dj-1:=k; end; for i:=1 to n do writeln(di);end.可見，其時間復(fù)雜度也是O(n2)的。不難發(fā)現(xiàn)，如果某趟排序中沒有發(fā)生交換，就意味著任意兩個相鄰元素都是有序的，那么全部元素

9、就已經(jīng)有序了。所以該算法可以改進(jìn)如下：program maopao1;const mx=10000;var d:array1.mxof longint; n,i,j,k:longint; sorted:boolean; /是否有序是否有序begin readln(n); for i:=1 to n do read(di); sorted:=false; i:=1; while not sorted do begin sorted:=true; /假定已有序假定已有序 for j:=n-1 downto i do if dj+10)and(djk)do begin dj+1:=dj; j:=j-

10、1; end; dj+1:=k; end; for i:=1 to n do writeln(di);end.可見，其時間復(fù)雜度為O(n2)，需要至多n*(n-1)/2次、至少n-1次比較，至多n*(n-1)/2次、至少0次的移動。4. 快速排序通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要?。蝗缓笤侔创朔椒▽@兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。取中間元素185作為基準(zhǔn)元素225 220 41 185 242 190 42 231i=1j=8225 220 41 185 242 190 42

11、231i=1j=742220 41 185 242 190 225 231i=1j=742220 41 185 242 190 225 231i=2j=642220 41 185 242 190 225 231i=2j=542220 41 185 242 190 225 231i=2j=442185 41 220 242 190 225 231i=2j=442185 41 220 242 190 225 231i=3j=342185 41 220 242 190 225 231i=4j=342185 41 220 242 190 225 231i=4j=3L.ji.Rconst maxn=10

12、0000; fin=sort.in; fout=sort.out;var a:array1.maxn of longint; n:longint; procedure init; var i:longint; begin assign(input,f.in); reset(input); readln(n); for i:=1 to n do read(ai); close(input); end; procedure qsort(head,tail:longint); var i,j,mid,tem:longint; begin i:=head; j:=tail; mid:=a(head+t

13、ail)div2; while i=j do begin while aimid do dec(j); if i=j then begin tem:=ai; ai:=aj; aj:=tem; inc(i); dec(j); end; end; if headj then qsort(head,j); if itail then qsort(i,tail); end; procedure print; var i:longint; begin assign(output,fout); rewrite(output); for i:=1 to n-1 do write(ai, ); writeln

14、(an); close(output); end;begin init; qsort(1,n); print;end.隨機(jī)快排隨機(jī)快排program qsortsortpro;const max=10000;var n,i:longint; a:array1.maxof longint;procedure qsort(head,tail:longint);var i,j,x,t:longint;begin i:=head; j:=tail; x:=arandom(tail-head+1)+head;/隨機(jī)選取參考值隨機(jī)選取參考值 headtail while ij do begin while

15、 aix do inc(i); while xaj do dec(j); if (i=j) then begin t:=ai; ai:=aj; aj:=t; inc(i); dec(j); end; end; if headj then qsort(head,j); if itail then qsort(i,tail);end;begin readln(n); randomize; for i:=1 to n do read(ai); qsort(1,n); for i:=1 to n do writeln(ai);end.取首快排program quicksort;const mx=100

16、00;var n,i:longint; d:array1.mxof longint;procedure qsort(head,tail:longint);var x,i,j:longint;begin x:=dhead; i:=head; j:=tail; while ij do begin while(i=x)do j:=j-1; di:=dj; while(ij)and(di=x)do i:=i+1; dj:=di; end; di:=x; if headj-1 then qsort(head,j-1); if i+1tail then qsort(i+1,tail);end;begin

17、readln(n); for i:=1 to n do read(di); qsort(1,n); for i:=1 to n do writeln(di);end.1、排隊(duì)接水、排隊(duì)接水 有有n個人排隊(duì)在一個水籠頭前接水，每個人的接水時間個人排隊(duì)在一個水籠頭前接水，每個人的接水時間互不相等。找出一種互不相等。找出一種n個人排隊(duì)接水的順序，使他們平均等個人排隊(duì)接水的順序，使他們平均等待的時間最短。待的時間最短。輸入：輸入： 第一行：第一行：n(tj then begin tem:=ti; ti:=tj; tj:=tem; tem:=numi; numi:=numj; numj:=tem; en

18、d; sum:=0; for i:=1 to n do sum:=sum+(n+1-i)*ti; writeln(sum/n:0:2); for i:=1 to n-1 do write(numi, ); writeln(numn);end.可優(yōu)化可優(yōu)化2、主油管的最優(yōu)位置、主油管的最優(yōu)位置 Olay教授正在為一家石油公司咨詢。該公司正在設(shè)計(jì)教授正在為一家石油公司咨詢。該公司正在設(shè)計(jì)建造一條由東向西的管道，該管道要穿過一個有建造一條由東向西的管道，該管道要穿過一個有n口井的油口井的油田。從每口井中都有一條噴油管沿最短路徑與主管道直接相田。從每口井中都有一條噴油管沿最短路徑與主管道直接相連（或南

19、或北）。連（或南或北）。 給定各個井的給定各個井的X和和Y坐標(biāo)，坐標(biāo)，Olay教授如何才能選擇主管教授如何才能選擇主管道的最優(yōu)位置（即使得噴管長度總和最小的位置）。道的最優(yōu)位置（即使得噴管長度總和最小的位置）。輸入：輸入：3 2 3 3 7 5 4 輸出：輸出：4 var x,y:array1.100of integer; n,i,j,k,m:integer; begin read(n); 油井個數(shù) for i:=1 to n do read(xi,yi); 每個油井的坐標(biāo) for i:=1 to n-1 do 冒泡排序縱坐標(biāo)：從小到大 for j:=2 to n-i+1 do if yj-1

20、yj then begin k:=yj-1; yj-1:=yj; yj:=k; end; if n mod 2=1 then write(y(n+1) div 2) 輸出中間值 else write(yn div 2, ,y n div 2+1); 輸出中間區(qū)間 end.3、區(qū)間合并、區(qū)間合并【問題描述：問題描述：】 從鍵盤上任意輸入從鍵盤上任意輸入n個區(qū)間，然后按從小到大的順序依次輸出個區(qū)間，然后按從小到大的順序依次輸出n個個區(qū)間的并集。區(qū)間的并集?！据斎耄狠斎耄骸?第一行，區(qū)間個數(shù)第一行，區(qū)間個數(shù)n（=1000） 以下以下n行，每行兩個整數(shù)行，每行兩個整數(shù)a、b（1000000000ab1

21、000000000）,相應(yīng)區(qū)間的坐標(biāo)，中間一個空格。相應(yīng)區(qū)間的坐標(biāo)，中間一個空格?！据敵觯狠敵觯骸?n個區(qū)間的并集，個區(qū)間的并集，n行，每行一個區(qū)間，坐標(biāo)軸的左邊的區(qū)間先輸出。行，每行一個區(qū)間，坐標(biāo)軸的左邊的區(qū)間先輸出?！緲永斎耄簶永斎耄骸?3 2 5 1 4 7 8 【樣例輸出：樣例輸出：】 1 5 7 8區(qū)間的合并區(qū)間的合并注意：注意：1 1、區(qū)間個數(shù)、區(qū)間個數(shù)n n的范圍（的范圍（=1000=1000）2 2、區(qū)間的數(shù)據(jù)類型和范圍：、區(qū)間的數(shù)據(jù)類型和范圍： 整數(shù)類型、整數(shù)類型、-10-109 9-10-109 9算法一：離散化算法一：離散化思路：思路： 設(shè)設(shè)fi:0.1,fi:0.1,初始值全部為初始值全部為0 0。 每讀入一個區(qū)間每讀入一個區(qū)間a ba b For i:=1 to n For i:=1 to n For j:=a to b do fj=1 For j:=a to b do fj=1 最后輸出最后輸出 fj=1 fj=1 的區(qū)間。的區(qū)間。時間復(fù)雜度：時間復(fù)雜度： 10101212，只能過部分?jǐn)?shù)據(jù)。，只能過部分?jǐn)?shù)據(jù)。算法二：直接合并算法二：直接合并1 1、按每個區(qū)間的左端的的值升序排列。、按每個區(qū)間的左端的的值升序排列。 由于由于N=1000,N=1000,任意排序算法。任意排序算法。 注意數(shù)據(jù)