第6講排序算法及應用

1、第六講排序算法及應用 劉建國劉建國昌邑市卜莊初中昌邑市卜莊初中排序算法的種類：排序算法的種類：1、選擇排序、選擇排序2、冒泡排序、冒泡排序3、插入排序、插入排序4、快速排序、快速排序5、堆排序、堆排序1、選擇排序、選擇排序算法基本思想：算法基本思想： 對待排序的序列進行對待排序的序列進行n-1遍處理：遍處理： 第第1 1遍處理是從遍處理是從a1,a2,ana1,a2,an中選擇最小的放在中選擇最小的放在a1a1位置；位置； 第第2 2遍處理是從遍處理是從a2,a3,ana2,a3,an中選擇最小的放在中選擇最小的放在a2a2位置；位置； 第第I I遍處理是將遍處理是將a i ,a i+1,an

2、a i ,a i+1,an中最小的數(shù)與中最小的數(shù)與a i a i 交換位置，這交換位置，這樣經(jīng)過第樣經(jīng)過第i i遍處理后，遍處理后，aiai是所有的中的第是所有的中的第i i小。即前小。即前i i個數(shù)就已經(jīng)排個數(shù)就已經(jīng)排好序了。好序了。N-1N-1遍處理后，剩下的最后一個一定是最大的，不需要再處理了。遍處理后，剩下的最后一個一定是最大的，不需要再處理了。a:待排序的數(shù)組；待排序的數(shù)組；/從小到大排序從小到大排序簡單選擇排序：簡單選擇排序：for i:=1 to n-1 do 從第一個元素開始從第一個元素開始,進行進行n-1遍處理遍處理 for j:=i+1 to n do 第第i遍處理遍處理

3、If aiaj then 交換交換ai和和aj begin t:=ai; ai:=aj; aj:=t; end; 算法的改進算法的改進: 減少交換次數(shù)減少交換次數(shù) for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if ajak then k:=j; if ki then begin t:=ak; ak:=ai; ai:=t; end; end;排序的關鍵字：排序的關鍵字：20 30 10 15 16 13 82、冒泡排序算法：、冒泡排序算法：基本思想基本思想：（從小到大排序）：（從小到大排序） 將待排序的數(shù)據(jù)看作豎派排的一列將待排序的數(shù)據(jù)看作

4、豎派排的一列”氣泡氣泡“，小的數(shù)據(jù)，小的數(shù)據(jù)比較輕，從而要上浮。比較輕，從而要上浮。共進行共進行n-1遍處理，每一遍處理，就是從底向上檢查序列，遍處理，每一遍處理，就是從底向上檢查序列，如果相鄰的兩個數(shù)據(jù)順序不對，即輕（?。┑脑谙旅?，就交如果相鄰的兩個數(shù)據(jù)順序不對，即輕（小）的在下面，就交換他們的位置。換他們的位置。 第一遍處理完后，第一遍處理完后，“最輕最輕”的就浮到上面。的就浮到上面。 第二遍處理完后，第二遍處理完后，“次輕次輕”的就浮到上面。的就浮到上面。 共需要共需要n-1遍處理即完成排序。遍處理即完成排序。/ 簡單的冒泡排序簡單的冒泡排序for i:=1 to n-1 do for

5、j:=n downto i+1 do if ajaj-1 then begin t:=aj; aj:=aj-1; aj-1:=t; end;/ 判斷標志：判斷標志： flag=true 已有序已有序/改進后的冒泡排序改進后的冒泡排序for i:=1 to n-1 do begin flag:=true; for j:=n downto i+1 do if ajaj-1 then begin t:=aj; aj:=aj-1; aj-1:=t; flag:=false; end; if flag=true then break; /某一輪沒有交換，說明都已經(jīng)有序了某一輪沒有交換，說明都已經(jīng)有序了

6、end;算法的改進算法的改進關鍵字關鍵字 20 30 40 50 60 10測定時間的方法：測定時間的方法：通過訪問MemLSeg0040:$006C來獲取當前時間，它返回的是當日零時到現(xiàn)在所經(jīng)過的時間，單位約為55毫秒（約1/18.2秒）。測定測定執(zhí)行的時間執(zhí)行的時間Starttime,endtime:longint;Starttime:= MemLSeg0040:$006C; endtime:= MemLSeg0040:$006C;Writeln(endtime-starttime)/18.2:0:2); 語句組2運行的時間或： Writeln(MemLSeg0040:$006C -sta

7、rttime)/18.2:0:2); StartTime := MemLSeg0040:$006C; for i:=1 to n-1 do for j:=n downto i+1 do if ajaj-1 then begin t:=aj; aj:=aj-1; aj-1:=t; end; writeln(MemLSeg0040:$006c - StartTime)/18.2:0:2);3、插入排序算法、插入排序算法:基本思想：基本思想：經(jīng)過經(jīng)過i-1i-1遍處理后，遍處理后，a1,a2,ai-1a1,a2,ai-1已排好序。已排好序。第第i i遍處理是將元素遍處理是將元素aiai插入到插入到a

