數據結構（Java版）課件 呂云翔 第6、7章 圖、排序

第6章圖目錄2第6.1節(jié)第6.2節(jié)第6.3節(jié)第6.4節(jié)第6.5節(jié)第6.6節(jié)圖概述圖的存儲結構圖的遍歷最小生成樹最短路徑拓撲排序和關鍵路徑6.1圖概述6.1.1圖的基本概念6.1.2圖的抽象數據類型描述圖概述在離散數學中，圖論研究圖的純數學性質；在數據結構中，圖結構研究計算機中如何存儲圖以及如何實現圖的操作和應用。圖是刻畫離散結構的一種有力工具。在運籌規(guī)劃、網絡研究和計算機程序流程分析中都存在圖的應用問題。我們也經常用圖來表達文字難以描述的信息，如城市交通圖、鐵路網等。4網絡研究運籌規(guī)劃程序流程分析描述信息圖的基本概念圖是一種數據元素間具有“多對多”關系的非線性數據結構，由頂點集V和邊集E組成，記作G=(V,E)。其中V是有窮非空集合，v∈V稱為頂點；E是有窮集合，e∈E稱為邊。

5

圖的基本概念6線性結構樹“一對一”的線性關系“一對多”的層次關系每一個數據元素都可以和其他的任意數據元素相關。每個元素可以有多個前驅元素和多個后繼元素，任意兩個元素可以相鄰。與線性結構和樹相比圖更為復雜圖圖的基本概念7e=(u,v)表示頂點u和頂點v間的一條無向邊，也可以簡稱為邊。(u,v)間沒有方向，即(u,v)和(v,u)是相同的。e=<u,v>表示頂點u到頂點v間的一條有向邊，也叫弧。u叫始點或弧尾，v叫終點或弧頭。<u,v>是有方向的，因此<u,v>和<v,u>是不同的。零圖是指E為空集的圖，也就是圖中只有頂點存在，沒有邊。030102無向邊有向邊零圖

圖的基本概念8無向圖指全部由無向邊構成的圖。有向圖指全部由有向邊構成的圖。完全圖是指邊數達到最大值的圖，即在頂點數為n的無向圖中邊數為n(n-1)2，在頂點數為n的有向圖中邊數為n(n-1)。040506無向圖有向圖圖的基本概念907.稠密圖稠密圖是指邊數較少的圖，如e<nlog2n，反之則為稀疏圖。08.子圖設有兩個圖G=(V,E)和G′=(V′,E′)，如果有V′?V和E′?E，則稱G′是G的子圖，記作G′?G。09.生成子圖如果G′=(V′,E′)是G=(V,E)的子圖，并且V′=V，則稱G′是G的生成子圖。10.鄰接點在一個無向圖中若存在邊(u,v)，則稱頂點u和v互為鄰接點。邊(u,v)是頂點u和v關聯的邊，頂點u和v是邊(u,v)關聯的頂點。圖的基本概念10R111213頂點的度頂點的度是指與該頂點關聯的邊的數目。頂點u的度記作D(u)。在有向圖中頂點的度有入度和出度兩種。對于頂點u，入度指的是以u為終點的弧的數目，記為ID(u)；出度指的是以u為起點的弧的數目，記為OD(u)。全部頂點的度之和為邊數的兩倍。路徑路徑是指從頂點u到頂點v所經過的頂點序列。路徑長度是指路徑上邊的數目。沒有頂點重復出現的路徑叫初等路徑?；芈返谝粋€和最后一個頂點相同的路徑稱為回路或環(huán)，除了第一個和最后一個頂點以外，其他頂點都不重復出現的回路叫初等回路。圖的基本概念11連通分量是指無向圖中的極大連通子圖。15連通分量強連通分量是指有向圖中的極大連通子圖。17強連通分量在有向圖中若任意兩個頂點均是連通的，則稱該圖為強連通圖。16強連通圖在無向圖中若頂點u和頂點v間有路徑，則稱u和v是連通的。連通圖是指任意兩個頂點均是連通的圖。14連通圖

