第2講 排序算法及應(yīng)用

1、第二講排序算法及應(yīng)用第二講排序算法及應(yīng)用排序算法的種類：排序算法的種類：1、選擇排序、選擇排序2、冒泡排序、冒泡排序3、插入排序、插入排序4、快速排序、快速排序5、堆排序、堆排序1、選擇排序、選擇排序算法基本思想：算法基本思想： 對待排序的序列進(jìn)行對待排序的序列進(jìn)行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,ana i ,a i+1,

2、an中最小的數(shù)與中最小的數(shù)與a i a i 交換位置，這交換位置，這樣經(jīng)過第樣經(jīng)過第i i遍處理后，遍處理后，aiai是所有的中的第是所有的中的第i i小。即前小。即前i i個(gè)數(shù)就已經(jīng)排個(gè)數(shù)就已經(jīng)排好序了。好序了。N-1N-1遍處理后，剩下的最后一個(gè)一定是最大的，不需要再處理了。遍處理后，剩下的最后一個(gè)一定是最大的，不需要再處理了。排序的關(guān)鍵字：排序的關(guān)鍵字：20 30 10 15 16 13 8第第i個(gè)和后邊的依次比較，找最小的放在個(gè)和后邊的依次比較，找最小的放在i處。處。a:待排序的數(shù)組；待排序的數(shù)組；/從小到大排序從小到大排序簡單選擇排序：簡單選擇排序：for i:=1 to n-1 d

3、o 從第一個(gè)元素開始從第一個(gè)元素開始,進(jìn)行進(jìn)行n-1遍處理遍處理 for j:=i+1 to n do 第第i遍處理遍處理 If aiaj then 交換交換ai和和aj begin t:=ai; ai:=aj; aj:=t; end; /簡單選擇排序簡單選擇排序:從小到大從小到大const maxn=1000;var n,i,j,t:integer; a:array1.maxn of integer;begin randomize; /隨機(jī)過程初始化隨機(jī)過程初始化 readln(n); for i:=1 to n do ai:=random(1000); /產(chǎn)生產(chǎn)生n個(gè)個(gè)0,999之間的整數(shù)

4、。之間的整數(shù)。 for i:=1 to n-1 do for j:=i+1 to n do if aiaj then begin t:=ai; ai:=aj; aj:=t; end; for i:=1 to n-1 do write(ai, ); writeln(an);end.算法的改進(jìn)算法的改進(jìn): 減少交換次數(shù)減少交換次數(shù)排序的關(guān)鍵字：排序的關(guān)鍵字：20 30 10 15 16 13 8 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; a

5、i:=t; end; end;2、冒泡排序算法：、冒泡排序算法：基本思想基本思想：（從小到大排序）：（從小到大排序） 將待排序的數(shù)據(jù)看作豎派排的一列將待排序的數(shù)據(jù)看作豎派排的一列”氣泡氣泡“，小的數(shù)據(jù)，小的數(shù)據(jù)比較輕，從而要上浮。比較輕，從而要上浮。共進(jìn)行共進(jìn)行n-1遍處理，每一遍處理，就是從底向上檢查序列，遍處理，每一遍處理，就是從底向上檢查序列，如果如果相鄰相鄰的兩個(gè)數(shù)據(jù)順序不對，即輕（?。┑脑谙旅?，就交的兩個(gè)數(shù)據(jù)順序不對，即輕（?。┑脑谙旅妫徒粨Q他們的位置。換他們的位置。 第一遍處理完后，第一遍處理完后，“最輕最輕”的就浮到上面。的就浮到上面。 第二遍處理完后，第二遍處理完后，“次輕次

6、輕”的就浮到上面。的就浮到上面。 共需要共需要n-1遍處理即完成排序。遍處理即完成排序。排序的關(guān)鍵字：從小到排序的關(guān)鍵字：從小到大大20 30 10 15 16 13 8/ 簡單的冒泡排序簡單的冒泡排序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;算法的改進(jìn)算法的改進(jìn)關(guān)鍵字關(guān)鍵字 20 30 40 50 60 10/ 判斷標(biāo)志：判斷標(biāo)志： flag=true 已有序已有序/改進(jìn)后的冒泡排序改進(jìn)后的冒泡排序for i:=1 to n-1 do begin f