8、1,a2,ai-1a1,a2,ai-1的適當?shù)奈恢茫瑥牡倪m當?shù)奈恢?，從而使得而使得a1,a2,ai-1,aia1,a2,ai-1,ai又是排好的序列。又是排好的序列。a:array0.n of integer; a:array0.n of integer; a0a0記錄當前待插元記錄當前待插元aiaifor i:=2 to n dofor i:=2 to n do begin begin a0:=ai; a0:=ai; 取第取第i i個元素作為待插入元素個元素作為待插入元素 j:=i-1; j:=i-1; 從已排好的最后一個從已排好的最后一個ai-1ai-1開始比較開始比較 while a0a

9、j do while a0=aja0=aj時循環(huán)結束時循環(huán)結束 aj+1:=a0; aj+1:=a0; 在第在第j+1j+1個位置插入個位置插入aiai元素元素 end; end;4、快速排序算法：、快速排序算法： 基本思想：把待排序的n個元素放到一個中的任一個元素數(shù)組中，先取數(shù)組取數(shù)組中的某一個元素作為一個基準元素中的某一個元素作為一個基準元素，把這個元素放到數(shù)組中合適的位置，同時對其他元素進行調(diào)整，使得在這個基準元素的右邊的所有元素都比這個基準元素大，而基準元素左邊的元素都比它小。也就是說，這個基準元素當前所在的位置就是排序后的最終位置。然后再對基準元素的前后兩個區(qū)間分別進行快速排序，直到

10、每個區(qū)間為空后者只有一個元素時，整個快速排序結束。方法一：方法一： 取數(shù)組中的第一個第一個元素作為基準元素： 把待排序的數(shù)組按照基準元素分為左右兩部分的過程稱為快速排序的一次劃分（一趟排序）。 待排數(shù)組：a1 an。一次劃分的過程：設I，j兩個指針，開始時，i 1，j n，x ai：基準元素。如果aj=x 那么j j-1，直到找到ajx，然后：aj ai。procedure qsort(s,t:integer);s:待排序數(shù)組首元素下標待排序數(shù)組首元素下標,t:末尾元素下標末尾元素下標 var i,j:integer; x:integer; begin i:=s; j:=t; x:=as; x

11、:首元素為基準元素首元素為基準元素 while i=x) and(ji) do dec(j); 從未部找比從未部找比x小的元素小的元素aj if ji then begin ai:=aj; inc(i); end; 把把aj放在放在i處處,j處空著處空著 while (ai=x)and(ij) do inc(i); 繼續(xù)從前邊找比繼續(xù)從前邊找比x大元素大元素ai if ij then begin aj:=ai; dec(j); end; 把把ai移動到移動到j位置處位置處,i處空著處空著 end; ai:=x; 基準元素基準元素x放到合適的放到合適的i位置位置 if s(i-1) then q

12、sort(s,i-1); 對基準元素對基準元素x的的左左區(qū)間再進行快速排序區(qū)間再進行快速排序 if (i+1)t then qsort(i+1,t); 對基準元素對基準元素x的的右右區(qū)間再進行快速排序區(qū)間再進行快速排序 end;主程序的調(diào)用主程序的調(diào)用: qsort(1,n);方法二方法二:取中間元素為基準元素的算法取中間元素為基準元素的算法:procedure qsort(l,r:integer); var i,j,mid:integer; temp:integer; begin i:=l;j:=r; mid:=a(l+r) div 2; 將當前序列在中間位置的數(shù)定義為中間數(shù) repeat

