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

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

對待排序的序列進(jìn)行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{從第一個元素開始,進(jìn)行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;

算法的改進(jìn):減少交換次數(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;排序的關(guān)鍵字：20301015161382、冒泡排序算法：基本思想：（從小到大排序）將待排序的數(shù)據(jù)看作豎派排的一列”氣泡“，小的數(shù)據(jù)比較輕，從而要上浮。共進(jìn)行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;//判斷標(biāo)志：flag=true已有序//改進(jìn)后的冒泡排序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;算法的改進(jìn)關(guān)鍵字203040506010測定時間的方法：通過訪問MemL[Seg0040:$006C]來獲取當(dāng)前時間，它返回的是當(dāng)日零時到現(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運(yùn)行的時間或：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]的適當(dāng)?shù)奈恢?，從而使得a[1],a[2],……,a[i-1],a[i]又是排好的序列。a:array[0..n]ofinteger;{a[0]記錄當(dāng)前待插元a[i]}fori:=2tondobegina[0]:=a[i];{取第i個元素作為待插入元素}j:=i-1;{從已排好的最后一個a[i-1]開始比較}whilea[0]<a[j]dobegina[j+1]:=a[j];{當(dāng)待插入元素a[0]小于當(dāng)前a[j]時，a[j]后移}j:=j-1;end;{當(dāng)a[0]>=a[j]時循環(huán)結(jié)束}a[j+1]:=a[0];{在第j+1個位置插入a[i]元素}end;4、快速排序算法：基本思想：把待排序的n個元素放到一個中的任一個元素?cái)?shù)組中，先取數(shù)組中的某一個元素作為一個基準(zhǔn)元素，把這個元素放到數(shù)組中合適的位置，同時對其他元素進(jìn)行調(diào)整，使得在這個基準(zhǔn)元素的右邊的所有元素都比這個基準(zhǔn)元素大，而基準(zhǔn)元素左邊的元素都比它小。也就是說，這個基準(zhǔn)元素當(dāng)前所在的位置就是排序后的最終位置。然后再對基準(zhǔn)元素的前后兩個區(qū)間分別進(jìn)行快速排序，直到每個區(qū)間為空后者只有一個元素時，整個快速排序結(jié)束。方法一：取數(shù)組中的第一個元素作為基準(zhǔn)元素：把待排序的數(shù)組按照基準(zhǔn)元素分為左右兩部分的過程稱為快速排序的一次劃分（一趟排序）。待排數(shù)組：a[1]……a[n]。一次劃分的過程：設(shè)I，j兩個指針，開始時，i←1，j←n，x←a[i]：基準(zhǔn)元素。如果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ù)組首元素下標(biāo),t:末尾元素下標(biāo)}vari,j:integer;x:integer;begini:=s;j:=t;x:=a[s];{x:首元素為基準(zhǔn)元素}whilei<jdobeginwhile(a[j]>=x)and(j>i)dodec(j);{從未部找比x小的元素a[j]}ifj>ithenbegina[i]:=a[j];inc(i);end;{把a(bǔ)[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(bǔ)[i]移動到j(luò)位置處,i處空著}end;a[i]:=x;{基準(zhǔn)元素x放到合適的i位置}ifs<(i-1)thenqsort(s,i-1);{對基準(zhǔn)元素x的左區(qū)間再進(jìn)行快速排序}if(i+1)<tthenqsort(i+1,t);{對基準(zhǔn)元素x的右區(qū)間再進(jìn)行快速排序}end;主程序的調(diào)用:qsort(1,n);方法二:取中間元素為基準(zhǔn)元素的算法:procedureqsort(l,r:integer);vari,j,mid:integer;temp:integer;begini:=l;j:=r;mid:=a[(l+r)div2];{將當(dāng)前序列在中間位置的數(shù)定義為中間數(shù)}repeatwhilea[i]<middoinc(i);{在左半部分尋找比中間數(shù)大的數(shù)}whilea[j]>middodec(j);{在右半部分尋找比中間數(shù)小的數(shù)}ifi<=jthenbegin{若找到一組與排序目標(biāo)不一致的數(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}排序算法的應(yīng)用1、排隊(duì)接水有n個人排隊(duì)在一個水籠頭前接水，每個人的接水時間互不相等。找出一種n個人排隊(duì)接水的順序，使他們平均等待的時間最短。輸入：第一行：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教授正在為一家石油公司咨詢。該公司正在設(shè)計(jì)建造一條由東向西的管道，該管道要穿過一個有n口井的油田。從每口井中都有一條噴油管沿最短路徑與主管道直接相連（或南或北）。給定各個井的X和Y坐標(biāo)，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]);{每個油井的坐標(biāo)}fori:=1ton-1do{冒泡排序縱坐標(biāo)：從小到大}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ù)期末考試的成績單信息，把所有的學(xué)生按總分從高到低的順序輸出?！据斎耄骸康谝恍校簩W(xué)生的個數(shù)n（n<=100）。以下n行：每行包含一個學(xué)生的信息，依次是：學(xué)號（1..n）、姓名、語文成績、數(shù)學(xué)成績。他們中間有且僅有一個空格隔開，輸入信息中沒有多余的空格。姓名全是字母，長度不大于200，各科成績不超過100?！据敵觯骸縉行，每行包含一個學(xué)生的信息：學(xué)號、姓名、總分。中間用一個空格隔開，不能有多余的空格。總分相同的學(xué)生，學(xué)號大的在前?！緲永斎耄骸?3abc40502gd50401wr60604dsd1020【樣例輸出：】1wr1203abc902gd904dsd304、區(qū)間合并【樣例輸入：】【問題描述：】從鍵盤上任意輸入n個區(qū)間，然后按從小到大的順序依次輸出n個區(qū)間的并集?！据斎耄骸康谝恍校瑓^(qū)間個數(shù)n（<=1000）以下n行，每行兩個整數(shù)a、b（-1000000000<a<b<1000000000）,相應(yīng)區(qū)間的坐標(biāo)，中間一個空格。【輸出：】n個區(qū)間的并集，n行，每行一個區(qū)間，坐標(biāo)軸的左邊的區(qū)間先輸出?！緲永斎耄骸?548【樣例輸出：】1578區(qū)間的合并注意：1、區(qū)間個數(shù)n的范圍（<=1000）2、區(qū)間的數(shù)據(jù)類型和范圍：整數(shù)類型、-109--109算法一：離散化思路：◆設(shè)f[i]:0..1,初始值全部為0。◆每讀入一個區(qū)間abFori:=1tonForj:=atobdof[j]=1◆最后輸出f[j]=1的區(qū)間。時間復(fù)雜度：1012，只能過部分?jǐn)?shù)據(jù)。算法二：直接合并1、按每個區(qū)間的左端的的值升序排列。由于N<=1000,任意排序算法。注意數(shù)據(jù)結(jié)構(gòu)的設(shè)置:

◆記錄類型

◆二維數(shù)組：a:array[1..1000,1..2]oflongint;a:array[1..1000]ofarray[1..2]oflongint2、合并過程◆輸出第一個區(qū)間的左端點(diǎn)坐標(biāo)（最小的）◆依次處理后面的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、修理牛棚

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

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

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

在馬其頓王國舉行了一次潛水比賽。其中一個項(xiàng)目是從高山上跳下水，再潛水達(dá)到終點(diǎn)。這是一個團(tuán)體項(xiàng)目，一支隊(duì)伍由n人組成。在潛水時必須使用氧氣瓶，但是每只隊(duì)伍只有一個氧氣瓶。最多兩人同時使用一個氧氣瓶，但此時兩人必須同步游泳，因此兩人達(dá)到終點(diǎn)的時間等于較慢的一個人單獨(dú)游到終點(diǎn)所需要的時間。好在大家都很友好，因此任何兩個人后都愿意一起游水。安排一種潛水的策略，使得最后一名選手盡量的達(dá)到終點(diǎn)。輸入：第一行：隊(duì)伍的人數(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。假設(shè)t1最小。每次由t1接送人和氧氣瓶，則總時間：s=t2+t3+。。。。tn+（n-2）*t14）n=4，每個人所用時間：1258采用貪心策略方法一：計(jì)算所用的總時間為：2+5+8+1*2=17事實(shí)上：采用下面策略：第一步：12一起先過，用時：2第二步：1送回氧氣瓶，用時：1第三步：58一起過，用時：8第四步：2送回氧氣瓶，用時：2第五步：1和2一起過去，用時：2完成。共用時：2+1+8+2+2=15<17貪心策略方法二:將n個人的時間從小到達(dá)排序，假設(shè)從小到大為：t1，t2，……tn1：t1和t2過：t22：t1帶瓶返回：t13：最大的兩個人：tnt