7、lag:=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)有序了 end;3、插入排序算法、插入排序算法:基本思想：基本思想：經(jīng)過經(jīng)過i-1i-1遍處理后，遍處理后，a1,a2,ai-1a1,a2,ai-1已排好序。已排好序。第第i i遍處理是將元素遍處理是將元素aiai插入到插入到a1,a2,ai-1a1,a2,ai-1的適當(dāng)?shù)奈恢茫瑥牡倪m當(dāng)?shù)奈?/p>

8、置，從而使得而使得a1,a2,ai-1,aia1,a2,ai-1,ai又是排好的序列。又是排好的序列。排序的關(guān)鍵字：從小到排序的關(guān)鍵字：從小到大大20 30 10 15 16 13 8a:array0.n of integer; a:array0.n of integer; a0a0記錄當(dāng)前待插元記錄當(dāng)前待插元aiaifor i:=2 to n dofor i:=2 to n do begin begin a0:=ai; a0:=ai; 取第取第i i個(gè)元素作為待插入元素個(gè)元素作為待插入元素 j:=i-1; j:=i-1; 從已排好的最后一個(gè)從已排好的最后一個(gè)ai-1ai-1開始比較開始比較

9、while a0aj do / while a0aj do / 找找j j滿足：滿足： aj=a0aj+1aj=a0=aja0=aj時(shí)循環(huán)結(jié)束時(shí)循環(huán)結(jié)束 aj+1:=a0; aj+1:=a0; 在第在第j+1j+1個(gè)位置插入個(gè)位置插入aiai元素元素 end; end;4、快速排序算法：、快速排序算法： 基本思想：把待排序的基本思想：把待排序的n個(gè)元素放到一個(gè)中的任一個(gè)元素?cái)?shù)組中，先個(gè)元素放到一個(gè)中的任一個(gè)元素?cái)?shù)組中，先取數(shù)組取數(shù)組中的某一個(gè)元素作為一個(gè)基準(zhǔn)元素中的某一個(gè)元素作為一個(gè)基準(zhǔn)元素，把這個(gè)元素放到數(shù)組中合適的位置，同時(shí)，把這個(gè)元素放到數(shù)組中合適的位置，同時(shí)對其他元素進(jìn)行調(diào)整，使得在這

10、個(gè)基準(zhǔn)元素的右邊的所有元素都比這個(gè)基準(zhǔn)元對其他元素進(jìn)行調(diào)整，使得在這個(gè)基準(zhǔn)元素的右邊的所有元素都比這個(gè)基準(zhǔn)元素大，而基準(zhǔn)元素左邊的元素都比它小。也就是說，這個(gè)基準(zhǔn)元素當(dāng)前所在的素大，而基準(zhǔn)元素左邊的元素都比它小。也就是說，這個(gè)基準(zhǔn)元素當(dāng)前所在的位置就是排序后的最終位置。然后再對基準(zhǔn)元素的前后兩個(gè)區(qū)間分別進(jìn)行快速位置就是排序后的最終位置。然后再對基準(zhǔn)元素的前后兩個(gè)區(qū)間分別進(jìn)行快速排序，直到每個(gè)區(qū)間為空后者只有一個(gè)元素時(shí)，整個(gè)快速排序結(jié)束。排序，直到每個(gè)區(qū)間為空后者只有一個(gè)元素時(shí)，整個(gè)快速排序結(jié)束。方法：方法： 取數(shù)組中的取數(shù)組中的第一個(gè)第一個(gè)元素作為基準(zhǔn)元素：元素作為基準(zhǔn)元素： 把待排序的數(shù)組按

