數(shù)據(jù)結(jié)構(gòu)與算法 課件 第6、7章 圖結(jié)構(gòu)、內(nèi)部排序

全國高等教育自學(xué)考試指定教材

計算機及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第六章圖結(jié)構(gòu)學(xué)習(xí)目標(biāo)理解圖的定義和相關(guān)的基本概念掌握圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)掌握圖基本操作的實現(xiàn)掌握并實現(xiàn)圖的深度優(yōu)先和廣度優(yōu)先搜索算法，理解圖的連通性及連通分量概念理解圖的生成樹概念，掌握求圖最小代價生成樹的兩個算法理解有向無環(huán)圖的概念，掌握圖的拓?fù)渑判蛩惴?，掌握關(guān)鍵路徑算法理解最短路徑概念，掌握迪杰斯特拉算法和弗洛伊德算法的求解過程了解各算法的時間復(fù)雜度本章主要內(nèi)容圖的基本概念12圖基本操作的實現(xiàn)3圖的存儲結(jié)構(gòu)圖的遍歷4圖的生成樹56最短路徑7DAG圖及其應(yīng)用第一節(jié)圖的基本概念圖（graph）由頂點和邊組成一般地，用G=(V,E)來表示，其中V表示頂點（vertex）集，是一個有窮非空集合；E表示邊（edge）集，E中的每條邊都是V中某一對頂點的連接當(dāng)頂點分別是u和v時，連接這兩個頂點的邊可以表示為一個二元組(u,v)，有時也將邊稱為頂點的偶對圖中任意兩個不同頂點之間允許有邊，但不能超過一條基本概念圖G=(V,E)中，頂點總數(shù)記為|V|，邊的總數(shù)記為|E|如果圖中邊的數(shù)目較少（相對于頂點數(shù)來說），則圖稱為稀疏圖邊數(shù)較多的圖稱為密集圖或是稠密圖至于邊數(shù)多到多少是密集圖或少到多少是稀疏圖，并沒有嚴(yán)格的界定當(dāng)圖中邊數(shù)的數(shù)量級不高于頂點數(shù)的數(shù)量級時，就可以認(rèn)為圖是稀疏圖基本概念當(dāng)圖中的邊限定為從一個頂點指向另一個頂點時，稱為有向邊，或稱為弧（arc）不限定方向的邊稱為無向邊一條無向邊可以看成是兩條方向相反的有向邊組成有向邊的偶對看作是有序的組成無向邊的偶對是無序的基本概念有向邊(u,v)表示從頂點u指向頂點v的邊，弧的方向是從u指向v，u稱為弧尾（tail），v稱為弧頭（head）對于有向邊，(u,v)與(v,u)不同無向邊(u,v)既可以表示從頂點u指向頂點v，也可以表示從頂點v指向頂點u對于無向邊，(u,v)與(v,u)是等價的基本概念含有向邊的圖稱為有向圖（directedgraph或簡寫為digraph）如果圖中的邊都是無向邊，則圖稱為無向圖（undirectedgraph或簡寫為undigraph）如果一個圖中既含有有向邊，又含有無向邊，則可以將其中所有的無向邊表示為一對方向相反的有向邊提到有向圖時，表明其中所含的邊全部都是有向邊基本概念若無向圖G中含有邊(u,v)，則u和v互為鄰接點（adjacent）邊(u,v)稱為與頂點u和v相關(guān)聯(lián)（incident），也可以說邊(u,v)依附于頂點u和v對于有向圖中的有向邊(u,v)，稱頂點v是頂點u的鄰接點頂點u鄰接到頂點v，或頂點v鄰接自頂點u可以給邊賦予一個非負(fù)的數(shù)值，這個非負(fù)數(shù)值稱為邊的權(quán)（weight），相應(yīng)的圖稱為帶權(quán)圖（weightedgraph）或是加權(quán)圖可以讓各頂點帶有標(biāo)號，這樣的圖稱為標(biāo)號圖（labedledgraph）本章討論的圖大多是標(biāo)號圖，標(biāo)號可以作為頂點的名稱示例圖中兩個頂點之間的邊不能有重復(fù)無向圖中兩個頂點之間最多只能有一條邊有向圖中兩個頂點之間最多有兩條方向相反的弧圖中不包含(i,i)形式的邊，即沒有頂點自身到自身的邊在無向圖中，與頂點v相關(guān)聯(lián)的邊的數(shù)目稱為頂點的度（degree）在有向圖中，頂點的度分為出度和入度以某頂點為弧頭的弧稱為該頂點的入邊，入邊的數(shù)目稱為該頂點的入度以某頂點為弧尾的弧稱為該頂點的出邊，出邊的數(shù)目稱為該頂點的出度一個頂點的出度和入度之和稱為該頂點的度有n個頂點的無向圖中，其邊數(shù)最多可達n(n-1)/2有向圖中由于邊具有方向性，所以可能的最大邊數(shù)比無向圖多了一倍，含n個頂點的有向圖中最大邊數(shù)為n(n-1)

包含了所有可能邊的圖稱為完全圖（completegraph）