強連通圖強連通分量連通分量連通圖圖的基本概念1218.生成樹和生成森林生成樹是指包含圖中的全部頂點，但只有構成樹的n-1條邊的生成子圖。對于非連通圖，每個連通分量可形成一棵生成樹，所有生成樹組成的集合叫該非連通圖的生成森林。19.網網指的是邊上帶有權值的圖。通常權為非負實數，可以表示從一個頂點到另一個頂點的距離、時間和代價等。圖的抽象數據類型描述13圖的抽象數據類型用Java抽象類描述如下：6.2圖的存儲結構6.2.1鄰接矩陣6.2.2鄰接表圖的存儲結構圖的存儲結構需要存儲頂點的值以及與頂點相關聯的頂點和邊的信息。頂點間沒有次序關系，各條邊之間也沒有次序關系，但是表示和存儲一個圖必須約定好頂點次序。邊集合表達每對頂點間的鄰接關系，是二維線性關系。圖的存儲結構可用矩陣來形容。15

鄰接矩陣矩陣的存儲結構常見有鄰接矩陣、鄰接表、十字鏈表3種。

鄰接表

十字鏈表圖的存儲結構邊采用順序存儲結構，用二維數組存儲，稱為圖的鄰接矩陣。邊采用鏈式存儲結構，存儲行的后繼，即矩陣行的單鏈表，稱為圖的鄰接表。邊采用鏈式存儲結構，存儲行和列的后繼，即矩陣十字鏈表，稱為圖的鄰接多重表。16鄰接矩陣——存儲結構17

分析可得，在無向圖的鄰接矩陣中第i行或者第i列的非零元素的個數為第i個頂點的度；在有向圖的鄰接矩陣中第i行的非∞元素的個數為第i個頂點的出度，第i列非∞元素的個數為第i個頂點的入度。無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣不一定是對稱的。