11、照基準(zhǔn)元素分為左右兩部分的過程稱為快速排序的一次把待排序的數(shù)組按照基準(zhǔn)元素分為左右兩部分的過程稱為快速排序的一次劃分（一趟排序）。劃分（一趟排序）。 待排數(shù)組：待排數(shù)組：a1 an。一次劃分的過程：一次劃分的過程：設(shè)設(shè)I，j兩個(gè)指針，開始時(shí)，兩個(gè)指針，開始時(shí)，i 1，j n，x ai：基準(zhǔn)元素。如果：基準(zhǔn)元素。如果aj=x 那么那么j j-1，直到找到，直到找到ajx，然，然后：后：aj ai。35 12 37 15 40 31 50 30 29 6035 12 37 15 40 31 50 30 29 606 629 12 30 15 31 35 50 40 37 603 315 12 29

12、 30 31 35 50 40 37 602 212 15 29 30 31 35 50 40 37 604 412 15 29 30 31 35 50 40 37 609 912 15 29 30 31 35 37 40 50 607 712 15 29 30 31 35 37 40 50 6012 15 29 30 31 35 37 40 50 60procedure qsort(s,t:integer);s:待排序數(shù)組首元素下標(biāo)待排序數(shù)組首元素下標(biāo),t:末尾元素下標(biāo)末尾元素下標(biāo) var i,j:integer; x:integer; begin i:=s; j:=t; x:=as; x:

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

14、ort(s,i-1); 對基準(zhǔn)元素對基準(zhǔn)元素x的的左左區(qū)間再進(jìn)行快速排序區(qū)間再進(jìn)行快速排序 if (i+1)t then qsort(i+1,t); 對基準(zhǔn)元素對基準(zhǔn)元素x的的右右區(qū)間再進(jìn)行快速排序區(qū)間再進(jìn)行快速排序 end;主程序的調(diào)用主程序的調(diào)用: qsort(1,n);const maxn=10000;/快速排序源程序快速排序源程序var a:array1.maxn of integer; n,i:integer; procedure qsort(l,r:integer); var i,j:integer; x:integer; begin i:=l; j:=r; x:=al; whil

15、e i=x) and(ji) do dec(j); if ij then begin ai:=aj; inc(i); end; while (aii) do inc(i); if ij then begin aj:=ai; dec(j); end; end; ai:=x; /i=j if l(i-1) then qsort(l,i-1); if (i+1)r then qsort(i+1,r); end;begin randomize; readln(n); for i:= 1 to n do ai:=random(100); for i:=1 to n-1 do write(ai, ); w

16、riteln(an); qsort(1,n); for i:=1 to n-1 do write(ai, ); writeln(an);end.排序算法的應(yīng)用排序算法的應(yīng)用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;

17、 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教授正在為一家石油公司咨詢。該公司正在設(shè)計(jì)建造教授正在為一家石油公司咨詢。該公司正在設(shè)計(jì)建造一條由東向西的管道，該管道要穿過一個(gè)有一條由東向西的管道，該管道要穿過一個(gè)有n口井的油田。口井的油田。從每口井中都有一條噴油管沿最短路徑與主管道直接相連從每口井中都有一條噴油管沿最短路徑與主管道直接相連（或南或北

18、）。（或南或北）。 給定各個(gè)井的給定各個(gè)井的X和和Y坐標(biāo)，坐標(biāo)，Olay教授如何才能選擇主管道教授如何才能選擇主管道的最優(yōu)位置（即使得個(gè)噴管長度總和最小的位置）。的最優(yōu)位置（即使得個(gè)噴管長度總和最小的位置）。輸入：輸入：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:=i+1 downto n do if yiy

19、j then begin k:=yi; yi:=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個(gè)區(qū)間，然后按從小到大的順序依次輸出個(gè)區(qū)間，然后按從小到大的順序依次輸出n個(gè)區(qū)間個(gè)區(qū)間的并集。的并集?！据斎耄骸俊据斎耄骸康谝恍校瑓^(qū)間個(gè)數(shù)第一行，區(qū)間個(gè)數(shù)n（=1000）以下以下n行，每行兩個(gè)整數(shù)行，每行兩個(gè)整數(shù)a、b（-1000000000ab1000