若兩個圖G=(V,E)和G'=(V',E')，滿足條件：V’V，E’E且E'中邊依附的頂點均屬于V'，則稱G'為G的子圖（subgraph）一個圖G的子圖是指由圖G中選出其頂點集的一個子集Vs以及僅與Vs中頂點相關(guān)聯(lián)的一些邊所構(gòu)成的圖例6-3對于圖G，圖G1、G2、G3和G4都是它的子圖；特別地，圖G1與圖G完全一樣，它也是圖G的子圖，即圖本身也是它自身的子圖；同時，圖G2也是圖G4的子圖。而圖G5不是圖G的子圖在圖G=(V,E)中，如果(vi0,vi1),(vi1,vi2),…,(vim-2,vim-1)都是E中的邊，則頂點序列(vi0,vi1,…,vim-1)稱為從頂點vi0到頂點vim-1的路徑（path）若圖G是有向圖，則路徑也要求是有向的，且有向邊必須是方向一致的，即有向路徑(vi0,vi1,…,vim-1)是由E中的弧(vi0,vi1),(vi1,vi2),…,(vim-2,vim-1)組成的路徑(vi0,vi1,…,vim-1)中包含的邊或弧的數(shù)目m稱為路徑長度如果路徑上各頂點均不同，則稱此路徑為簡單路徑（simplepath）第一個頂點和最后一個頂點相同的路徑稱為回路（cycle），也稱為環(huán)如果一個回路中除第一個頂點和最后一個頂點之外，其余頂點均不相同，則稱為簡單回路（simplecycle）或簡單環(huán)不帶回路的圖稱為無環(huán)圖。不帶回路的有向圖稱為有向無環(huán)圖從頂點0到頂點3到頂點4再到頂點1構(gòu)成一條有向簡單路徑(0,3,4,1)，路徑長度為3從頂點2到頂點3到頂點4再回到頂點2構(gòu)成一個簡單有向回路(2,3,4,2)從頂點2到頂點0再到頂點3，雖然其中均有邊相連，但由于邊的方向不一致，所以不能構(gòu)成有向路徑對于無向圖G，如果頂點u和頂點v之間有路徑，則稱這兩個頂點是連通的如果無向圖G中任意一個頂點到其他任意頂點都至少存在一條路徑，也就是說，圖中任意兩個頂點都是連通的，則稱圖G為連通圖（connectedgraph）無向圖中的極大連通子圖稱為連通分量（connectedcomponent）有向圖G中，如果每對頂點u與v之間均有從u到v的有向路徑，則稱G為強連通圖（stronglyconnectedgraph）有向圖的最大強連通子圖稱為強連通分量如果對于每對頂點u和v，存在頂點序列vi0,vi1,…,vim-1，這里u=vi0，v=vim-1，并且(vij,vij+1)∈E或(vij+1,vij)∈E(0≤j≤m-2)，則稱圖G為弱連通圖（weaklyconnectedgraph）示例例6-5設(shè)無向圖G含有10個頂點和6條邊，則G中連通分量的個數(shù)最多可能是多少？最少可能是多少？要讓G中連通分量最多，可以讓某些頂點與盡可能多的邊相關(guān)聯(lián)，且這些頂點組成盡可能少的連通分量。6條邊可以讓4個頂點組成完全圖，其余的6個頂點均為孤立頂點，則G含有7個連通分量圖的基本操作VType表示頂點類型MEdge表示邊的類型圖的基本操作定義頂點使用單字符表示，保存在頂點表verticesList[MaxVtxNum]中，使用兩個輔助方法，在頂點字符與頂點表下標(biāo)之間進行轉(zhuǎn)換intVerToNum(MGraphg,VTypeu) //返回頂點u在頂點表verticesList中的下標(biāo)值VType

NumToVer(MGraphg,inti) //返回頂點表verticesList中下標(biāo)i對應(yīng)的頂點第二節(jié)圖的存儲結(jié)構(gòu)圖也有兩類基本的存儲方式，即順序存儲結(jié)構(gòu)及鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu)以鄰接矩陣為代表鏈?zhǔn)酱鎯Y(jié)構(gòu)以鄰接表為代表鄰接矩陣設(shè)圖G=(V,E)，|V|=n，圖的鄰接矩陣是一個n

