本部分總結(jié)在網(wǎng)站建設(shè)中數(shù)據(jù)結(jié)構(gòu)和算法，并討論在不同的情況下如何進(jìn)行選擇。
通用數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、樹、哈希表
專用數(shù)據(jù)結(jié)構(gòu)：棧、隊列、優(yōu)先級隊列
排序：插入排序、希爾排序、快速排序、歸并排序、堆排序
圖：鄰接矩陣、鄰接表
外部存儲：順序存儲、索引文件、B-樹、哈希方法
若想存儲真實(shí)世界中的類似人事記錄、存貨目錄、合同表或銷售業(yè)績等數(shù)據(jù)，則只需要一般用途的數(shù)據(jù)結(jié)構(gòu)。在本書中屬于這種類型的結(jié)構(gòu)有數(shù)組、鏈表、樹和哈希表。他們被稱之為通用的數(shù)據(jù)結(jié)構(gòu)是因為它們通過關(guān)鍵字的值來存儲并查找數(shù)據(jù)，這一點(diǎn)在通用數(shù)據(jù)庫程序中常見到(棧等特殊結(jié)構(gòu)正好相反，它們只允許存取一定的數(shù)據(jù)項)。
1.1 速度與算法
通用數(shù)據(jù)結(jié)構(gòu)可以完全按照速度的快慢來分類:數(shù)組和鏈表是最慢的，樹相對較快，哈希表是最快的。
但是不要有這樣的結(jié)論:使用最快的結(jié)構(gòu)永遠(yuǎn)是最好的方案。這些最快的結(jié)構(gòu)也有缺陷。首先，它們的程序在不同程度上比數(shù)組和鏈表的復(fù)雜;其次，哈希表要求預(yù)先知道要存儲多少數(shù)據(jù)，數(shù)據(jù)對存儲空間的利用率也不是非常高。普通的二叉樹對順序的數(shù)據(jù)來說，會變成緩慢的O(N)級操作，而平衡樹雖然避免了上述的問題，但是它的程序編制起來卻比較困難。
處理器速度因素
快速的結(jié)構(gòu)都有缺陷，而計算機(jī)的另一個發(fā)展因素卻能使低速的結(jié)構(gòu)更加具有吸引力。新計算機(jī)的CPU和存取速度每一年都有提升。Moore定律聲明了CPU的速度每18個月翻一倍。這造成了早期計算機(jī)和現(xiàn)代應(yīng)用的計算機(jī)在性能方面的驚人差異，而且目前沒有任何理由能忍我這個增長速度會減慢。
幾年前一臺電腦可以在一個可接受的時間內(nèi)處理100個對象的數(shù)組，而現(xiàn)在的計算機(jī)則快多了，因此可以在同樣的時間里處理含有10000個對象的數(shù)組。
請從簡單數(shù)據(jù)結(jié)構(gòu)入手考慮:除非它們明顯是太慢了，否則就用數(shù)組或鏈表編寫程序，看看結(jié)構(gòu)究竟怎樣。如果能在一個可接受的時間內(nèi)運(yùn)行完畢，那么就采用它，不必再找別的。沒有人會留意用的是數(shù)組或別的什么結(jié)構(gòu)，為什么一定要拼命地寫出一個平衡樹的算法?甚至必須面對成千上萬、百萬的數(shù)據(jù)項進(jìn)行操作時，不妨先看一看數(shù)組或鏈表處理表現(xiàn)的情況，這也還是值得的。只有在實(shí)驗中發(fā)現(xiàn)這些簡單結(jié)構(gòu)的性能太慢時，才回過頭來采用哪些更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。
Java引用的優(yōu)點(diǎn)
在操作對象的速度上，Java與其他語言相比有極大的優(yōu)勢，那是由于對于大多數(shù)數(shù)據(jù)結(jié)構(gòu)來說，Java數(shù)據(jù)結(jié)構(gòu)只存儲引用而不是實(shí)際的對象，因此相對于那些在數(shù)據(jù)結(jié)構(gòu)中實(shí)際為對象開辟了空間的語言來說，大多數(shù)Java算法的執(zhí)行速度更快。在分析算法時，不是從對象的真實(shí)存儲空間出發(fā)，因而移動對象的速度也不依賴于對象的大小，而只是考慮對象引用的移動，因此對象本身的大小就不重要了。
數(shù)組
當(dāng)存儲和操作數(shù)據(jù)時，在大多數(shù)情況下數(shù)組是首先應(yīng)該考慮的結(jié)構(gòu)，數(shù)組在下列情況下很有用:
數(shù)據(jù)量較小
數(shù)據(jù)量的大小事先可預(yù)測
如果存儲空間足夠大的話，可以放松第二條，創(chuàng)建一個足夠大的數(shù)組來應(yīng)付所有可以預(yù)見的數(shù)據(jù)輸入。
如果插入速度很重要的話，使用無序數(shù)組，如果查找速度很重要的話，使用有序數(shù)組，并用二分查找。數(shù)組元素的刪除總是很慢，這是由于未來填充空出來的單元，平均半數(shù)以上的數(shù)組元素要被移動，在有序數(shù)組中的遍歷是很快的，而在無序數(shù)組不支持這種功能。向量類是一種當(dāng)數(shù)據(jù)太滿時可以自己擴(kuò)展空間的數(shù)組，向量可以應(yīng)用于數(shù)據(jù)量不可預(yù)知的情況下，然而，在向量擴(kuò)充時，要將舊的數(shù)據(jù)拷入一個新的空間中，這一過程會造成程序明顯的周期性暫停。
鏈表
如果需要存儲的數(shù)據(jù)量不能預(yù)知或者需要頻繁地插入刪除數(shù)據(jù)元素時，考慮使用鏈表。當(dāng)有新的元素加入時，鏈表就開辟新的所需要的空間，所以它甚至可以占滿全部可用的內(nèi)存;在刪除過程中，沒必要像數(shù)組那樣填補(bǔ)"空白"
在一個無序的鏈表中，插入是相當(dāng)快的，查找和刪除卻很慢，因此，與數(shù)組一樣，鏈表最好也應(yīng)用于數(shù)據(jù)量相對較小的情況。
對于編程而言，鏈表比數(shù)組復(fù)雜，但它比樹或哈希表簡單。
二叉搜索樹
當(dāng)確認(rèn)數(shù)組和鏈表過慢時，二叉搜索樹是最先應(yīng)該考慮的結(jié)果，樹可以提供快速的O(logN)級的插入、查找和刪除。遍歷的時間復(fù)雜度是O(N)級的，這是任何數(shù)據(jù)結(jié)構(gòu)遍歷的最大值(根據(jù)定義，必須訪問所有的數(shù)據(jù))。對于遍歷一定范圍內(nèi)的數(shù)據(jù)可以很快得出訪問數(shù)據(jù)的最大值或最小值。
對于程序來說，不平衡的二叉搜索樹要比平衡的二叉樹簡單得多，但不幸的是，有序數(shù)據(jù)能將它的性能降至O(N)級，不比一個鏈表好多歲，然而如果可以保證數(shù)據(jù)是隨機(jī)進(jìn)入的，就不需要用平衡二叉樹。
平衡樹
在眾多平衡樹中，我們討論了紅黑樹和2-3-4樹，它們都是平衡樹，并且無論輸入數(shù)據(jù)是否有序，它們都能保證性能為O(logN)。然而對于實(shí)現(xiàn)來說，平衡樹是很復(fù)雜的，特別是紅黑樹。如果利用樹的商用類，可以降低復(fù)雜性。
哈希表
哈希表在數(shù)據(jù)存儲結(jié)構(gòu)中速度最快，這使它成為計算機(jī)而不是人與數(shù)據(jù)交互時的必需。哈希表通常用于拼寫檢查器和作為計算機(jī)語言編譯器的符號表，這些應(yīng)用中，程序必須在幾分之一秒的時間里檢查上千的詞或符號。
哈希表對插入的順序并不敏感，因此可以取代平衡樹。但是哈希表的編程比平衡樹簡單多了。
哈希表需要有額外的存儲空間，尤其是對于開放地址法，因為哈希表用數(shù)組作為基本結(jié)構(gòu)，所以，必須預(yù)先精確地知道待存儲的數(shù)據(jù)量。
用鏈地址法處理沖突的哈希表是最健壯的實(shí)現(xiàn)方法，若能預(yù)先精確地知道數(shù)據(jù)量，在這種情況下，用開放地址法編程最簡單，因為不需要用到鏈表類。
哈希表并不能提供任何形式的有序遍歷，或?qū)ψ畲笾?、最小值進(jìn)行存取，如果這些功能很重要，使用二叉樹更好些。
通用數(shù)據(jù)存儲結(jié)構(gòu)的比較
專用數(shù)據(jù)結(jié)構(gòu)有棧、隊列和優(yōu)先級隊列。這些結(jié)構(gòu)不是為了用戶可訪問的數(shù)據(jù)庫而建立的，通常用它們在程序中輔助實(shí)現(xiàn)一些算法。
棧、隊列和優(yōu)先級隊列是抽象數(shù)據(jù)類型，它們由一些更加基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)如數(shù)組、鏈表或堆來實(shí)現(xiàn)。這些ADT只提供給用戶間的的接口，一般僅允許插入和訪問或者刪除一個數(shù)據(jù)項。這些數(shù)據(jù)項是：
對于棧：最后被插入的數(shù)據(jù)項
對于隊列：最先被插入的數(shù)據(jù)項
對于優(yōu)先級隊列：具有最高優(yōu)先級的數(shù)據(jù)項
棧
棧用在最后被插入數(shù)據(jù)項訪問的時候，它是一個后進(jìn)先出的結(jié)構(gòu)。
棧往往通過數(shù)組或鏈表實(shí)現(xiàn)，通過數(shù)組實(shí)現(xiàn)很有效率，因為最后被插入的數(shù)據(jù)總是在數(shù)組的最后，這個位置的數(shù)據(jù)很容易被刪除。棧的溢出有可能出現(xiàn)，但當(dāng)數(shù)組的大小被合理規(guī)劃后，溢出并不常見，因為棧很少會擁有大量的數(shù)據(jù)。
如果棧擁有許多數(shù)據(jù)，并且數(shù)量不可精確預(yù)測(當(dāng)用棧實(shí)現(xiàn)遞歸時)，用鏈表比數(shù)組更好一些，這是由于從表頭的位置刪除或插入一個元素很方便，除非整個內(nèi)存滿了，棧的溢出不可能出現(xiàn)。鏈表比數(shù)組稍慢一些，因為對于插入一個新鏈結(jié)必須分配內(nèi)存，從表中某個鏈結(jié)點(diǎn)上刪除元素后回收分配內(nèi)存亦是必須的。
隊列
隊列用在只對最先被插入數(shù)據(jù)項訪問的時候，它是一個先進(jìn)先出的結(jié)構(gòu)。
同棧相比，隊列同樣可以通過數(shù)組和鏈表實(shí)現(xiàn)，這兩種方法都很有效率。數(shù)組需要附加的程序來處理隊在數(shù)組尾部回繞的情況。鏈表必須是雙端的，這樣才能從一端插入到另一端刪除。
用數(shù)組還是鏈表來實(shí)現(xiàn)隊列的選擇是通過數(shù)據(jù)量是否可以被很好地預(yù)測來決定的，如果知道會有多少數(shù)據(jù)量的話，就使用數(shù)組，否則的話就用鏈表。
優(yōu)先級隊列
優(yōu)先級隊列用在只對訪問最高優(yōu)先級數(shù)據(jù)項訪問的時候，最高優(yōu)先級數(shù)據(jù)項就是含有最大(有時最小)的關(guān)鍵字的項。
優(yōu)先級隊列可以用有序數(shù)組或堆來實(shí)現(xiàn)，向有序數(shù)組中插入是很慢的，但是刪除很快，使用堆來實(shí)現(xiàn)優(yōu)先級隊列，插入和刪除的時間復(fù)雜度都是O(logN)級
當(dāng)插入速度不重要時，可以使用數(shù)組或雙端鏈表，當(dāng)數(shù)據(jù)量可以被預(yù)測時，使用數(shù)組，當(dāng)數(shù)據(jù)量未知時，可以使用鏈表，如果速度很重要的話，選擇堆更好一些。
專用結(jié)構(gòu)的比較
當(dāng)選擇數(shù)據(jù)結(jié)構(gòu)時，可以先嘗試一種較慢但簡單的排序，例如插入排序。如果采用了這些方法，現(xiàn)代計算機(jī)的快速處理速度也有可能在恰當(dāng)?shù)臅r間內(nèi)將較大的數(shù)據(jù)量排序。
插入排序?qū)缀跻雅藕玫奈募埠苡行?，如果沒有太多的元素處于亂序的位置上，操作的時間復(fù)雜度大約在O(N)級，這通常發(fā)生在往一個已排好序的文件中插入一些新的數(shù)據(jù)元素的情況。
如果插入排序顯得太慢，下一步可以嘗試希爾排序，它很容易實(shí)現(xiàn)，并且使用起來不會因為條件不同而性能變化差距太大：Sedgewick估計它的數(shù)據(jù)量為5000以下時很有用。
只有當(dāng)希爾排序變得很慢時，你才應(yīng)該使用那些更復(fù)雜但更快速的排序方法：歸并排序、堆排序或快速排序。歸并排序需要輔助存儲空間，堆排序需要有一個堆的數(shù)據(jù)結(jié)構(gòu)，前兩者都比快速排序在某些程度上慢，所以當(dāng)需要最短的排序時間時經(jīng)常選擇快速排序。
然而，快速排序在處理非隨機(jī)性能數(shù)據(jù)時性能不大可靠，因為那時它的速度有可能退化至O(N^2)級。
對那些有可能是非隨機(jī)性的數(shù)據(jù)來說，堆排序更加可靠，當(dāng)快速排序沒有被正確地實(shí)現(xiàn)時，它會產(chǎn)生微小偏差，在代碼中細(xì)小的錯誤會使它對按某些順序排列的數(shù)據(jù)無能為力，而診斷這種情況又相當(dāng)難。
下面是幾種排序算法的時間復(fù)雜度級別
對于網(wǎng)站建設(shè)中數(shù)據(jù)結(jié)構(gòu)和算法的選擇，看到這里，相信你已經(jīng)學(xué)會了。