20、000000）,相相應(yīng)區(qū)間的坐標(biāo)，中間應(yīng)區(qū)間的坐標(biāo)，中間一個(gè)空格。一個(gè)空格?！据敵觯骸俊据敵觯骸?n個(gè)區(qū)間的并集，個(gè)區(qū)間的并集，n行，每行一個(gè)區(qū)間，坐標(biāo)軸的左邊的區(qū)間先輸出。行，每行一個(gè)區(qū)間，坐標(biāo)軸的左邊的區(qū)間先輸出?！緲永斎耄骸俊緲永斎耄骸?2 51 47 8 【樣例輸出：】【樣例輸出：】1 57 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,初始

21、值全部為初始值全部為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ù)結(jié)構(gòu)的設(shè)置注意數(shù)據(jù)結(jié)構(gòu)的設(shè)置: : 記錄類型記錄類型 二維數(shù)組：二維數(shù)

22、組： 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 longint2 2、合并過程、合并過程 輸出第一個(gè)區(qū)間的左端點(diǎn)坐標(biāo)（最小的）輸出第一個(gè)區(qū)間的左端點(diǎn)坐標(biāo)（最小的） 依次處理后面的依次處理后面的 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(tai

23、l=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(a1,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,

24、2; then tail:=ai,2; if tailai,1 then /3 if tailaj,1 then begin t:=ai; ai:=aj; aj:=t; end; end;procedure main; var i:integer; tail:longint; begin assign(output,fout);rewrite(output); write(a1,1, ); tail:=a1,2; for i:=2 to n do begin if (ai,1=tail)and(tail=ai,2) then tail:=ai,2; if tailai,1 then begin

25、 writeln(tail); write(ai,1, ); tail:=ai,2; end; end; writeln(tail); close(output); end;/主程序主程序begin init; main;end.4、潛水比賽、潛水比賽 在馬其頓王國舉行了一次潛水比賽。其中一個(gè)項(xiàng)目是從高山上跳下在馬其頓王國舉行了一次潛水比賽。其中一個(gè)項(xiàng)目是從高山上跳下水，再潛水達(dá)到終點(diǎn)。這是一個(gè)團(tuán)體項(xiàng)目，一支隊(duì)伍由水，再潛水達(dá)到終點(diǎn)。這是一個(gè)團(tuán)體項(xiàng)目，一支隊(duì)伍由n人組成。在潛水時(shí)必人組成。在潛水時(shí)必須使用氧氣瓶，但是每只隊(duì)伍只有一個(gè)氧氣瓶。最多兩人同時(shí)使用一個(gè)氧氣須使用氧氣瓶，但是每只隊(duì)伍只有

26、一個(gè)氧氣瓶。最多兩人同時(shí)使用一個(gè)氧氣瓶，但此時(shí)兩人必須同步游泳，因此兩人達(dá)到終點(diǎn)的時(shí)間等于較慢的一個(gè)人瓶，但此時(shí)兩人必須同步游泳，因此兩人達(dá)到終點(diǎn)的時(shí)間等于較慢的一個(gè)人單獨(dú)游到終點(diǎn)所需要的時(shí)間。好在大家都很友好，因此任何兩個(gè)人后都愿意單獨(dú)游到終點(diǎn)所需要的時(shí)間。好在大家都很友好，因此任何兩個(gè)人后都愿意一起游水。安排一種潛水的策略，使得最后一名選手盡量的達(dá)到終點(diǎn)。一起游水。安排一種潛水的策略，使得最后一名選手盡量的達(dá)到終點(diǎn)。輸入：輸入：第一行：隊(duì)伍的人數(shù)第一行：隊(duì)伍的人數(shù)n（=1000）。）。第二行：第二行：n個(gè)數(shù)，分別是個(gè)數(shù)，分別是n個(gè)人潛水所用的時(shí)間個(gè)人潛水所用的時(shí)間ti(=1000)。樣例：

27、樣例：輸入：輸入：31 3 4輸出：輸出：8分析分析:先從簡單入手先從簡單入手:1) n=2 ,時(shí)間時(shí)間 t: 1 10 所需的時(shí)間為所需的時(shí)間為:102) n=3, 時(shí)間時(shí)間 t: 1 3 4所需的時(shí)間為所需的時(shí)間為:3+1+4=83) n=4 ,時(shí)間時(shí)間 t: 1 10 11 12 所需的時(shí)間為所需的時(shí)間為:10+1+11+1+12=35貪心策略方法一貪心策略方法一: N個(gè)人個(gè)人: 每個(gè)人所需的時(shí)間每個(gè)人所需的時(shí)間: t1，t2，tn。假設(shè)。假設(shè)t1最小。最小。 每次由每次由t1接送人和氧氣瓶，則接送人和氧氣瓶，則總時(shí)間：總時(shí)間：s=t2+t3+。tn+（n-2）*t14）n=4 ，每個(gè)人