n矩陣，矩陣元素表示圖中各頂點之間的鄰接關(guān)系，鄰接矩陣也稱為相鄰矩陣設(shè)各頂點為v0,v1,…,vn-1，如果從vi到vj存在一條邊，則鄰接矩陣中位于i行j列的元素值為1，否則值為0這樣的一個矩陣可以表示圖中所有頂點之間的鄰接關(guān)系鄰接矩陣的存儲空間與頂點個數(shù)有關(guān)，為O(|V|2)鄰接矩陣是一個二維數(shù)組對于帶權(quán)圖鄰接矩陣是對稱矩陣有向圖的鄰接矩陣不能保證對稱性例6-7若無向圖G中含有n個頂點和e條邊，則它的鄰接矩陣中0的個數(shù)是多少？根據(jù)圖鄰接矩陣的定義，因為圖G中含有n個頂點，所以鄰接矩陣中元素個數(shù)為n2。無向圖的鄰接矩陣是對稱矩陣，對G中的任一條邊(vi,vj)，在鄰接矩陣中都會對應(yīng)兩個1，即A[i][j]和A[j][i]均為1。所以圖G的鄰接矩陣中有2e個1，0的個數(shù)為n2-2e用鄰接矩陣表示圖時，可以很容易地判定圖中任意兩頂點之間是否存在邊（或?。┤艟仃囋谹[i][j]為1或wij，就表示從vi到vj有一條邊（或?。?，否則從vi到vj沒有邊（或?。┐嬖诮柚卩徑泳仃?，很容易得到圖中各頂點的度對于無向圖G，鄰接矩陣i行或i列中非零元素的個數(shù)即為頂點vi的度對于有向圖G，鄰接矩陣i行中非零（也不等于∞）元素的個數(shù)為頂點vi的出度而i列中非零（也不等于∞）元素的個數(shù)為頂點vi的入度i行非零（也不等于∞）元素的個數(shù)加上i列非零（也不等于∞）元素的個數(shù)為頂點vi的度設(shè)用鄰接矩陣表示有n個頂點的圖G，計算G中有多少條邊時，需要檢查矩陣中的所有元素，因此時間復(fù)雜度為O(n2)存儲空間僅與圖G中的頂點數(shù)有關(guān)，與邊數(shù)無關(guān)，即為O(n2)設(shè)圖G=(V,E)，則G的鄰接表由一個一維數(shù)組和n=|V|個鏈表組成一維數(shù)組包含n個元素，每個元素包含表示頂點信息的域和一個指針域與頂點vi(0≤i≤n-1)相鄰接的所有頂點組成一個單鏈表，其表頭指針保存在一維數(shù)組下標(biāo)為i的元素的指針域中鄰接表鄰接表表結(jié)點的結(jié)構(gòu)對于帶權(quán)圖，可以擴展鄰接表的結(jié)構(gòu)，在單鏈表的每個表結(jié)點中增加一個域，用來存儲兩個頂點間這條邊的權(quán)表結(jié)點結(jié)構(gòu)對于有向圖，如果將所有有向弧的方向轉(zhuǎn)向，則得到的新圖的鄰接表稱為原圖的逆鄰接表例6-8無向圖的鄰接表有向圖的鄰接表和逆鄰接表用鄰接表表示有n個頂點和e條邊的無向圖時，需要一個由n個元素組成的順序表（表頭結(jié)點表）和由總共2e個結(jié)點組成的n個單鏈表表示有n個頂點e條弧的有向圖時，需要一個由n個元素組成的順序表和由總共e個結(jié)點組成的n個單鏈表鄰接表的空間復(fù)雜度為O(n+e)當(dāng)圖中頂點個數(shù)經(jīng)常變化時，為便于頂點的插入和刪除，也可以將圖的全部頂點保存在一個單鏈表中，而不是一維數(shù)組中。單鏈表中的結(jié)點結(jié)構(gòu)如下所示指向下一頂點的指針指向鄰接點表的指針頂點信息第三節(jié)圖基本操作的實現(xiàn)采用鄰接矩陣存儲的圖的定義頂點表的相應(yīng)查詢查詢邊的權(quán)值創(chuàng)建圖創(chuàng)建無向圖創(chuàng)建有向帶權(quán)圖驗證圖構(gòu)建函數(shù)的正確性找到某頂點的第一個鄰接點查找下一個鄰接點獲取頂點個數(shù)及邊數(shù)intgetNumVertices(MGraphg){ returng.numVertices;}intgetNumEdges(MGraphg){ returng.numEdges;}第四節(jié)圖的遍歷定義6-1給定一個連通圖G=(V,E)，從圖中的某個頂點出發(fā)，經(jīng)過一定的路線訪問圖中的所有頂點，使每個頂點被訪問且只訪問一次，這一過程稱為圖的遍歷深度優(yōu)先搜索（depthfirstsearch,DFS）遍歷廣度優(yōu)先搜索（breadthfirstsearch,BFS）遍歷深度優(yōu)先搜索選擇圖中任意指定頂點為起始頂點，將其設(shè)為當(dāng)前頂；訪問當(dāng)前頂點v，輸出關(guān)于v的相關(guān)信息將v的訪問標(biāo)志置為VISITED如果v的鄰接點中存在未被訪問的頂點w，則將w設(shè)為當(dāng)前頂點，轉(zhuǎn)②繼續(xù)；否則轉(zhuǎn)⑤回退到最近被訪問過的且仍有未被訪問鄰接點的頂點u，轉(zhuǎn)④繼續(xù)；不能回退時，轉(zhuǎn)⑥如果所有頂點均已訪問，則遍歷結(jié)束，否則，選擇未被訪問的另一個頂點作為起始頂點，繼續(xù)上述過程v0,v1,v3,v7,v4,v5,v2,v6DFS算法當(dāng)圖是連通圖時，使用DFS算法從某個頂點出發(fā)，可以訪問到圖中的所有頂點。如果圖不連通，則一次調(diào)用DFS不能訪問圖中的全部頂點，只能訪問初始頂點所在的連通分量中的所有頂點廣度優(yōu)先搜索選擇圖中指定的頂點v為起始頂點，將其入隊列，且其訪問標(biāo)志置為VISITED隊列為空時，轉(zhuǎn)⑤；隊列不為空時，出隊列，設(shè)出隊列的頂點為w輸出關(guān)于w的相關(guān)信息找到與頂點w相鄰接的且訪問標(biāo)志不是VISITED的頂點序列w1,w2,…,wk，依次入隊列，轉(zhuǎn)②如果所有頂點均已訪問，則遍歷結(jié)束，否則，選擇未被訪問的一個頂點作為起始頂點，繼續(xù)上述過程廣度優(yōu)先搜索過程中，使用了一個隊列作為輔助存儲結(jié)構(gòu)，頂點是一批批加入隊列的如果圖是不連通的，則這個過程也不能訪問圖中的全部頂點，而只能遍歷圖中某個連通分量中的所有頂點BFS算法第五節(jié)圖的生成樹設(shè)G=(V,E)是一個連通的無向圖，包含圖中全部頂點的極小連通子圖稱為圖的生成樹極小連通子圖是指含有圖中所有頂點并使圖仍保持連通性的最小子圖從圖中任一頂點出發(fā)，按照深度優(yōu)先搜索策略或是廣度優(yōu)先搜索策略，可以訪問到圖中的全部頂點。在遍歷的過程中，所經(jīng)過的邊集設(shè)為T(G)，沒有經(jīng)過的邊集設(shè)為B(G)。T(G)即構(gòu)成G的一棵生成樹生成樹中所含的邊數(shù)必定是n-1進行深度優(yōu)先搜索時得到的生成樹稱為深度優(yōu)先生成樹進行廣度優(yōu)先搜索時得到的生成樹稱為廣度優(yōu)先生成樹進行遍歷時可能會得到不同的頂點序列，實際上，圖的生成樹也可能是不唯一的同一個圖的深度優(yōu)先生成樹，也可能不是唯一的廣度優(yōu)先生成樹，也可能不是唯一的示例兩棵深度優(yōu)先生成樹圖的最小代價生成樹帶權(quán)圖的每條邊上都有一個非負(fù)的權(quán)值，稱邊權(quán)值之和最小的生成樹為最小代價生成樹（minimum_costspanningtree，MST）。簡稱為最小生成樹給定一個無向連通圖G，則MST是一個包括G的所有頂點及其邊子集的圖，邊的子集滿足下列條件這個子集中所有邊的權(quán)之和為所有滿足條件的子集中最小的子集中的邊能夠保證圖是連通的最小生成樹性質(zhì)它含有圖G中的所有n個頂點它沒有回路。因為從構(gòu)成回路的各邊中去掉一條邊，仍能保證其連通性，而所得的權(quán)值總和可以進一步地減少它含有的邊數(shù)為n-1去掉最小生成樹中的一條邊，換上不在最小生成樹中的另外一條邊，在仍要求連通的前提下，所得的權(quán)值總和都不會小于原最小生成樹的權(quán)值總和普里姆算法設(shè)連通的帶權(quán)圖G=(V,E)，V是頂點集合，E是邊的集合設(shè)T是圖G的最小生成樹的邊集合，U是最小生成樹的頂點集合，設(shè)由頂點v1開始，初始時T=Ф，U={v1}在所有u∈U，v∈V-U的邊(u,v)∈E中選擇一條權(quán)最小的邊(ui,vj)，將vj并入U中，將邊(ui,vj)并入T中重復(fù)②，直到U=V時結(jié)束示例程序普里姆算法是貪心算法的一個實例，每次選出一條連接U中頂點及V-U中頂點的具有最小權(quán)值的邊，逐步生成最小生成樹普里姆算法共進行n-1輪的選邊操作，每輪選邊時，最多從n-1條邊中選中權(quán)最小的邊。故對于含|V|個頂點的圖，算法的時間復(fù)雜度為O(|V|2)當(dāng)圖是一個邊稠密的圖時，適合使用普里姆算法求圖的最小生成樹克魯斯卡爾算法設(shè)E1的初值：E1=Φ，T中只含有圖中的所有頂點，頂點個數(shù)為n=|V|當(dāng)E1中邊數(shù)小于n-1時，重復(fù)執(zhí)行下面的步驟在圖G的邊集E中選擇權(quán)值最小的邊(u,v)，并從E中刪除它如果u和v分別屬于T中不同的連通分量，則將邊(u,v)加入到E1中去，否則丟掉該邊，選擇E中的下一條權(quán)值最小的邊邊權(quán)值(6,8)2(7,8)2(5,8)3(1,3)4(3,4)5(4,7)5(1,4)6(1,2)6(3,7)6(2,5)7(2,6)7(5,6)10(4,5)14程序克魯斯卡爾算法中，從|E|條邊中選出權(quán)值最小的邊(u,v)，并檢測u和v是不是在同一連通分量上，時間花費為O(|E|log|E|)。所以，克魯斯卡爾算法適宜求稀疏圖的最小生成樹第六節(jié)有向無環(huán)圖及其應(yīng)用圖中不存在回路的有向圖稱為有向無環(huán)圖（directedacyclinegraph），簡稱為DAG圖比如，表達式樹可表示為DAG圖拓?fù)渑判蛴邢驘o環(huán)圖G=(V,E)的拓?fù)湫蛄惺荊中頂點的一個線性序列，并且滿足以下關(guān)系：對于圖G中的所有頂點v和w，如果(v,w)∈E，則在線性序列中v排在w之前求有向無環(huán)圖拓?fù)湫蛄械倪^程稱為拓?fù)渑判蛟谟邢驁D中，以頂點表示活動，有向邊表示活動之間的優(yōu)先關(guān)系，這樣的有向圖稱為頂點表示活動的網(wǎng)絡(luò)（activityonvertexnetwork），簡稱為AOV網(wǎng)在AOV網(wǎng)中，若從頂點vi到vj有一條有向路徑，則稱vi是vj的前驅(qū)，vj是vi的后繼若(vi,vj)是AOV網(wǎng)中的一條弧，則稱vi是vj的直接前驅(qū)，vj是vi的直接后繼如果vi是vj的前驅(qū)或直接前驅(qū)，則vi活動必須在vj活動開始之前結(jié)束，即vj活動必須在vi活動結(jié)束之后才能開始在AOV網(wǎng)中不允許出現(xiàn)回路，因此AOV網(wǎng)必是有向無環(huán)圖拓?fù)渑判蚩梢詫OV網(wǎng)中的各個活動排序，它把AOV網(wǎng)中各頂點按照它們之間的先后關(guān)系排成一個線性序列在AOV網(wǎng)中，如果從頂點vi到頂點vj存在有向路徑，則在拓?fù)湫蛄兄?，vi必定排在vj的前面；如果從頂點vi到頂點vj沒有有向路徑，則在拓?fù)湫蛄兄?，vi與vj的先后次序可以任意五門課程排成的拓?fù)湫蛄袨?C1,C2,C3,C4,C5還可以排列成 C1,C2,C5,C3,C4課程代號課程名稱先導(dǎo)課C1高等數(shù)學(xué)無C2程序設(shè)計基礎(chǔ)無C3數(shù)據(jù)結(jié)構(gòu)C2C4編譯原理C3C5算法分析C1,C2遵循的原則在拓?fù)湫蛄兄校總€頂點都必須排在它的后繼頂點之前。那么排在最前面的頂點一定不能是其他任何頂點的后繼有向圖中一個頂點的直接前驅(qū)數(shù)即是頂點的入度值，可以使用一個一維數(shù)組來記錄各個頂點的入度值如果一個頂點不是其他任何頂點的后繼，就意味著該頂點的入度值為0初始化時，數(shù)組中填入各頂點的入度值，可以將入度值看作是一個頂點的約束條件個數(shù)基于廣度優(yōu)先搜索策略實現(xiàn)拓?fù)渑判蛲負(fù)渑判蜃裱脑瓌t是，在拓?fù)湫蛄兄?，每個頂點都必須排在它的后繼頂點之前有向圖中一個頂點的直接前驅(qū)數(shù)即是頂點的入度值，可以使用一個一維數(shù)組來記錄各個頂點的入度值如果一個頂點不是其他任何頂點的后繼，就意味著該頂點的入度值為0初始化時，數(shù)組中填入各頂點的入度值，可以將入度值看作是一個頂點的約束條件個數(shù)求AOV網(wǎng)的拓?fù)湫蛄械牟襟E初始化：記錄AOV網(wǎng)中所有頂點的入度值選一個沒有前驅(qū)（入度為0）的頂點，輸出之從圖中刪除該頂點和以它為尾的所有的弧，即將輸出頂點的所有后繼頂點的入度值減1。轉(zhuǎn)②步驟②、③重復(fù)執(zhí)行，每輸出一個頂點，就修改入度值數(shù)組，然后再選擇滿足條件的頂點輸出，再修改數(shù)組直至輸出全部頂點或者還沒有輸出全部頂點，但已找不到?jīng)]有前驅(qū)的頂點（即入度值為0的頂點）為止第一種情況表示拓?fù)渑判蛞呀?jīng)完成第二種情況表明原有向圖中含有回路建立入度值表靜態(tài)鏈表在入度值表中，那些入度值為0的頂點的“入度值”域的值都是0，所以可以用這個域在入度值表中建立一個靜態(tài)鏈表，專門將入度值為0的頂點鏈接起來來，方便后面的選擇初始建立入度值表時，將入度值為0的頂點逐一插入到這個靜態(tài)鏈表中入度值表建立完成時，靜態(tài)鏈表的初始化也即完成當(dāng)同時有多個入度值為0的頂點時，拓?fù)渑判虿⒉粡娭戚敵銎渲械哪囊粋€，所以將滿足要求的頂點插入靜態(tài)鏈表時，可以插入在表頭位置，這樣的插入效率最高輸出入度值為0的頂點時，即是從靜態(tài)鏈表的表頭位置刪除一個結(jié)點，輸出其中保存的頂點根據(jù)存儲結(jié)構(gòu)尋找輸出頂點的鄰接點并修正入度值表時，遇到修正后值為0的頂點，將其插入到靜態(tài)鏈表的表頭入度值表的結(jié)構(gòu)typedefstruct{

VType

ver; intindeg;}IndegreeV;IndegreeV

