第6講排序算法及應用

第六講排序算法及應用劉建國昌邑市卜莊初中排序算法的種類：1、選擇排序2、冒泡排序3、插入排序4、快速排序5、堆排序1、選擇排序算法基本思想：

對待排序的序列進行n-1遍處理：第1遍處理是從a[1],a[2],……a[n]中選擇最小的放在a[1]位置；第2遍處理是從a[2],a[3],……a[n]中選擇最小的放在a[2]位置；……第I遍處理是將a[i],a[i+1],……a[n]中最小的數(shù)與a[i]交換位置，這樣經(jīng)過第i遍處理后，a[i]是所有的中的第i小。即前i個數(shù)就已經(jīng)排好序了。N-1遍處理后，剩下的最后一個一定是最大的，不需要再處理了。

a:待排序的數(shù)組；//從小到大排序簡單選擇排序：

fori:=1ton-1do{從第一個元素開始,進行n-1遍處理}

forj:=i+1tondo{第i遍處理}

Ifa[i]>a[j]then{交換a[i]和a[j]}

begint:=a[i];a[i]:=a[j];a[j]:=t;end;

算法的改進:減少交換次數(shù)fori:=1ton-1dobegink:=i;forj:=i+1tondoifa[j]<a[k]thenk:=j;ifk<>ithenbegint:=a[k];a[k]:=a[i];a[i]:=t;end;end;排序的關鍵字：20301015161382、冒泡排序算法：基本思想：（從小到大排序）將待排序的數(shù)據(jù)看作豎派排的一列”氣泡“，小的數(shù)據(jù)比較輕，從而要上浮。共進行n-1遍處理，每一遍處理，就是從底向上檢查序列，如果相鄰的兩個數(shù)據(jù)順序不對，即輕（?。┑脑谙旅妫徒粨Q他們的位置。第一遍處理完后，“最輕”的就浮到上面。第二遍處理完后，“次輕”的就浮到上面。共需要n-1遍處理即完成排序。//簡單的冒泡排序fori:=1ton-1doforj:=ndowntoi+1doifa[j]<a[j-1]thenbegint:=a[j];a[j]:=a[j-1];a[j-1]:=t;end;//判斷標志：flag=true已有序//改進后的冒泡排序fori:=1ton-1dobeginflag:=true;forj:=ndowntoi+1doifa[j]<a[j-1]thenbegint:=a[j];a[j]:=a[j-1];a[j-1]:=t;flag:=false;end;ifflag=truethenbreak;//某一輪沒有交換，說明都已經(jīng)有序了end;算法的改進關鍵字203040506010測定時間的方法：通過訪問MemL[Seg0040:$006C]來獲取當前時間，它返回的是當日零時到現(xiàn)在所經(jīng)過的時間，單位約為55毫秒（約1/18.2秒）。測定<語句組2>執(zhí)行的時間Starttime,endtime:longint;Starttime:=MemL[Seg0040:$006C];<語句組2>endtime:=MemL[Seg0040:$006C];Writeln((endtime-starttime)/18.2:0:2);語句組2運行的時間或：Writeln((MemL[Seg0040:$006C]-starttime)/18.2:0:2);StartTime:=MemL[Seg0040:$006C];fori:=1ton-1doforj:=ndowntoi+1doifa[j]<a[j-1]thenbegint:=a[j];a[j]:=a[j-1];a[j-1]:=t;end;writeln((MemL[Seg0040:$006c]-StartTime)/18.2:0:2);3、插入排序算法:基本思想：經(jīng)過i-1遍處理后，a[1],a[2],……,a[i-1]已排好序。第i遍處理是將元素a[i]插入到a[1],a[2],……,a[i-1]的適當?shù)奈恢?，從而使得a[1],a[2],……,a[i-1],a[i]又是排好的序列。a:array[0..n]ofinteger;{a[0]記錄當前待插元a[i]}fori:=2tondobegina[0]:=a[i];{取第i個元素作為待插入元素}j:=i-1;{從已排好的最后一個a[i-1]開始比較}whilea[0]<a[j]dobegina[j+1]:=a[j];{當待插入元素a[0]小于當前a[j]時，a[j]后移}j:=j-1;end;{當a[0]>=a[j]時循環(huán)結(jié)束}a[j+1]:=a[0];{在第j+1個位置插入a[i]元素}end;4、快速排序算法：基本思想：把待排序的n個元素放到一個中的任一個元素數(shù)組中，先取數(shù)組中的某一個元素作為一個基準元素，把這個元素放到數(shù)組中合適的位置，同時對其他元素進行調(diào)整，使得在這個基準元素的右邊的所有元素都比這個基準元素大，而基準元素左邊的元素都比它小。也就是說，這個基準元素當前所在的位置就是排序后的最終位置。然后再對基準元素的前后兩個區(qū)間分別進行快速排序，直到每個區(qū)間為空后者只有一個元素時，整個快速排序結(jié)束。方法一：取數(shù)組中的第一個元素作為基準元素：把待排序的數(shù)組按照基準元素分為左右兩部分的過程稱為快速排序的一次劃分（一趟排序）。待排數(shù)組：a[1]……a[n]。一次劃分的過程：設I，j兩個指針，開始時，i←1，j←n，x←a[i]：基準元素。如果a[j]>=x那么j←j-1，直到找到a[j]<x，然后a[i]←a[j]，同時i←i+1,找一個a[i]>x，然后：a[j]←a[i]。procedureqsort(s,t:integer);{s:待排序數(shù)組首元素下標,t:末尾元素下標}vari,j:integer;x:integer;begini:=s;j:=t;x:=a[s];{x:首元素為基準元素}whilei<jdobeginwhile(a[j]>=x)and(j>i)dodec(j);{從未部找比x小的元素a[j]}ifj>ithenbegina[i]:=a[j];inc(i);end;{把a[j]放在i處,j處空著}while(a[i]<=x)and(i<j)doinc(i);{繼續(xù)從前邊找比x大元素a[i]}ifi<jthenbegina[j]:=a[i];dec(j);end;{把a[i]移動到j位置處,i處空著}end;a[i]:=x;{基準元素x放到合適的i位置}ifs<(i-1)thenqsort(s,i-1);{對基準元素x的左區(qū)間再進行快速排序}if(i+1)<tthenqsort(i+1,t);{對基準元素x的右區(qū)間再進行快速排序}end;主程序的調(diào)用:qsort(1,n);方法二:取中間元素為基準元素的算法:procedureqsort(l,r:integer);vari,j,mid:integer;temp:integer;begini:=l;j:=r;mid:=a[(l+r)div2];{將當前序列在中間位置的數(shù)定義為中間數(shù)}repeatwhilea[i]<middoinc(i);{在左半部分尋找比中間數(shù)大的數(shù)}whilea[j]>middodec(j);{在右半部分尋找比中間數(shù)小的數(shù)}ifi<=jthenbegin{若找到一組與排序目標不一致的數(shù)對則交換它們}temp:=a[i];a[i]:=a[j];a[j]:=temp;inc(i);dec(j);{繼續(xù)找}end;untili>j;ifl<jthenqsort(l,j);{若未到兩個數(shù)的邊界，則遞歸搜索左右區(qū)間}ifi<rthenqsort(i,r);end;{sort}排序算法的應用1、排隊接水有n個人排隊在一個水籠頭前接水，每個人的接水時間互不相等。找出一種n個人排隊接水的順序，使他們平均等待的時間最短。輸入：第一行：n(<100).第二行：依次為n個人的接水時間。輸出：第一行：所有人的平均等待時間。第二行：接水的順序。樣例：輸入：526138輸出：8.4031425varnum,t:array[1..100]ofinteger;n,i,j,sum,tem:integer;beginreadln(n);fori:=1tondoread(t[i]);fori:=1tondonum[i]:=i;fori:=1ton-1doforj:=i+1tondoift[i]>t[j]thenbegintem:=t[i];t[i]:=t[j];t[j]:=tem;tem:=num[i];num[i]:=num[j];num[j]:=tem;end;sum:=0;fori:=1tondosum:=sum+(n+1-i)*t[i];writeln(sum/n:0:2);fori:=1ton-1dowrite(num[i],'');writeln(num[n]);end.2、主油管的最優(yōu)位置Olay教授正在為一家石油公司咨詢。該公司正在設計建造一條由東向西的管道，該管道要穿過一個有n口井的油田。從每口井中都有一條噴油管沿最短路徑與主管道直接相連（或南或北）。給定各個井的X和Y坐標，Olay教授如何才能選擇主管道的最優(yōu)位置（即使得個噴管長度總和最小的位置）。輸入：3233754輸出：4varx,y:array[1..100]ofinteger;n,i,j,k,m:integer;beginread(n);{油井個數(shù)}fori:=1tondoread(x[i],y[i]);{每個油井的坐標}fori:=1ton-1do{冒泡排序縱坐標：從小到大}forj:=ndowntoi+1doify[j]<y[j-1]thenbegink:=y[j];y[j]:=y[j-1];y[j-1]:=k;end;ifnmod2=1thenwrite(y[trunc((n+1)/2)]){輸出中間值}elsewrite(y[trunc(n/2)],‘’,y[trunc(n/2+1)]);{輸出中間區(qū)間}end.3、成績排名【問題描述：】根據(jù)期末考試的成績單信息，把所有的學生按總分從高到低的順序輸出?！据斎耄骸康谝恍校簩W生的個數(shù)n（n<=100）。以下n行：每行包含一個學生的信息，依次是：學號（1..n）、姓名、語文成績、數(shù)學成績。他們中間有且僅有一個空格隔開，輸入信息中沒有多余的空格。姓名全是字母，長度不大于200，各科成績不超過100。【輸出：】N行，每行包含一個學生的信息：學號、姓名、總分。中間用一個空格隔開，不能有多余的空格?？偡窒嗤膶W生，學號大的在前?！緲永斎耄骸?3abc40502gd50401wr60604dsd1020【樣例輸出：】1wr1203abc902gd904dsd304、區(qū)間合并【樣例輸入：】【問題描述：】從鍵盤上任意輸入n個區(qū)間，然后按從小到大的順序依次輸出n個區(qū)間的并集?！据斎耄骸康谝恍校瑓^(qū)間個數(shù)n（<=1000）以下n行，每行兩個整數(shù)a、b（-1000000000<a<b<1000000000）,相應區(qū)間的坐標，中間一個空格?！据敵觯骸縩個區(qū)間的并集，n行，每行一個區(qū)間，坐標軸的左邊的區(qū)間先輸出?！緲永斎耄骸?548【樣例輸出：】1578區(qū)間的合并注意：1、區(qū)間個數(shù)n的范圍（<=1000）2、區(qū)間的數(shù)據(jù)類型和范圍：整數(shù)類型、-109--109算法一：離散化思路：◆設f[i]:0..1,初始值全部為0。◆每讀入一個區(qū)間abFori:=1tonForj:=atobdof[j]=1◆最后輸出f[j]=1的區(qū)間。時間復雜度：1012，只能過部分數(shù)據(jù)。算法二：直接合并1、按每個區(qū)間的左端的的值升序排列。由于N<=1000,任意排序算法。注意數(shù)據(jù)結(jié)構(gòu)的設置:

◆記錄類型

◆二維數(shù)組：a:array[1..1000,1..2]oflongint;a:array[1..1000]ofarray[1..2]oflongint2、合并過程◆輸出第一個區(qū)間的左端點坐標（最小的）◆依次處理后面的n-1的區(qū)間。Ifa[I,2]<=tailTail不變If(a[I,1]<=tail)and(tail<=a[I,2])Tail=a[I,2]Iftail<a[I,1]Writeln(tail);Write(a[I,1]);Tail:=a[I,2];write(a[1,1],'');tail:=a[1,2];fori:=2tondobeginif(a[i,1]<=tail)and(tail<=a[i,2])//2thentail:=a[i,2];iftail<a[i,1]then//3beginwriteln(tail);write(a[i,1],'');tail:=a[i,2];end;end;writeln(tail);5、修理牛棚

在一個暴風雨的夜晚,農(nóng)民約翰的牛棚的屋頂、門被吹飛了。好在許多牛正在度假，所以牛棚沒有住滿。有些牛棚里有牛，有些沒有。所有的牛棚有相同的寬度,并且一個緊挨著另一個被排成一行。自門遺失以后,農(nóng)民約翰很快在牛棚門口之前豎立起新的木板。他的新木材供應者將會供應他任何他想要的長度,但是供應者只能提供有限數(shù)目的木板。農(nóng)民約翰想將他購買的木板總長度減到最少。給出可能買到的木板最大的數(shù)目M(1<=M<=50)；牛棚的總數(shù)S(1<=S<=200)；牛棚里牛的數(shù)目C(1<=C<=S)。牛所在的牛棚的編號number(1<=number<=S),計算攔住所有有牛的牛棚所需木板的最小總長度。輸出所需木板的最小總長度（每個牛棚的寬度為1）作為的答案。

