pascal排序算法1

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

2、線）。如果一種排序算法使排序后的結(jié)果是（23，23，40，58，72，85），則此方法是穩(wěn)定的；如果另一種排序算法使排序后的結(jié)果是（23，23，40，58，72，85），則此方法是不穩(wěn)定的。1. 選擇排序 基本思想：待排序的n個(gè)元素由一個(gè)有序部分和一個(gè)無序部分。 開始時(shí)有序部分為空，無序部分包含n個(gè)元素。 每一趟從無序部分中選出最小的元素，把它與無序部分的第一個(gè)元素交換位置，從而使有序部分元素個(gè)數(shù)增1，無序部分元素個(gè)數(shù)減1。 經(jīng)過n-1次選擇和交換后，有序部分有n-1個(gè)元素，無序部分只有1個(gè)元素，且該元素大于（或等于）有序部分中的所有元素，整個(gè)排序過程結(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.選擇排序的時(shí)間復(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.冒泡排序 冒泡排序也是一種簡(jiǎn)單的排序方法。其操作過程是：首先比較第一個(gè)和第二個(gè)數(shù)據(jù)，將其中較小的數(shù)據(jù)放到第一個(gè)位置，較大的放到第二個(gè)位置；然后比較第二個(gè)和第三個(gè)數(shù)據(jù)，仍將較小放到后一個(gè)位置。依此類推，直到比較第n-1和第n個(gè)數(shù)據(jù)。這樣，就將待排序序列中的最大的一個(gè)放到了第n個(gè)數(shù)據(jù)，這個(gè)過程稱為第一趟排序。此時(shí)第n個(gè)數(shù)據(jù)已經(jīng)是最大的了，下面對(duì)前N-1個(gè)數(shù)據(jù)重復(fù)這個(gè)過程，又將次大的數(shù)據(jù)放到了第n-1個(gè)位置。一般地，第i趟冒泡排序是對(duì)第1個(gè)到第n-i+1個(gè)數(shù)據(jù)進(jìn)行操作，選出原序列第i大的數(shù)據(jù)放到數(shù)組的第n-i+1位置。重復(fù)這個(gè)過程，直到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.可見，其時(shí)間復(fù)雜度也是O(n2)的。不難發(fā)現(xiàn)，如果某趟排序中沒有發(fā)生交換，就意味著任意兩個(gè)相鄰元素都是有序的，那么全部元素

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.可見，其時(shí)間復(fù)雜度為O(n2)，需要至多n*(n-1)/2次、至少n-1次比較，至多n*(n-1)/2次、至少0次的移動(dòng)。4. 快速排序通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要??；然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸遞歸進(jìn)行，以此達(dá)到整個(gè)數(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個(gè)人排隊(duì)在一個(gè)水籠頭前接水，每個(gè)人的接水時(shí)間個(gè)人排隊(duì)在一個(gè)水籠頭前接水，每個(gè)人的接水時(shí)間互不相等。找出一種互不相等。找出一種n個(gè)人排隊(duì)接水的順序，使他們平均等個(gè)人排隊(duì)接水的順序，使他們平均等待的時(shí)間最短。待的時(shí)間最短。輸入：輸入： 第一行：第一行：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ì)建造一條由東向西的管道，該管道要穿過一個(gè)有建造一條由東向西的管道，該管道要穿過一個(gè)有n口井的油口井的油田。從每口井中都有一條噴油管沿最短路徑與主管道直接相田。從每口井中都有一條噴油管沿最短路徑與主管道直接相連（或南

19、或北）。連（或南或北）。 給定各個(gè)井的給定各個(gè)井的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); 油井個(gè)數(shù) for i:=1 to n do read(xi,yi); 每個(gè)油井的坐標(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ū)間合并【問題描述：?jiǎn)栴}描述：】 從鍵盤上任意輸入從鍵盤上任意輸入n個(gè)區(qū)間，然后按從小到大的順序依次輸出個(gè)區(qū)間，然后按從小到大的順序依次輸出n個(gè)個(gè)區(qū)間的并集。區(qū)間的并集?！据斎耄狠斎耄骸?第一行，區(qū)間個(gè)數(shù)第一行，區(qū)間個(gè)數(shù)n（=1000） 以下以下n行，每行兩個(gè)整數(shù)行，每行兩個(gè)整數(shù)a、b（1000000000ab1

21、000000000）,相應(yīng)區(qū)間的坐標(biāo)，中間一個(gè)空格。相應(yīng)區(qū)間的坐標(biāo)，中間一個(gè)空格?！据敵觯狠敵觯骸?n個(gè)區(qū)間的并集，個(gè)區(qū)間的并集，n行，每行一個(gè)區(qū)間，坐標(biāo)軸的左邊的區(qū)間先輸出。行，每行一個(gè)區(qū)間，坐標(biāo)軸的左邊的區(qū)間先輸出。【樣例輸入：樣例輸入：】 3 2 5 1 4 7 8 【樣例輸出：樣例輸出：】 1 5 7 8區(qū)間的合并區(qū)間的合并注意：注意：1 1、區(qū)間個(gè)數(shù)、區(qū)間個(gè)數(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。 每讀入一個(gè)區(qū)間每讀入一個(gè)區(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ū)間。時(shí)間復(fù)雜度：時(shí)間復(fù)雜度： 10101212，只能過部分?jǐn)?shù)據(jù)。，只能過部分?jǐn)?shù)據(jù)。算法二：直接合并算法二：直接合并1 1、按每個(gè)區(qū)間的左端的的值升序排列。、按每個(gè)區(qū)間的左端的的值升序排列。 由于由于N=1000,N=1000,任意排序算法。任意排序算法。 注意數(shù)據(jù)