鄰接矩陣圖的鄰接矩陣可以用二維數組進行表示，鄰接矩陣類的Java語言描述如右圖：18鄰接矩陣2.圖的鄰接矩陣類的基本操作的實現1)圖的創(chuàng)建【算法6.1】創(chuàng)建無向圖【算法6.2】創(chuàng)建有向圖19鄰接矩陣2.圖的鄰接矩陣類的基本操作的實現1)圖的創(chuàng)建【算法6.3】創(chuàng)建無向網20鄰接矩陣2.圖的鄰接矩陣類的基本操作的實現1)圖的創(chuàng)建【算法6.4】創(chuàng)建有向網21鄰接矩陣222.圖的鄰接矩陣類的基本操作的實現2)頂點的定位頂點定位算法locateVex(x)是根據x的值取得其在頂點集中的位置，若不存在則返回-1?！舅惴?.5】頂點的定位。鄰接矩陣232.圖的鄰接矩陣類的基本操作的實現3)查找第一個鄰接點查找第一個鄰接點算法firstAdj(i)是指給定一個頂點在頂點集中的位置i，返回其第一個鄰接點，若不存在則返回-1。【算法6.6】查找第一個鄰接點。鄰接矩陣242.圖的鄰接矩陣類的基本操作的實現4)查找下一個鄰接點查找下一個鄰接點算法nextAdj(i,j)是指給定兩個頂點在頂點集中的位置i、j，第j個頂點是第i個頂點的鄰接點，返回第j個頂點之后的下一個鄰接點，若不存在則返回-1?！舅惴?.7】查找下一個鄰接點。鄰接矩陣——性能分析2501圖的鄰接矩陣表示存儲了任意兩個頂點間的鄰接關系或邊的權值，能夠實現對圖的各種操作，其中判斷兩個頂點間是否有邊相連、獲得和設置邊的權值等操作的時間復雜度為O(1)。02但是，與順序表存儲線性表的性能相似，由于采用數組存儲，每插入或者刪除一個元素需要移動大量元素，使得插入和刪除操作的效率很低，而且數組容量有限，當擴充容量時需要復制全部元素，效率更低。在圖的鄰接矩陣中每個矩陣元素表示兩個頂點間的鄰接關系，無邊或有邊。即使兩個頂點之間沒有鄰接關系，也占用一個存儲單元存儲0或者-1。對于一個有n個頂點的完全圖，其鄰接矩陣有n(n-1)/2個元素，此時鄰接矩陣的存儲效率較高；當圖中的邊數較少時，鄰接矩陣變得稀疏，存儲效率較低，此時可用圖的鄰接表進行存儲。何時選擇鄰接矩陣？鄰接矩陣26【例6.1】n個頂點的無向圖采用鄰接矩陣存儲，回答下列問題：（1）圖中有多少條邊？（2）任意兩個頂點i和j之間是否有邊相連？（3）任意一個頂點的度是多少？解：（1）鄰接矩陣中非零元素個數的總和除以2。（2）當鄰接矩陣A中A[i][j]=1(或A[j][i]=1)時表示兩頂點之間有邊相連。（3）計算鄰接矩陣上該頂點對應的行上非零元素的個數。鄰接表271.圖的鄰接表存儲結構鄰接表采用鏈式存儲結構存儲圖，是由一個順序存儲的頂點表和多個鏈式存儲的邊表組成的。邊表的個數和圖的頂點數相同。頂點表由頂點結點組成，每個頂點結點又由數據域和指針域組成，其中數據域data存放頂點值，指針域firstArc指向邊表中的第一個邊結點。邊表由邊結點組成，每個邊結點又由adjVex、nextArc、value幾個域組成，其中value存放邊的信息，例如權值；adjVex存放與結點鄰接的頂點在圖中的位置；nextArc指向下一個邊結點。鄰接表頂點結點類的描述鄰接表的頂點結點類的Java描述如下：28鄰接表邊結點類的描述鄰接表的邊結點類的Java描述如下：29鄰接表30鄰接表類的描述圖的鄰接表類的描述如下：鄰接表31鄰接表2.圖的鄰接表的基本操作的實現1)圖的創(chuàng)建【算法6.8】創(chuàng)建無向圖【算法6.9】創(chuàng)建有向圖32鄰接表2.圖的鄰接表的基本操作的實現1)圖的創(chuàng)建【算法6.10】創(chuàng)建無向網33鄰接表2.圖的鄰接表的基本操作的實現1)圖的創(chuàng)建【算法6.11】創(chuàng)建有向網34鄰接表352.圖的鄰接表的基本操作的實現2)在圖中插入邊結點插入邊結點的算法addArc(i,j,value)是指在邊鏈表中加入一個由第i個頂點指向第j個頂點的權值為value的邊結點，采用頭插法進行插入。【算法6.12】插入邊結點。鄰接表363)查找第一個鄰接點【算法6.13】查找第一個鄰接點。4)查找下一個鄰接點【算法6.14】查找下一個鄰接點。鄰接表37用鄰接矩陣存儲圖可以很好地確定兩個頂點間是否有邊，但是查找頂點的鄰接點，需要訪問對應一行或一列的所有數據元素，并且無論兩個頂點間是否有邊都要保留存儲空間。用鄰接表存儲圖可以方便地找到頂點的鄰接點，對于稀疏圖來說節(jié)省存儲空間，但若要確定兩個頂點間是否有邊相連則需要遍歷單鏈表，比鄰接矩陣復雜。6.3圖的遍歷6.3圖的遍歷-問題描述圖的遍歷是指從圖的任意一個頂點出發(fā)對圖的每個頂點訪問且僅訪問一次的過程，因為圖中可能存在回路，為了避免對一個頂點的重復訪問可以增設一個輔助數組visited[0...n-1]，全部初始化為0，一旦第i個頂點被訪問，置visited[i]=1。圖的遍歷和樹的遍歷相比更加復雜，需要考慮以下3個問題。(1)指定遍歷的第一個頂點。(2)由于一個頂點和多個頂點相鄰，需要在多個鄰接頂點間確定訪問次序。(3)由于圖中存在回路，必須對訪問過的頂點做標記，防止出現重復訪問同一頂點的情況。396.3圖的遍歷-遍歷方法遍歷方法廣度優(yōu)先搜索深度優(yōu)先搜索406.3圖的遍歷-廣度優(yōu)先搜索0102030405建立訪問標識數組visited[n]并初始化為0,n為圖頂點的個數隊列初始化訪問所有臨界點重復步驟(3)，直到隊列為空。改變i值，0≤i<n，跳到步驟(2)繼續(xù)進行，直到i=n-1訪問所有頂點將隊首元素頂點vi從隊列中取出，依次訪問它的未被訪問的鄰接點vj、vk、…，并將其入隊。取出頂點，添加鄰接點添加未訪問頂點將未訪問頂點vi入隊416.3圖的遍歷-廣度優(yōu)先搜索算法展示426.3圖的遍歷-深度優(yōu)先搜索01020304以未訪問頂點vi為起始點訪問其未訪問鄰接點vj頂點入隊，訪問其臨界點從vj出發(fā)遞歸進行步驟(2)，直到所有鄰接點均被訪問訪問所有臨界點改變i值，0≤i<n，跳到步驟(2)繼續(xù)進行，直到i=n-1訪問所有頂點建立訪問標識數組visited[n]并初始化為0,n為圖頂點的個數隊列初始化436.3圖的遍歷-深度優(yōu)先搜索算法展示446.3圖的遍歷-廣度度優(yōu)先搜索算法應用【例6.2】編程利用廣度優(yōu)先搜索算法確定無向圖的連通分量。456.3圖的遍歷-廣度優(yōu)先搜索算法應用【例6.2】編程利用廣度優(yōu)先搜索算法確定無向圖的連通分量。第1個連通塊：123第2個連通塊：45第3個連通塊：6466.3圖的遍歷-遍歷算法應用【例6.3】已知一個連通圖如下所示，試給出圖的鄰接矩陣和鄰接表存儲示意圖，若從頂點v1出發(fā)對該圖進行遍歷，分別給出一個按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列。476.3圖的遍歷-遍歷算法應用【例6.3】解：深度優(yōu)先遍歷序列：v1v2v3v4v5v6廣度優(yōu)先遍歷序列：v1v2v4v6v3v5鄰接矩陣和鄰接表表示如左圖所示。