indegreeTable[MaxVtxNum];建立入度值表的實現(xiàn)first是入度為0的靜態(tài)鏈表的表頭指針程序基于入度值表的拓?fù)渑判蛩惴ǔ绦蚧谏疃葍?yōu)先搜索策略實現(xiàn)拓?fù)渑判驅(qū)D進行深度優(yōu)先搜索時，改變頂點輸出的條件。不是在遇到一個頂點時即刻輸出頂點，而是等到該頂點的所有鄰接點都輸出了才輸出該頂點，將得到的頂點序列逆序，即可得到圖的拓?fù)渑判虺绦蜿P(guān)鍵路徑可以使用帶權(quán)有向圖表示一個含多個活動的工程。在這樣的圖中，用頂點表示事件，用弧表示活動，邊上的權(quán)值表示活動持續(xù)的時間，這樣組成的網(wǎng)稱為以邊表示活動的網(wǎng)，簡稱為AOE網(wǎng)在AOE網(wǎng)中，通常只有一個入度為0的點和一個出度為0的點。入度為0的點稱為起始點或源點，出度為0的點稱為結(jié)束點或匯點一個工程中的某些子活動是可以并行進行的；從源點到匯點最長路徑的長度，即該路徑上所有活動持續(xù)時間之和，就是完成整個工程所需的最少時間將從源點到匯點具有最大長度的路徑稱為關(guān)鍵路徑關(guān)鍵路徑上的所有活動稱為關(guān)鍵活動求關(guān)鍵路徑是帶權(quán)有向無環(huán)圖的一個重要應(yīng)用一個含有8個活動的工程，其中頂點1是源點，頂點6是匯點從頂點1到頂點6的所有路徑中，路徑長度最大為8，表明這項工程至少需要8天才能完成在AOE網(wǎng)中，從源點v1到任意頂點vi的最長路徑長度叫做事件vi的最早開始時間。這個時間決定了所有以vi為尾的弧所表示的活動的最早開始時間另外，在不推遲整個工程完成的前提下，活動ai最遲必須開始進行的時間稱作活動ai的最遲開始時間用e(i)表示活動ai的最早開始時間，l(i)表示其最遲開始時間。兩者之差l(i)-e(i)意味著完成活動ai的時間余量ai的實際開始時間可以在e(i)到l(i)之間任意調(diào)整，而絲毫不會影響整個工程的完成時間把l(i)=e(i)的活動稱作關(guān)鍵活動，即關(guān)鍵活動的最早開始時間和最遲開始時間相等，它們沒有時間余量顯然，關(guān)鍵路徑上的所有活動都是關(guān)鍵活動，關(guān)鍵活動的推延將直接導(dǎo)致整個工程的推延，而提前完成非關(guān)鍵活動并不能加快整個工程的進度設(shè)活動ai由弧(j,k)表示，其持續(xù)時間記為dut(j,k)，事件的最早開始時間為ve(j)，最遲開始時間為vl(j)，則有如下關(guān)系：e(i)=ve(j)l(i)=vl(k)-dut(j,k)求ve(j)和vl(j)將采用遞推的方法，分兩步進行：①從ve(1)=0開始向前遞推 ve(j)=max{ve(i)+dut(i,j)}(i,j)∈T，2≤j≤n其中T是所有以頂點j為頭的弧的集合。②從vl(n)=ve(n)起向后遞推 vl(i)=min{vl(j)–dut(i,j)}(i,j)∈S，1≤i≤n-1其中S是所有以頂點i為尾的弧的集合計算ve時，從事件1開始向前遞推計算vl時，從最后一個事件開始，向后遞推求關(guān)鍵路徑的算法①輸入e條弧(j,k)，建立AOE網(wǎng)的存儲結(jié)構(gòu)②從源點v1出發(fā)，令ve[1]=0，按拓?fù)湫蛄星笃溆喔黜旤c的最早發(fā)生時間ve[i](2≤i≤n)。如果得到的拓?fù)湫蛄兄许旤c個數(shù)小于AOE網(wǎng)中頂點數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟③③從匯點vn出發(fā)，令vl[n]=ve[n]，按逆拓?fù)湫蛄星笃溆喔黜旤c的最遲發(fā)生時間vl[i](n-1≥i≥1)④根據(jù)各頂點的ve和vl值，求每條弧s的最早開始時間e(s)和最遲開始時間l(s)。若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動例6-17求下圖所示工程的關(guān)鍵路徑，列出關(guān)鍵活動事件vevl100234322466567688活動ell-ea1011a2000a3341a4341a5220a6253a7660a8671時間余量為0的活動即是關(guān)鍵活動，這些活動是a2、a5和a7關(guān)鍵路徑是1、3、4、6，路徑長度是8第七節(jié)最短路徑對于帶權(quán)圖，修改路徑長度概念兩個頂點之間的路徑長度定義為兩頂點間路徑上各邊的權(quán)值之和路徑的開始頂點稱為源點，目的頂點稱為終點求從某個源點到圖中其他各頂點的最短路徑稱為單源最短路徑（single-sourceshortestpaths）問題，即，已知圖G=(V,E)，找出從某個給定源點s∈V到V中任一其他頂點的最短路徑示例終點最短路徑路徑長度b(a,d,b)3c(a,c)5d(a,d)2e(a,d,e)5f(a,d,g,f)8g(a,d,g)6Dijkstra算法求帶權(quán)圖單源最短路徑的算法稱為迪杰斯特拉（Dijkstra）算法它按照路徑長度不減的次序產(chǎn)生最短路徑，也就是生成的各條路徑的長度越來越長基本思想是：把圖中的所有頂點分成兩個集合，令S表示已求出最短路徑的頂點集合，其余尚未確定最短路徑的頂點組成另一個集合V-S。初始時，S中僅含有源點。按最短路徑長度不減的次序逐個把第二個集合V-S中的頂點加入到S中，不斷擴大已求出最短路徑的頂點集合，直到從源點出發(fā)可以到達的所有頂點都在S中為止給圖中每個頂點定義一個距離值，分兩種情況S集合中頂點對應(yīng)的距離值就是從源點到此頂點的最短路徑長度集合V-S中頂點對應(yīng)的距離值是從源點到此頂點、且路徑中僅包括S中的頂點為中間頂點的最短路徑的長度當(dāng)有V-S中的頂點加入S時，對S中頂點的距離值沒有影響，而有可能使V-S中頂點的距離值變小對于V-S中的所有頂點如果距離值確實變小了，則以變化后的值替代原來的值如果距離值沒有變小，則保持原值不變設(shè)圖G=(V,E)，源點為v0，引入輔助數(shù)組distdist[i]表示對應(yīng)于頂點i的距離值dist的初值為Dijkstra算法的步驟（1）初始化