28、所用時(shí)間：，每個(gè)人所用時(shí)間：1 2 5 8采用 貪心策略方法一：貪心策略方法一：計(jì)算所用的總時(shí)間為：計(jì)算所用的總時(shí)間為：2+5+8+1*2=17事實(shí)上：采用下面策略：事實(shí)上：采用下面策略：第一步：第一步： 1 2一起先過，一起先過， 用時(shí)：用時(shí)：2第二步：第二步： 1 送回氧氣瓶，送回氧氣瓶， 用時(shí)：用時(shí)：1第三步：第三步： 5 8一起過，一起過， 用時(shí)：用時(shí)： 8第四步：第四步： 2送回氧氣瓶，送回氧氣瓶， 用時(shí)：用時(shí)：2第五步：第五步： 1 和和2一起過去，一起過去， 用時(shí)：用時(shí)：2 完成。完成。 共用時(shí)：共用時(shí)：2+1+8+2+2=15y then 用用t1送送 else 用用t1和和t

29、2送送貪心三算法：貪心三算法：數(shù)組數(shù)組a存時(shí)間：存時(shí)間：把時(shí)間從小到大排序。把時(shí)間從小到大排序。sum:=0; if odd(n) then begin sum:=sum+a2+a1+a3 end else sum:=sum+a2; i:=n; while i3 do begin x:=2*a2+a1+ai; 用用a1和和a2送一趟送一趟 y:=2*a1+ai+ai-1; 用用a1送一趟送一趟 if xy then sum:=sum+x else sum:=sum+y; dec(i,2); i=i-2:每趟送兩人每趟送兩人 end; writeln(sum);1、成績排名、成績排名【問題描述：

30、】【問題描述：】根據(jù)期末考試的成績單信息，把所有的學(xué)生按總分從高到低的順序輸出。根據(jù)期末考試的成績單信息，把所有的學(xué)生按總分從高到低的順序輸出?！据斎耄骸俊据斎耄骸康谝恍校簩W(xué)生的個(gè)數(shù)第一行：學(xué)生的個(gè)數(shù)n（n=100）。）。以下以下n行：每行包含一個(gè)學(xué)生的信息，依次是：學(xué)號（行：每行包含一個(gè)學(xué)生的信息，依次是：學(xué)號（1.n）、姓名、語文）、姓名、語文成績、數(shù)學(xué)成績。他們中間有且僅有一個(gè)空格隔開，輸入信息中沒有多余的成績、數(shù)學(xué)成績。他們中間有且僅有一個(gè)空格隔開，輸入信息中沒有多余的空格。姓名全是字母，長度不大于空格。姓名全是字母，長度不大于200，各科成績不超過，各科成績不超過100?！据敵觯骸俊据敵觯骸縉行，每行包含一個(gè)學(xué)生的信息：學(xué)號、姓名、總分。中間用一個(gè)空格隔開，行，每行包含一個(gè)學(xué)生的信息：學(xué)號、姓名、總分。中間用一個(gè)空格隔開，不能有多余的空格?？偡窒嗤膶W(xué)生，學(xué)號大的在