486.3圖的遍歷-遍歷算法應用【例6.4】已知無向圖G的鄰接表如圖所示，分別寫出從頂點1出發(fā)的深度遍歷和廣度遍歷序列，并畫出相應的生成樹。49【例6.4】解：由章節(jié)給出的算法可知深度優(yōu)先遍歷序列為1，2，3，4，5，6。對應的生成樹如圖所示。廣度優(yōu)先遍歷序列為1，2，4，3，5，6。對應的生成樹如圖所示。深度優(yōu)先遍歷序列對應的生成樹廣度優(yōu)先遍歷序列對應的生成樹6.3圖的遍歷-遍歷算法應用506.3圖的遍歷-遍歷算法應用【例6.5】假設有如圖所示的有向網圖，利用Dijkstra算法求從頂點v1到其他各頂點的最短路徑。51【例6.5】解：從源點v1到其他各頂點的最短路徑如表所示。源點終點最短路徑最短路徑長度v1v1v1v1v1v3v5v2v6v4v1v3v1v5v1v3v2v1v3v2v6v1v3v2v415152540456.3圖的遍歷-遍歷算法應用526.3圖的遍歷-遍歷算法應用【例6.6】編寫程序實現如圖所示的連通無向網的最小生成樹。53[['A','D'],['D','F'],['F','C'],['D','B'],['B','E']]6.3圖的遍歷-遍歷算法應用輸出：546.4最小生成樹6.4.1最小生成樹的基本概念6.4.2Kruskal算法6.4.3Prim算法6.4.1最小生成樹的概念01連通圖的生成樹是圖的極小連通子圖，它包含圖中的全部頂點，但只有構成一棵樹的邊。一個有n個頂點的連通圖的生成樹只有n-1條邊。若有n個頂點而少于n-1條邊，則為非連通圖，若多于n-1條邊，則一定形成回路。根據生成算法不同又分為廣度優(yōu)先生成樹和深度優(yōu)先生成樹。連通圖的生成樹02對于非連通圖，每個連通分量中的頂點集和遍歷經過的邊一起構成若干棵生成樹，共同組成了該非連通圖的生成森林。生成森林03在一個網的所有生成樹中權值總和最小的生成樹稱為最小代價生成樹，簡稱為最小生成樹最小生成樹566.4.1最小生成樹的概念具有n個頂點和n-1條邊01只能使用圖中的邊構造最小生成樹02不能使用產生回路的邊03最小生成樹3大原則576.4.2Kruskal算法算法原理：Kruskal算法是依次找出權值最小的邊建立最小生成樹，每次新增的邊不能使生成樹產生回路，直到找到n-1條邊。21(2)在圖G的邊集中選取權值最小的邊，若該邊未使生成樹T形成回路，則加入到TE中，否則丟棄，直到生成樹中包含了n-1條邊(1)將T的初始狀態(tài)置為僅含有源點的集合設圖是由n個頂點組成的連通無向網，是圖G的最小生成樹,其中V是T的頂點集，TE是T的邊集586.4.3