①設(shè)用帶權(quán)的鄰接矩陣cost表示帶權(quán)有向圖G=(V,E)

②cost[i][j]為弧(vi,vj)上的權(quán)值

（若弧(vi,vj)不存在，則該值為∞，一般地取計算機中能表示的最大值）

③S為已找到從源點v0出發(fā)的最短路徑的終點集合，其初態(tài)只含有源點v0

④從v0出發(fā)到圖中其余各頂點vi的距離值為 dist[i]=cost[v0][vi] vi∈V（2）選擇vj，使得dist[j]=min{dist[i]|vi∈V-S} vj即當(dāng)前求得的一條從v0出發(fā)的最短路徑的終點。令S=S∪{vj}（3）修改從v0出發(fā)到集合V-S上任一頂點vk可達的最短路徑長度

如果dist[j]+cost[j][k]<dist[k]，則dist[k]=dist[j]+cost[j][k]（4）重復(fù)執(zhí)行（2）、（3），直到再也沒有可加入到S中的頂點時為止示例所有頂點間的最短路徑求得所有頂點間的最短路徑，可以用弗洛伊德（Floyd）算法考慮圖中從頂點vi到頂點vj的一條最短路徑，中間經(jīng)過或不經(jīng)過一些頂點如果最短路徑不經(jīng)過任何中間頂點，則這條最短路徑就是從vi到vj的邊反之，假設(shè)中間經(jīng)過頂點k，則vi到vj的最短路徑分為從vi到vk及從vk到vj的兩段，并且這兩段分別都是相應(yīng)頂點間的最短路徑，否則可以用更短的路徑來分別替代它們，從而組成從vi到vj之間更短的路徑顯然，從vi到vj的最短路徑不包含回路，否則可以去掉回路，找到一條更短的路徑設(shè)圖G中頂點序列為v1,v2,…,vn，帶權(quán)鄰接矩陣為A，A[i][j]中保存從vi到vj邊的權(quán)值，仍設(shè)權(quán)值為非負(fù)值現(xiàn)在限制最短路徑所經(jīng)過中間頂點的編號初始時，規(guī)定最短路徑中間不允許經(jīng)過任何頂點，則從vi到vj的路徑就是從vi到vj的邊，其路徑長度即為A[i][j]現(xiàn)在允許最短路徑中間經(jīng)過編號不大于v1的頂點，如果從vi到vj有最短路徑的話，則最短路徑只有以下兩種可能①從vi到vj的原有最短路徑，即從vi到vj的邊，A[i][j]為路徑長度②從vi到v1的路徑加上從v1到vj的路徑，A[i][v1]+A[v1][j]為路徑長度判斷上述兩值，取較小者作為新的A[i][j]值，此時A中保存的是允許經(jīng)過v1后頂點之間最短路徑的長度為了區(qū)別，標(biāo)記為A(1)，初始的帶權(quán)鄰接矩陣可以表示為A(0)Floyd算法定義A(k-1)[i][j]表示從頂點vi到頂點vj的中間頂點序號不大于vk-1的最短路徑之長度，A(0)[i][j]即是cost[i][j]從A(0)[i][j]出發(fā)，逐次計算從頂點vi到頂點vj的中間頂點序號不大于k（1≤k≤n）的最短路徑之長度，即在A(k-1)的基礎(chǔ)上計算A(k)，遞推地產(chǎn)生一個矩陣序列：A(0),A(1),…,A(k),…,A(n)，A(n)[i][j]表示的就是從頂點vi到vj的最短路徑的長度設(shè)目前已求出A(k-1)[i][j]，求A(k)[i][j]時分兩種情況：①如果從頂點vi到vj的最短路徑不經(jīng)過頂點vk，則由A(k)[i][j]的定義可知，從vi到vj的中間頂點序號不大于k的最短路徑長度就是A(k-1)[i][j]，即A(k)[i][j]=A(k-1)[i][j]。②如果從頂點vi到vj的最短路徑經(jīng)過頂點vk，則由vi到vk和由vk到vj兩條路徑組成從vi到vj的路徑。由于A(k-1)[i][k]和A(k-1)[k][j]分別代表從vi到vk和從vk到vj的中間頂點序號不大于vk-1的最短路徑的長度，則A(k)[i][j]=A(k-1)[i][k]+A(k-1)[k][j]。由此得到A(k)[i][j]的迭代計算公式：最后得到的A(n)[i][j]就是從頂點vi到vj的最短路徑的長度Floyd算法中計算cost的循環(huán)例6-19ThankYou!全國高等教育自學(xué)考試指定教材