輸入：第1行：MSC（中間用空格分開）第2行到c+1共c行，每行一個個整數(shù)，表示牛所占的牛棚的編號。輸出：單獨的一行包含一個整數(shù)，表示所需木板的最小總長度。樣例：輸入：4501834681415161721252627303140414243輸出：25

[提示：一種最優(yōu)的安排是用板攔住牛棚3-8,14-21,25-31,40-43.]6、潛水比賽

在馬其頓王國舉行了一次潛水比賽。其中一個項目是從高山上跳下水，再潛水達到終點。這是一個團體項目，一支隊伍由n人組成。在潛水時必須使用氧氣瓶，但是每只隊伍只有一個氧氣瓶。最多兩人同時使用一個氧氣瓶，但此時兩人必須同步游泳，因此兩人達到終點的時間等于較慢的一個人單獨游到終點所需要的時間。好在大家都很友好，因此任何兩個人后都愿意一起游水。安排一種潛水的策略，使得最后一名選手盡量的達到終點。輸入：第一行：隊伍的人數(shù)n（<=1000）。第二行：n個數(shù)，分別是n個人潛水所用的時間ti(<=1000)。樣例：輸入：3134輸出：8分析:先從簡單入手:1)n=2,時間t:110所需的時間為:102)n=3,時間t:134所需的時間為:3+1+4=83)n=4,時間t:1101112所需的時間為:10+1+11+1+12=35貪心策略方法一:N個人:每個人所需的時間:t1，t2，……tn。假設t1最小。每次由t1接送人和氧氣瓶，則總時間：s=t2+t3+。。。。tn+（n-2）*t14）n=4，每個人所用時間：1258采用貪心策略方法一：計算所用的總時間為：2+5+8+1*2=17事實上：采用下面策略：第一步：12一起先過，用時：2第二步：1送回氧氣瓶，用時：1第三步：58一起過，用時：8第四步：2送回氧氣瓶，用時：2第五步：1和2一起過去，用時：2完成。共用時：2+1+8+2+2=15<17貪心策略方法二:將n個人的時間從小到達排序，假設從小到大為：t1，t2，……tn1：t1和t2過：t22：t1帶瓶返回：t13：最大的兩個人：tnt