Prim算法12

頂點到頂點集合的距離：頂點到頂點集合中所有頂點的距離的最小值，記為|u,V|=min|u,v|3

兩個頂點集合之間的距離：頂點集合U的頂點到頂點集合V的距離的最小值，記為|U,V|=min|u,V|兩個頂點之間的距離：將頂點u鄰接到頂點v的關聯邊的權值，記為|u,v|。若兩個頂點之間不相連，則這兩個頂點之間的距離為無窮大596.4.3Prim算法-類描述606.4.3Prim算法-類描述616.5最短路徑6.5.1單源最短路徑6.5.2求任意兩個頂點間的最短路徑6.5.1單源最短路徑-Dijkstra算法B在最短路徑中長度最短的最短路徑一定有且僅有一條弧，弧的權值是從源點出發(fā)的所有弧的權中的最小值C長度次短的最短路徑有兩種情況：其一。只包含一條從源點出發(fā)的弧，弧上的權值大于已求得最短路徑的弧的權值，小于其他從源點出發(fā)的弧的權值；其二，一條只經過已求得最短路徑的頂點的路徑A基本思想是“按最短路徑長度遞增的次序”產生最短路徑算法思想與原理636.5.1單源最短路徑-Dijkstra算法1.保存當前最短路徑保存當前已經得到的從源點到各個其余頂點的最短路徑算法細節(jié)引入一個輔助向量D，它的每個分量D[i]存放當前所找到的從源點到終點的最短路徑長度。2.更新最短路徑若源點到該頂點有弧，存在一條路徑，長度為弧上的權值，每求得一條到達某個頂點的最短路徑就需要檢查是否存在經過這個頂點的其他路徑，若存在，判斷其長度是否比當前求得的路徑長度短，若是，則修改當前路徑64Dijkstra算法構造最短路徑的類Java語言描述如下：6.5.1單源最短路徑-Dijkstra算法65