計算機及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第七章內(nèi)部排序?qū)W習(xí)目標(biāo)理解排序的基本概念。掌握各種排序方法及其特點。掌握各種排序算法的實現(xiàn)過程，能夠?qū)ζ溥M行復(fù)雜度分析。能夠?qū)Ω鞣N排序方法進行比較，理解各排序方法的使用條件。本章主要內(nèi)容排序的基本概念12交換排序3插入排序選擇排序4歸并排序56排序算法的比較7分配排序第一節(jié)

排序的基本概念定義7.1給定一組記錄r1,r2,…,rn，其關(guān)鍵字分別為 k1,k2,…,kn

將這些記錄排成順序為rs1,rs2,…,rsn的一個序列S，滿足條件 ks1≤ks2≤…≤ksn

或是ks1≥ks2≥…≥ksn

此過程稱為排序若關(guān)鍵字值依從小到大的順序排列，則稱為升序若依從大到小的順序排列，則稱為降序內(nèi)部排序?qū)Σ煌愋偷年P(guān)鍵字而言，“大”、“小”的含義可能不一樣對于數(shù)值型的關(guān)鍵字，可按一般意義的“大”、“小”來理解對于字符型的關(guān)鍵字，往往按其對應(yīng)的ASCII碼來定義大小次序把能唯一標(biāo)識記錄的關(guān)鍵字稱為主關(guān)鍵字，其余的稱為次關(guān)鍵字主關(guān)鍵字值不允許有重復(fù)計算機中存放待排序數(shù)據(jù)的存儲介質(zhì)可以分為內(nèi)存和外存當(dāng)待排序的數(shù)據(jù)量不大，全部數(shù)據(jù)都可以放入內(nèi)存，排序操作也完全在內(nèi)存中進行時，相應(yīng)的排序稱為內(nèi)部排序或內(nèi)排序內(nèi)排序因為不涉及內(nèi)外存數(shù)據(jù)交換的問題所以一般來講，排序速度較快當(dāng)待排序的數(shù)據(jù)量大，全部數(shù)據(jù)不能同時放在內(nèi)存中，需要借助外存完成排序過程時，相應(yīng)的排序稱為外部排序或外排序外排序中，排序的具體操作在內(nèi)存完成，且僅能對部分?jǐn)?shù)據(jù)進行排序過程中需要多次分批在內(nèi)存、外存之間進行數(shù)據(jù)交換，從而完成全部數(shù)據(jù)的排序任務(wù)減少數(shù)據(jù)內(nèi)外存交換次數(shù)定義7.2具有相等關(guān)鍵字的兩個記錄R1和R2，在排序之前，R1位于R2之前，在排序之后，R1仍然位于R2之前，即排序并沒有改變具有相等關(guān)鍵字的兩個記錄的相對次序，這樣的排序方法稱為穩(wěn)定的（stable）如果排序方法不能保證具有相等關(guān)鍵字值的兩個記錄的相對次序在排序前后不被改變，則稱排序方法是不穩(wěn)定的當(dāng)兩個記錄中關(guān)鍵字的大小次序與記錄相對次序不一致時，稱兩個記錄是逆序的（inversion）實際上，排序就是不斷地調(diào)整逆序數(shù)據(jù)對的過程類型定義#definemaxSize30 //最大記錄數(shù)typedefintELEMType; //元素類型typedefstruct{