13、while aimid do dec(j);在右半部分尋找比中間數(shù)小的數(shù) if ij; if lj then qsort(l,j); 若未到兩個數(shù)的邊界，則遞歸搜索左右區(qū)間 if ir then qsort(i,r); end;sort排序算法的應用排序算法的應用1、排隊接水、排隊接水 有有n個人排隊在一個水籠頭前接水，每個人的接水時間個人排隊在一個水籠頭前接水，每個人的接水時間互不相等。找出一種互不相等。找出一種n個人排隊接水的順序，使他們平均等個人排隊接水的順序，使他們平均等待的時間最短。待的時間最短。輸入：輸入： 第一行：第一行：n(tj then begin tem:=ti; ti:=

14、tj; tj:=tem; tem:=numi; numi:=numj; numj:=tem; end; 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.2、主油管的最優(yōu)位置主油管的最優(yōu)位置 Olay教授正在為一家石油公司咨詢。該公司正在設計建造一條由東向西的管道，該管道要穿過一個有n口井的油田。從每口井中都有一條噴油管沿最短路徑與主管道直接相連（或南或北）。 給定各個井的X和Y坐標，Olay教授如何才能選擇主

15、管道的最優(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); 每個油井的坐標 for i:=1 to n-1 do 冒泡排序縱坐標：從小到大 for j:=n downto i+1 do if yjyj-1 then begin k:=yj; yj:=yj-1; yj-1:=k; end; if n mod 2=1 then write(ytrunc(n+1)/2)

16、輸出中間值 else write(ytrunc(n/2), ,ytrunc(n/2+1); 輸出中間區(qū)間 end.3、成績排名、成績排名【問題描述：】【問題描述：】根據(jù)期末考試的成績單信息，把所有的學生按總分從高到低的順序輸出。根據(jù)期末考試的成績單信息，把所有的學生按總分從高到低的順序輸出。【輸入：】【輸入：】第一行：學生的個數(shù)第一行：學生的個數(shù)n（n=100）。）。以下以下n行：每行包含一個學生的信息，依次是：學號（行：每行包含一個學生的信息，依次是：學號（1.n）、姓名、語文）、姓名、語文成績、數(shù)學成績。他們中間有且僅有一個空格隔開，輸入信息中沒有多余的成績、數(shù)學成績。他們中間有且僅有一個

17、空格隔開，輸入信息中沒有多余的空格。姓名全是字母，長度不大于空格。姓名全是字母，長度不大于200，各科成績不超過，各科成績不超過100?！据敵觯骸俊据敵觯骸縉行，每行包含一個學生的信息：學號、姓名、總分。中間用一個空格隔開，行，每行包含一個學生的信息：學號、姓名、總分。中間用一個空格隔開，不能有多余的空格?？偡窒嗤膶W生，學號大的在前。不能有多余的空格?？偡窒嗤膶W生，學號大的在前?！緲永斎耄骸俊緲永斎耄骸?3 abc 40 502 gd 50 401 wr 60 604 dsd 10 20【樣例輸出：】【樣例輸出：】1 wr 1203 abc 902 gd 904 dsd 304、區(qū)間合

18、并、區(qū)間合并【樣例輸入：】【樣例輸入：】【問題描述：】【問題描述：】從鍵盤上任意輸入從鍵盤上任意輸入n個區(qū)間，然后按從小到大的順序依次輸出個區(qū)間，然后按從小到大的順序依次輸出n個區(qū)間個區(qū)間的并集。的并集。【輸入：】【輸入：】第一行，區(qū)間個數(shù)第一行，區(qū)間個數(shù)n（=1000）以下以下n行，每行兩個整數(shù)行，每行兩個整數(shù)a、b（-1000000000ab1000000000）,相相應區(qū)間的坐標，中間應區(qū)間的坐標，中間一個空格。一個空格?！据敵觯骸俊据敵觯骸?n個區(qū)間的并集，個區(qū)間的并集，n行，每行一個區(qū)間，坐標軸的左邊的區(qū)間先輸出。行，每行一個區(qū)間，坐標軸的左邊的區(qū)間先輸出?！緲永斎耄骸俊緲永斎耄?/p>

19、】3548【樣例輸出：】【樣例輸出：】1 57 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算法一：離散化算法一：離散化思路：思路： 設設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ū)

20、間。的區(qū)間。時間復雜度：時間復雜度： 10101212，只能過部分數(shù)據(jù)。，只能過部分數(shù)據(jù)。算法二：直接合并算法二：直接合并1 1、按每個區(qū)間的、按每個區(qū)間的左左端的的值升序排列。端的的值升序排列。 由于由于N=1000,N=1000,任意排序算法。任意排序算法。 注意數(shù)據(jù)結構的設置注意數(shù)據(jù)結構的設置: : 記錄類型記錄類型 二維數(shù)組：二維數(shù)組： a:array1.1000,1.2 of longint;a:array1.1000,1.2 of longint; a:array1.1000of array1.2 of longint a:array1.1000of array1.2 of lon

21、gint2 2、合并過程、合并過程 輸出第一個區(qū)間的左端點坐標（最小的）輸出第一個區(qū)間的左端點坐標（最小的） 依次處理后面的依次處理后面的 n-1 n-1 的區(qū)間。的區(qū)間。If aI,2=tailIf aI,2=tailTailTail不變不變If If (aI,1=tail)and(tail=aI,2)(aI,1=tail)and(tail=aI,2)Tail=aI,2Tail=aI,2If tailaI,1If tailaI,1Writeln(tail);Writeln(tail);Write(aI,1);Write(aI,1);Tail:=aI,2;Tail:=aI,2; write(a

22、1,1, ); write(a1,1, ); tail:=a1,2; tail:=a1,2; for i:=2 to n do for i:=2 to n do begin begin if (ai,1=tail)and(tail=ai,2) /2 if (ai,1=tail)and(tail=ai,2) /2 then tail:=ai,2; then tail:=ai,2; if tailai,1 then /3 if tailai,1 then /3 begin begin writeln(tail); writeln(tail); write(ai,1, ); write(ai,1,

23、); tail:=ai,2; tail:=ai,2; end; end; end; end; writeln(tail); writeln(tail);5、修理牛棚、修理牛棚 在一個暴風雨的夜晚在一個暴風雨的夜晚,農(nóng)民約翰的牛棚的屋頂、門被吹飛了。農(nóng)民約翰的牛棚的屋頂、門被吹飛了。 好在許多好在許多牛正在度假，所以牛棚沒有住滿。有些牛棚里有牛，有些沒有。牛正在度假，所以牛棚沒有住滿。有些牛棚里有牛，有些沒有。 所有的牛棚所有的牛棚有相同的寬度有相同的寬度,并且一個緊挨著另一個被排成一行。并且一個緊挨著另一個被排成一行。 自門遺失以后自門遺失以后,農(nóng)民約翰農(nóng)民約翰很快在牛棚門口之前豎立起新的木板

24、。很快在牛棚門口之前豎立起新的木板。 他的新木材供應者將會供應他任何他他的新木材供應者將會供應他任何他想要的長度想要的長度,但是供應者只能提供有限數(shù)目的木板。但是供應者只能提供有限數(shù)目的木板。 農(nóng)民約翰想將他購買的木農(nóng)民約翰想將他購買的木板總長度減到最少。板總長度減到最少。 給出可能買到的木板最大的數(shù)目給出可能買到的木板最大的數(shù)目M(1= M=50)；牛棚；牛棚的總數(shù)的總數(shù)S(1= S=200)；牛棚里牛的數(shù)目；牛棚里牛的數(shù)目C(1 = C =S)。牛所在的牛棚的編。牛所在的牛棚的編號號number(1 = number = S),計算攔住所有有牛的牛棚所需木板的最小總計算攔住所有有牛的牛棚所

25、需木板的最小總長度。長度。 輸出所需木板的最小總長度（每個牛棚的寬度為輸出所需木板的最小總長度（每個牛棚的寬度為1）作為的答案。）作為的答案。 輸入：輸入：第第1行：行：M S C（中間用空格分開）（中間用空格分開）第第 2行到行到c+1共共c行，每行一個個整數(shù)，表示牛所占的牛棚的編號。行，每行一個個整數(shù)，表示牛所占的牛棚的編號。輸出：單獨的一行包含一個整數(shù)，表示所需木板的最小總長度。輸出：單獨的一行包含一個整數(shù)，表示所需木板的最小總長度。樣例：樣例：輸入：輸入：4 50 183 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43 輸出：輸出：25

26、提示：提示： 一種最優(yōu)的安排是用板攔住牛棚一種最優(yōu)的安排是用板攔住牛棚3-8,14-21,25-31,40-43.6、潛水比賽、潛水比賽 在馬其頓王國舉行了一次潛水比賽。其中一個項目是從高山上跳下在馬其頓王國舉行了一次潛水比賽。其中一個項目是從高山上跳下水，再潛水達到終點。這是一個團體項目，一支隊伍由水，再潛水達到終點。這是一個團體項目，一支隊伍由n人組成。在潛水時必人組成。在潛水時必須使用氧氣瓶，但是每只隊伍只有一個氧氣瓶。最多兩人同時使用一個氧氣須使用氧氣瓶，但是每只隊伍只有一個氧氣瓶。最多兩人同時使用一個氧氣瓶，但此時兩人必須同步游泳，因此兩人達到終點的時間等于較慢的一個人瓶，但此時兩人必須同步游泳，因此兩人達到終點的時間等于較慢的一個人單獨游到終點所需要的時間。好在大家都很友好，因此任何兩個人后都愿意單獨游到終點所需要的時間。好在大家都很友好，因此任何兩個人后都愿意一起游水。安排一種潛水的策略，使得最后一名選手盡量的達到終點。一起游水。安排一種潛水的策略，使得最后一名選手盡量的達到終點。輸入：輸入：第一行：隊伍的人數(shù)第一行：隊伍的人數(shù)n（=1000）。）。第二行：第二行：n個數(shù)，分別是個數(shù)，分別是n個人潛水所用的時間個人潛水所用的時間ti(=