6.5.1單源最短路徑-Dijkstra算法666.5.2兩點最短路徑-Floyd算法用n階方陣序列來描述Floyd算法，其中D-1[i][j]表示從頂點出發(fā)不經過其他頂點直接到達頂點的路徑長度，即D-1[i][j]=G.arcs[i][j]，D(k)[i][j]表示從頂點vi到頂點vj的中間可能經過v0，…,vk，而不可能經過vk+1,…,vn-1等頂點的最短路徑長度，所以D(n-1)[i][j]是從頂點vi到頂點vj的最短路徑長度，和路徑長度序列相對應的是路徑的n階方陣序列p(-1),p(0),p(1),…,p(n-1)算法描述圖例分析其中，k表示在路徑中新增的頂點，i為路徑的源點，j為路徑的終點。676.5.2兩點最短路徑-Floyd算法Floyd算法構造最短路徑的類用Java語言描述如右：686.6拓撲排序和關鍵路徑6.6.1拓撲排序6.6.2關鍵路徑有向圖表示活動之間相互制約的關系，稱為頂點活動網(AOV）弧表示活動之間的優(yōu)先關系活動指在生產實踐中，幾乎所有的工程都可以分解為若干個具有相對獨立性的子工程頂點表示活動6.6.1

AOV概念引入和圖表示在AOV網中存在一條從頂點u到頂點v的弧，則活動u一定優(yōu)先于活動v發(fā)生，否則活動u、v的發(fā)生順序可以是任意的，且不能存在閉環(huán)。706.6.1拓撲排序-概念和算法原理對AOV網進行拓撲排序即構造一個包含圖中所有頂點的拓撲有序序列，若在AOV網中存在一條從頂點u到頂點v的弧，則在拓撲有序序列中頂點u必須先于頂點v，否則頂點u、v的順序可以是任意的。概念(1)在AOV網中選擇一個沒有前驅的頂點并輸出。(2)從AOV網中刪除該頂點以及從它出發(fā)的弧。(3)重復步驟(1)和(2)直到AOV網為空，或者剩余子圖中不存在沒有前驅的頂點，此時說明AOV網中存在環(huán)。算法步驟整個拓撲排序可以分成求各個頂點的入度和一個拓撲序列的過程。應用716.6.1拓撲排序-具體算法【算法6.16】求各頂點的入度。726.6.1拓撲排序-具體算法【算法6.17】計算AOV的一個拓撲序列，若存在返回拓撲序列，否則返回None。736.6.2關鍵路徑SWOTAOE網（邊活動網絡）以弧表示活動，弧上的權值表示進行該項活動需要的時間，頂點表示事件關鍵路徑工程開始事件的頂點稱為源點，工程結束事件的頂點稱為匯點，從源點到匯點的最短路徑稱為關鍵路徑關鍵活動當e(i)=l(i),稱為關鍵活動最早開始時間和最晚開始時間從V0到Vi的最長路徑叫做事件的最早發(fā)生時間，記為e(i)。最晚開始時間指的是在不推遲整個工程的前提下，活動最晚必須開始的時間，記為l(i)。746.6.2關鍵路徑-算法原理從源點出發(fā)，令ve(0)=0，其余各頂點的ve(j)=max(ve(i)+|i,l|)，其中，T是所有以第j個頂點為頭的弧的集合。若得到的拓撲排序序列中頂點的個數小于網中的頂點個數n，則說明網中有環(huán)，不能求出關鍵路徑，算法結束1從Vn-1匯點出發(fā)，令vl(n-1)=ve(n-1)，按逆拓撲排序求其余各頂點許的最晚開始時間為vl(i)=min(vl(j)-|i,j|)，其中，S是所有以第j個頂為尾的弧的集合。2每一項活動ai的最早開始時間為e(i)=ve(j)，最晚開始時間為l(i)=vl(j)-|i,j|。若ai滿足e(i)=l(i),則它是關鍵活動。3756.6.2關鍵路徑-具體算法【算法6.18】若拓撲序列存在，返回各頂點的最早發(fā)生時間ve與逆拓撲序列棧t，否則返回None,None。766.6.2關鍵路徑-具體算法【算法6.19】求各頂點的最晚發(fā)生時間并輸出關鍵活動。776.7小結SOTW圖的常見存儲結構有鄰接矩陣、鄰接表、十字鏈表3種。鄰接矩陣是圖，用二維數組存儲；鄰接表和十字鏈表是圖的鏈式存儲結構由廣度優(yōu)先遍歷和深度優(yōu)先遍歷得到的生成樹分別稱為廣度優(yōu)先生成樹和深度優(yōu)先生成樹。在一個網的所有生成樹中權值總和最小的生成樹稱為最小代價生成樹，簡稱為最小生成樹，最小生成樹不一定唯一。建立最小生成樹的方法有Kruskal算法和Prim算法圖是一種數據元素間具有“多對多”關系的非線性數據結構，由頂點集V和邊集E組成，記作G=(V,E)圖的遍歷是指從圖的任意一個頂點出發(fā)對圖的每個頂點訪問且僅訪問一次的過程。圖的遍歷方式分為兩種，即廣度優(yōu)先搜索遍歷和深度優(yōu)先搜索遍歷總結79SOTW用戶可以使用有向圖表示活動之間相互制約的關系，頂點表示活動，弧表示活動之間的優(yōu)先關系，這種有向圖稱為頂點活動網(AOV)。若在AOV網中存在一條從頂點u到頂點v的弧，則活動u一定優(yōu)先于活動v發(fā)生。AOE網絡常用來表示工程的進行，一個工程的AOE網應該是只有一個源點和一個匯點的有向無環(huán)圖。由于AOE網中的某些活動可以并行進行，故完成整個工程的最短時間即從源點到匯點的最長路徑的長度，這條路徑稱為關鍵路徑，構成關鍵路徑的弧即為關鍵活動。最短路徑的求解問題主要分為兩類，即求某個頂點到其余頂點的最短路徑、求每一對頂點間的最短路徑，可以分別使用Dijkstra算法和Floyd算法解決這兩類問題若以弧表示活動，弧上的權值表示進行該項活動需要的時間，頂點表示事件，這種有向網稱為邊活動網絡，簡稱為AOE網?？偨Y80第7章排序目錄82排序概述插入排序交換排序選擇排序歸并排序第一節(jié)第二節(jié)第三節(jié)第四節(jié)第五節(jié)第一節(jié)排序概述1.1排序的基本概念84排序是指將一組數據按照關鍵字值的大小(遞增或者遞減)次序進行排列。排序是線性表、二叉樹等數據結構的一種基本操作。作為排序依據的數據項叫關鍵字。關鍵字關鍵字能唯一標識一條記錄，叫主關鍵字關鍵字標識多條記錄，叫次關鍵字例如學號、班級、成績等數據項均可以作為學生信息數據元素的關鍵字，按主關鍵字進行排序，結果唯一；按非主關鍵字進行排序，結果不唯一，班級學生的次序不能確定，哪個在前后都有可能。1.1排序的基本概念85按照排序過程中所涉及的存儲器的不同可將排序分為內部排序和外部排序兩種類型。

內部排序是指排序序列完全存放在內存中的排序過程；

外部排序是指需要將數據元素存儲在外部存儲器上的排序過程。排序又可分為穩(wěn)定排序和不穩(wěn)定排序。

穩(wěn)定排序是指在用某種排序算法依據關鍵字進行排序后具有相同關鍵字的數據元素的位置關系與排序前相同的排序過程，反之則為不穩(wěn)定排序。1.2排序算法的性能評價86排序算法的性能評價時間復雜度：算法執(zhí)行過程中的比較和移動次數來計算空間復雜度：用外部存儲空間的大小來計算

排序往往處于軟件的核心部分，經常被使用，所以其性能的優(yōu)劣對軟件質量的好壞起著重要的作用1.3待排序的記錄和順序表的類描述87因為待排序的數據元素通常存儲在順序表中，所以本章中的排序算法都是以順序表為基礎進行設計的。待排序的記錄的類Python語言描述如下：1.3待排序的記錄和順序表的類描述88

待排序的順序表的類Python語言描述如下：第二節(jié)插入排序2.1直接插入排序90直接插入算法的實現直接插入排序是指將一條待排序的記錄按照其關鍵字值的大小插入到已排序的記錄序列中的正確位置，依次重復，直到全部記錄都插入完成。其主要步驟如下：

(1)將list[i]存放在臨時變量p中。(2)將p與list[i-1]、list[i-2]、…、list[0]依次比較，若有p<list[j].key(j=i-1、i-2、…、0)，則將list[j]后移一個位置，直到p≥list[j].key為止。當p≥list[j].key時將p插入到list[j+1]的位置。(3)令i=1、2、3、…、n-1，重復步驟(1)、(2)、(3)。2.1直接插入排序91假設一組待排序的記錄的關鍵字序列為{2,45,36,72,34}，直接插入排序的過程如圖7.1所示。2.1直接插入排序92【算法7.1】直接插入排序。2.1直接插入排序性能分析931.時間復雜度※有序表中逐個插入的操作進行了n-1趟，每趟的插入操作的時間主要耗費在關鍵字的比較和數據元素的移動上。

2.1直接插入排序性能分析942.空間復雜度由于其僅使用了一個輔助存儲單元p，所以空間復雜度為O(1)。2.算法穩(wěn)定性在使用直接插入排序后具有相同關鍵字的數據元素的位置關系與排序前相同，因此直接插入排序是一種穩(wěn)定的排序算法。2.2希爾排序95希爾排序算法的實現希爾排序是D.L.Shell在1959年提出的，又稱縮小增量排序，是對直接插入排序的改進算法，其基本思想是分組的直接插入排序。由直接插入排序算法分析可知，數據序列越接近有序時間效率越高，當n較小時時間效率也較高。希爾排序正是針對這兩點對直接插入排序算法進行改進。希爾排序算法的描述如下:(1)將一個數據元素序列分組，每組由若干個相隔一段距離的元素組成，在一個組內采用直接插入算法進行排序。(2)增量的初值通常為數據元素序列的一半，以后每趟增量減半，最后值為1。隨著增量逐漸減小，組數也減少，組內元素的個數增加，數據元素序列接近有序。2.2希爾排序96主要步驟(1)設定一個增量序列{d0,d1，…,1}。(2)根據當前增量di將間隔為di的數據元素組成一個子表，共di個子表。(3)對各子表中的數據元素進行直接插入排序。(4)重復步驟(2)、(3)，直到進行完di=1，此時序列已按關鍵字值排序。2.2希爾排序97假設一組待排序的記錄的關鍵字序列為{2,18,23,56,78,70,45,36,72,34}，增量分別取5、3、1，則希爾排序的過程如圖7.2所示。2.2希爾排序算法性能分析981.時間復雜度希爾排序的關鍵字比較次數和數據元素的移動次數取決于增量的選擇，目前還沒有更好的選取增量序列的方法。Hibbard提出了一種增量序列{2k-1,2k-1-1,…,7,3,1}，可以使時間復雜度達到O(n3/2)。需要注意的是，在增量序列中應沒有除1以外的公因子，并且最后一個增量值必須為1。2.2希爾排序992.空間復雜度希爾排序仍只使用了一個額外的存儲空間p，其空間復雜度為O(1)。3.算法穩(wěn)定性希爾排序算法在比較過程中會錯過關鍵字相等的數據元素的比較，算法不能控制穩(wěn)定，因此希爾排序是一種不穩(wěn)定的排序算法。第三節(jié)交換排序3.1冒泡排序101冒泡排序算法的實現冒泡排序是兩兩比較待排序記錄的關鍵字，如果次序相反則交換兩個記錄的位置，直到序列中的所有記錄有序。若按升序排序，每趟將數據元素序列中的最大元素交換到最后的位置，就像氣泡從水里冒出一樣。其主要步驟如下：(1)設交換次數k=1。(2)在常數為n的序列{a[0],a[1],…,a[n-1]}中從頭到尾比較a[i]和a[i+1]，若a[i].key>a[i+1].key，則交換兩個元素的位置，其中，0≤i<n-i。(3)k增加1。(4)重復步驟(2)、(3)，直到k=n-1或者步驟(2)中未發(fā)生交換為止。3.1冒泡排序102假設一組待排序的記錄的關鍵字序列為{2,23,18,56,78,70,45,36,72,34}，冒泡排序的過程如圖7.3所示。3.2快速排序103快速排序算法的實現快速排序是一種分區(qū)交換排序算法，是冒泡排序的改進，其采用了分治策略，將問題劃分成若干個規(guī)模更小但和原問題相似的子問題，然后用遞歸方法解決這些子問題，最終將它們組合成原問題的解?？焖倥判驅⒁判虻男蛄蟹殖瑟毩⒌膬蓚€部分，其中一部分的關鍵字值都比另一部分的關鍵字值大，然后分別對這兩個部分進行快速排序，排序過程遞歸進行，整個序列最終達到有序。獨立的兩個部分的劃分方法為在序列中任意選取一條記錄，然后將所有關鍵字值比它大的記錄放到它的后面，將所有關鍵字值比它小的記錄放到它的前面。這條記錄叫支點。3.1冒泡排序104主要步驟(1)設置兩個變量low、high，分別表示待排序序列的起始下標和終止下標。(2)設置變量p=list[low]。(3)從下標為high的位置從后向前依次搜索，當找到第1個比p的關鍵字值小的記錄時將該數據移動到下標為low的位置上，low加1。(4)從下標為low的位置從前向后依次搜索，當找到第1個比p的關鍵字值大的記錄時將該數據移動到下標為high的位置上，high減1。(5)重復步驟(3)和(4)，直到high=low為止。(6)list[low]=p。3.1冒泡排序105假設一組待排序的記錄的關鍵字序列為{45,53,18,36,72,30,48,93,15,36}，以排序碼45進行第一次劃分的過程如圖7.4所示。3.1冒泡排序1063.1冒泡排序算法性能分析1071.時間復雜度

3.1