ELEMTypedata[maxSize]; //數(shù)組 intcurrentNum; //元素個數(shù)}myRcd;第二節(jié)插入排序——直接插入排序參與排序的n個數(shù)據(jù)均保存在數(shù)組A中A的前面（S部分）是已有序的子序列，后面是待排序的部分（U部分）初始時S部分中僅含有一個元素e，U部分中含有除e外的其他n-1個元素每進行一趟排序，S部分增加一個元素，相應(yīng)地U部分減少一個元素n-1趟排序后，S部分中包含全部的n個元素，而U部分變?yōu)榭?。排序結(jié)束直接插入排序i=1:4268351702579596365i=2:4268351702579596365i=3:3542681702579596365i=4:1354268702579596365i=5:1354268702579596365i=6:1253542687079596365i=7:1253542687079596365i=8:1253542596870796365i=9:1253542596368707965結(jié)果:1253542596365687079算法實現(xiàn)之一算法實現(xiàn)之二效率直接插入排序除原來的數(shù)據(jù)所占用的數(shù)組空間外，還需要一個臨時工作單元，所以它的空間復(fù)雜度為O(1)最優(yōu)時，總的交換次數(shù)為0，總的比較次數(shù)為n-1最差時，總的交換次數(shù)為n(n-1)/2，總的比較次數(shù)為n(n-1)/2平均時，為最差情況的一半左右希爾排序希爾排序（shell’smethod）又稱縮小增量排序（diminishingincrementsort），它是插入排序的一種改進利用的是數(shù)據(jù)基本有序時，或是數(shù)據(jù)個數(shù)較少時，直接插入排序的高效性需要解決兩個問題如何劃分段如何合并段劃分段及合并段劃分?jǐn)?shù)據(jù)段時是按照一定的間隔數(shù)進行的，將相距等間隔數(shù)的元素放在同一個數(shù)據(jù)段內(nèi)間隔數(shù)為3時所有下標(biāo)等于3i(i≥0)的元素都分在第一個數(shù)據(jù)段中所有下標(biāo)等于3i+1(i≥0)的元素分在第二個數(shù)據(jù)段中所有下標(biāo)等于3i+2(i≥0)的元素分在第三個數(shù)據(jù)段中一般地，間隔數(shù)為k時，全部數(shù)據(jù)會分成k個數(shù)據(jù)段合并的過程易如反掌希爾排序的過程首次劃分?jǐn)?shù)據(jù)段每一個數(shù)據(jù)段看成是一個組，在組內(nèi)進行直接插入排序依同樣的機制，將全部數(shù)據(jù)劃分為更長的數(shù)據(jù)段，數(shù)據(jù)段內(nèi)的數(shù)據(jù)個數(shù)增多，段數(shù)減少每組內(nèi)依次進行直接插入排序最后一趟排序的k值為1，也就是全部元素都在同一個組內(nèi)，對所有元素進行直接插入排序增量序列di的取法取d0=m，di+1=

di/2

取d0=m，di+1=

(di+1)/2

取d0=m，di+1=

(di-1)/3

取d0=m，di+1=

(di-1)/2

希爾排序42,68,35,1,70,25,79,59,63,65,26,80,17,36增量為5黑色字是原始數(shù)據(jù)，紅色字是組內(nèi)排序后的數(shù)據(jù)結(jié)果：25,68,17,1,65,26,79,35,36,70,42,80,59,63d=54225

2526

2642

第一組

6868

7979

8080

第二組

3517

5935

1759

第三組

11

6336

3663第四組

7065

6570

第五組25,68,17,1,65,26,79,35,36,70,42,80,59,63增量為3結(jié)果：1,35,17,25,42,26,59,63,36,70,65,80,79,68d=3251

125

7959

7070

5979

第一組

6835

6542

3563

4265

6368第二組

1717

2626

3636

8080

第三組最后一趟使用增量1，數(shù)據(jù)均在同一組內(nèi)。這是第三趟排序結(jié)果：1,17,25,26,35,36,42,59,63,65,68,70,79,80用希爾排序方法對一個數(shù)據(jù)序列進行排序時，若第1趟排序結(jié)果為 9,1,4,13,7,8,20,23,15則該趟排序采用的增量（間隔）可能是A．2 B．3 C．4 D．5答案：B排序中用到的增量序列的取法實際上很有講究如果增量序列取2的冪次，雖然計算增量時簡單，但在前一趟掃描中互相比較過的兩個關(guān)鍵字，在后一趟掃描中還會遇到，從而又比較一次，顯然這些比較操作是多余的一般地，增量之間最好不是倍數(shù)關(guān)系希爾排序算法修改直接插入排序算法之一修改直接插入排序算法之二第三節(jié)交換排序——起泡排序參與排序的n個數(shù)據(jù)均保存在數(shù)組A中，起泡排序算法的一般策略是：掃描整個數(shù)組，依次比較相鄰的兩個元素，如果它們是逆序的，就交換它們，然后再去查看后面的相鄰元素。持續(xù)地進行這個過程，直到所有元素都有序時為止每趟選最大值42,68,35,1,70,25,79,59,63,65i=1:4235168257059636579i=2:3514225685963657079i=3:1352542596365687079i=4:1253542596365687079i=5:1253542596365687079i=6:1253542596365687079i=7:1253542596365687079i=8:1253542596365687079i=9:1253542596365687079起泡排序算法選取并調(diào)整本趟最大值的起泡排序的算法每趟選最小值42,68,35,1,70,25,79,59,63,65i=1:1426835257059796365i=2:1254268355970637965i=3:1253542685963706579i=4:1253542596863657079i=5:1253542596368657079i=6:1253542596365687079i=7:1253542596365687079i=8:1253542596365687079i=9:1253542596365687079起泡排序算法選取并調(diào)整本趟最小值的起泡排序的算法若用起泡排序方法對序列10,14,26,29,41,52進行降序排序，則需進行比較操作的次數(shù)是（

