五、圖
　　
　　圖的概念

　　圖是一種較線性表和樹形結構更為復雜的數據結構。在線性表中每個數據元素只有一個（直接）前驅和后繼，即各數據元素之間僅有線性關系。在樹形結構中，數據元素之間有明顯的層次關系，每一層中的數據元素只和上一層中的一個元素（即雙親結點）相關。而在圖中，任意兩個數據元素之間均有可能相關。

　　圖（graph）是圖型結構的簡稱。它是一種復雜的非線性數據結構。圖在各個領域都有著廣泛的應用。圖的二元組定義為:
　　
　　G=（V，E）

　　其中，V是非空的頂點集合，即

　　V=｛v i |1≤i≤n，n≥1，v i ∈elemtype，n為頂點數｝

　　E是V上二元關系的集合，一般只討論僅含一個二元關系的情況，且直接用E表示這個關系。這樣，E就是V上頂點的序偶或無序對（每個無序對（x，y）是兩個對稱序偶<x，y>和<y，x>的簡寫形式）的集合。對于V上的每個頂點，在E中都允許有任意多個前驅和任意多個后繼，即對每個頂點的前驅和后繼個數均不加限制。回顧一下線性表和樹的二元組定義，都是在其二元關系上規定了限制條件，線性表的限制條件是只允許每個結點有一個前驅和一個后繼，樹的限制條件是只允許每個結點有一個前驅。因此，圖比線性表和樹更具有廣泛性，它包含線性表和樹在內，線性表和樹可以認為是圖的簡單情況。
　　
　　對于一個圖G，若E是序偶的集合，則每個序偶對應圖形中的一條有向邊，若E是無序對的集合，則每個無序對對應圖形中的一條無向邊，所以可把E看作為邊的集合。這樣，圖的二元組定義可敘述為:圖的非空頂點集（vertexset）和邊集（edgeset）所組成。針對圖G，頂點集和邊集可分別記為V（G）和E（G）。邊集E（G）允許是空集，若是空集，圖G中的頂點均為孤立頂點。對于一個圖G，若邊集E（G）為有向邊的集合，則稱此圖為有向圖（digraph），若邊集E（G）為無向邊的集合，則稱此圖為無向圖（undigraph）。
　　
　　六、排序

　　1.直接插入排序

　　直接插入排序的基本思想是把表中元素依次插入一個已排好序的表中，就像人們打撲克摸牌時把牌插入手中的若干張牌里一樣。表中n個元素依次插入的比較次數為1+2+3+…+（n-1）=n（n-1）/2。在插入時，元素的移動次數最多為1+2+3+…+（n-1）=n（n-1）/2。如果表中元素已排好序，則只需比較n-1次，而移動次數為0。
　　
　　2.直接選擇排序
　　
　　直接選擇排序的基本思想是在表的n個元素中，經過n-1次比較得到其最大值（或最小值，下同），這就排好了第一個元素;再經過n-2次比較得到余下元素中的最大值，這就排好了第二個元素…直到比較1次后排好第n-1個元素，第n個元素的位置也就自然確定了。所需的比較次數為（n-1）+（n-2）++1=n（n-1）/2。所需移動次數最多也為n（n-1）/2。如果表中元素排好序，也需要比較n（n-1）/2次，而移動次數為0。

　　3.冒泡排序
　　
　　冒泡排序的基本思想是將表中元素兩個相鄰元素依次比較，若不符合排序要求，則交換位置，這樣經過n-1次比較后，將確定出最大（或最小）元素的位置，這稱為一趟掃描。經過n-1次掃描后，就完成了整個表的排序。第一趟掃描的比較次數是n-1，第二趟掃描的比較次數是n-2……，總的比較次數是（n-1）+（n-2）+……+1=n（n-1）/2。如果恰好表中元素按反序排列，則需要移動的次數為3×n（n-1）/2。如果表中元素已排好序，并采用交換標志來表示并未發生過交換，則只需一趟掃描，只比較n-1次，就夠了;當然，移動次數也是0。
　　
　　4.歸并排序

　　歸并排序的基本思想是表中元素兩兩比較排序，使表中的n個元素變成n/2個已排序的組，再兩兩組比較，而變成n/4個已排序的組……，直到表中只含有一個已排序的組，即完成排序。所需要的比較次數為nlog 2 n，移動次數為n。若表已排好序，則比較次數仍為nlog 2 n，但移動次數為0。

　　5.快速排序

　　快速排序的基本思想是把表中某元素作為基準，將表劃分為大于該值和小于該值的兩部分，然后用遞歸的方法處理這兩個子表，直到完成整個表的排序。快速排序的比較次數為（n-1）+（n-2）+…+1=n（n-1）/2，移動次數最多也是n（n-1）/2。如果每次的基準元素剛好是表的中值，使表分為大小相等的兩個子表，則比較次數為nlog 2 n;如果表已排好序，則移動次數為0。
　　6.常用排序方法的性能比較如下表所示:
　　
　　常用排序方法的性能比較
　　
　　排序方法 平均時間 最壞情況的時間 輔助存儲
　　
　　冒泡法、直接選擇法、直接插入法 O（n2 ） O（n2 ） O（1）
　　
　　快速排序 O（nlog2 n） O（n2 ） O（log2 n）
　　
　　堆排序 O（nlog2n） O（nlog2 n） O（1）
　　
　　歸并排序 O（nlog2 n） O（nlog2 n） O（n）

　　注:在上表中，我們將n（n-1）/2也記為O（n2 ）。如果在待排序的表中含有多個碼值相同的記錄，經過排序后，這些記錄的相對次序不變，則稱這種排序方法是穩定的，否則是不穩定的。根據上述說法，可以看出直接插入法、歸并法是穩定的;而直接選擇法、冒泡法、快速排序法、堆排序法是不穩定的。　

希望與更多計算機等級考試的網友交流，請進入計算機等級考試論壇

更多信息請訪問：考試吧計算機等級考試欄目