）A．3 B．10 C．15 D．25答案：C。修改算法方法一：使用一個變量來記錄一趟掃描中是否有數(shù)據(jù)交換。當(dāng)發(fā)現(xiàn)沒有數(shù)據(jù)交換時，起泡排序可以立即結(jié)束方法二：設(shè)置一個變量flag，用它來標(biāo)識一趟排序過程中是否有記錄交換在每趟排序之前，flag的值為0，每次交換記錄后，flag的值修改為1每趟排序之后，判別flag的值，若為1，則繼續(xù)下一趟排序；若為0則表明該趟沒有交換任何記錄，意味著再沒有逆序的記錄存在，排序結(jié)束42,68,35,1,70,25,79,59,63,65 right=9

i=1:4235168257059636579 right=8i=2:3514225685963657079 right=7i=3:1352542596365687079 right=6i=4:1253542596365687079 right=1i=5:1253542596365687079

改進后的起泡排序算法效率起泡排序算法中，數(shù)據(jù)比較的次數(shù)是確定的第一趟要比較n-1次，第二趟要比較n-2次，第i趟要比較n-i次，總的比較次數(shù)為次。起泡排序最優(yōu)、最差及平均情況下的比較次數(shù)是相同的，均為O(n2)最差情況下，交換次數(shù)亦為O(n2)次最優(yōu)情況下，不發(fā)生交換平均情況下，記錄交換的次數(shù)約為最差情況下交換次數(shù)的一半改進后起泡排序，其最優(yōu)時間復(fù)雜度為O(n)快速排序快速排序算法是將一個含多數(shù)據(jù)的大數(shù)據(jù)段的排序問題，分解為兩個或一個含更少數(shù)據(jù)的小數(shù)據(jù)段的排序問題，小的數(shù)據(jù)段又繼續(xù)分解為更小的數(shù)據(jù)段，分解過程依此類推，這樣的分解過程稱為劃分每次劃分，都會得到比原來的數(shù)據(jù)段更小的數(shù)據(jù)段經(jīng)過多次劃分后，總會得到只含一個數(shù)據(jù)的數(shù)據(jù)段，而這樣的數(shù)據(jù)段自然有序再將這些有序的小數(shù)據(jù)段組合起來成為有序的大數(shù)據(jù)段，從而得到初始數(shù)據(jù)的排序結(jié)果快速排序中，需要解決兩個主要問題如何將一個大數(shù)據(jù)段劃分為小數(shù)據(jù)段有序的小數(shù)據(jù)段如何組合為大的數(shù)據(jù)段，并保證大數(shù)據(jù)段仍是有序的從初始數(shù)據(jù)中選擇一個元素，用它作為基準(zhǔn)元素，稱為樞軸（pivot）將初始數(shù)據(jù)中所有小于樞軸的數(shù)據(jù)分在一個組內(nèi)，設(shè)為組1將所有大于樞軸的數(shù)據(jù)分在另一個組內(nèi)，設(shè)為組2這就是快速排序劃分?jǐn)?shù)據(jù)段的機制組1中的所有數(shù)據(jù)全部都小于組2中的所有數(shù)據(jù)，這個性質(zhì)稱為整體有序初始：4268351702579596365選擇第一個元素做樞軸并將樞軸放到最后的位置pivot:426568351702579596342

↑

↑leftright尋找數(shù)據(jù)對6568351702579596342

↑

↑leftright進行交換

得到2568351706579596342

↑

↑leftright尋找數(shù)據(jù)對2568351706579596342

↑

↑leftright交換2513568706579596342

↑

↑leftright放回樞軸2513542706579596368

↑

↑rightleft得到的結(jié)果具有如下的性質(zhì)樞軸42在最終的位置上樞軸前面的元素均小于樞軸樞軸后面的元素均大于樞軸算法劃分算法快速排序算法另一種劃分方法4268351702579596365pivot=42()68351702579596365

↑

↑leftright找到小于42的元素()68351702579596365（從右向左）

↑

↑leftright填空并產(chǎn)生新的空256835170()79596365

↑

↑leftright找到大于42的元素256835170()79596365（從左向向）

↑

↑leftright填空并產(chǎn)生新的空25()351706879596365

↑

↑leftright找到小于42的元素25()351706879596365（從右向左）

↑

↑leftright填空并產(chǎn)生新的空25135()706879596365

↑

↑leftright找到大于42的元素25135()706879596365（從左向右）

↑

↑rightleft因為left與right已經(jīng)交錯，所以這次使用樞軸來填空使用樞軸填空2513542706879596365

↑

↑rightleft另一種劃分算法效率如果每次都能把數(shù)組劃分成元素個數(shù)大致相等的兩個子段，則快速排序能達到最優(yōu)情況?？偟臅r間代價為O(nlogn)與之相對的是每次劃分不平衡，一個子段極大（含n-1個元素），另一個子段極?。ê?個元素）。這樣的情況是快速排序的最差情況。總的時間代價為O(n2)平均情況介于最優(yōu)與最差之間，在理想狀態(tài)下，時間代價為O(nlogn)導(dǎo)致快速排序效率不高的主要原因是劃分時選擇的樞軸不好在最左位置元素、中間位置元素及最右位置元素中選擇中間值作為樞軸，劃分后，兩個部分都不會為空，每個部分中最少含有一個元素。樞軸的這種選擇方法稱為三元取中方法排序當(dāng)n值很小時，它的優(yōu)越性并不突出使用直接插入排序來替代快速排序快速排序需要一個棧作為輔助空間，故最壞情況下空間復(fù)雜度為O(n)第四節(jié)選擇排序選擇排序（selectionsort）算法重復(fù)地選擇特定值放到其最終位置，從而完成一組值的排序。即對于數(shù)組中的每個位置，算法選出應(yīng)該處在那個位置的值，并將它一次性地放置到位簡單選擇排序堆排序簡單選擇排序第一趟掃描時從全部n個元素中找到最小值放到數(shù)組的第一個位置第二趟掃描時從剩余的n-1個元素中找到最小值放到數(shù)組的第二個位置一般地，第k趟掃描時從n-k+1個元素中找到最小值放到數(shù)組的第k個位置。直到只剩余一個元素時，不需要再做任何處理，排序過程結(jié)束簡單選擇排序示例初始：42683526702579596365i=1:25683526704279596365i=2:25263568704279596365i=3:25263568704279596365i=4:25263542706879596365i=5:25263542596879706365i=6:25263542596379706865i=7:25263542596365706879i=8:25263542596365687079i=9:25263542596365687079堆排序

最小堆和最大堆例7-11設(shè)有數(shù)據(jù)序