資料結構 java

本文整理了程式設計開發中遇到的資料結構方面的知識，适合初步接觸資料結構的讀者閱讀

數組

可以快速讀取和修改數組下标位置存儲的元素值(這時候不需要做比較，隻需要找到對應的下标即可完成通路)，數組中是不允許有“洞”的，即數組中不允許含有空的位置，我們一般建立數組的時候，需要初始化數組中的元素，或者元素個數，在隻初始化元素個數的時候，java語言會為每個數組元素賦預設值。java語言中數組的元素個數是固定，為此提供了ArrayList類對數組進行了擴充。

連結清單

連結清單是利用引用的方式，把元素串聯起來，在前一個元素中包含對後一個元素的引用，形成了連結清單結構，這時候的連結清單叫做單連結清單，再單連結清單的基礎上新增最後一個元素的引用，形成的連結清單結構叫做雙端連結清單，雙端連結清單除了可以快速讀取最後一個元素外，并沒有其他實際的作用，更像是為了引入雙向連結清單的概念，在雙端連結清單的基礎上，後一個元素包含前一個元素的因引用，形成的連結清單結構叫做雙向連結清單，雙向連結清單解決了單連結清單不能向前查找的缺陷，但也使得程式設計更加複雜。java中提供的連結清單實作是LinkedList(基于雙向連結清單實作)。

數組和連結清單的比較

在空間上：數組是記憶體中連續存儲的，大小固定，結構上不靈活，對記憶體的使用率低，除非你能清楚數組的準确大小，否則必有浪費。連結清單是不連續存儲的，可以很好的利用記憶體，但是需要存儲連結的引用，是以單個元素的記憶體開銷上要比數組大。

在時間上：數組因為是連續存儲的，所有讀取速度快，但是插入和删除很慢，因為需要移動資料以防止出現“洞”(為了儲存數組的連續特性，連續特性保證了數組的核心價值，即讀取速度快)，連結清單讀取速度慢，因為需要做比較，但是插入和删除比數組快，因為不需要移動元素，隻需要維護其中的向前和向後引用即可。

簡單排序

冒泡排序：冒泡行為i-1次，雙層for循環實作，外層i-1次标記未排序元素，内層循環j次标記已排序元素，相鄰元素兩兩向前比較交換，直到找到相應順序位置為止。

選擇排序：周遊未排序元素，找到最大的或者最小的，放在已排序元素末尾，循環此過程，雙層for循環實作，外層n-1次标記未排序元素，内層循環j次查找未排序元素中哪個最大或者最小，放在已排序元素末尾。

插入排序：周遊未排序元素，插入已排序元素中間的指定位置，循環此過程，插入排序是冒泡排序的優化，雙層for玄幻，外層n-1次标記未排序元素，内層循環j次把元素插入到已排序元素中間的指定位置

簡單排序比較：冒泡排序最差，選擇排序在冒泡排序的基礎上交換次數少了，比較次數一樣，插入排序的比較次數是冒泡排序的一半，交換次數和比較次數相當，插入排序比冒泡排序快一倍，比選擇排序略快(這是指需要排序的元素非常大的情況下，如果采用java實作，資料量較小的情況下，采用選擇排序更快，因為元素交換比元素比較的開發大的多)。如果是完全亂序，且資料量較小建議使用選擇排序，如果是基本有序，或者資料量超過100萬，建議使用插入排序。

抽象資料類型(棧和隊列)

棧：先進後出

隊列：先進先出，java提供的隊列Queue(同步阻塞隊列ConcurrentLinkedQueue，同步非阻塞隊列BlockingQueue)，優先級隊列PriorityQueue和雙端隊列Deque，一般使用Deque實作棧(棄用Stack，不推薦使用)。

這裡介紹兩個概念

同步、異步：同步是指主調函數等待被調函數傳回，異步是指主調函數不等待，繼續執行，被調函數執行完後通知主調函數執行結果。同步異步是從調用者是否等待來考慮的。

阻塞、非阻塞：阻塞是指被調函數不滿足條件的時候不傳回，滿足情況的時候才傳回。非阻塞是指被調函數不管滿不滿足條件都傳回。阻塞非阻塞是從被調用者是否能及時傳回結果的能力來考慮的。

疊代器

疊代器接口要求實作其的類必須提供三種方法：

hasNext()：周遊過程中，判斷是否還有下一個元素。(從Collection對象的第一個元素開始)

next()：周遊該元素。(即取出下一個元素)

remove()：移除剛剛周遊過的元素(用該方法在疊代過程中中删除符合條件的元素非常快速)

java中的集合大部分都實作了Iterator接口，可以很友善的進行疊代過程。

遞歸

遞歸方法的特性：1、調用自身。2、當它調用自身的時候，它這樣做是為了解決更小的問題。3、存在某個足夠簡單的問題的層次，在這一層算法不需要調用自身就可以直接解答，傳回結果。(遞歸需要消耗方法調用棧的空間和時間，可以采用循環的方式消除遞歸，可以加快程式的運作速度，但一般情況下不需要這麼做，除非遞歸的層級非常多)

分治算法

把一個大問題，分解成兩個相對較小的問題，并且分别解決每一個較小的問題，對每一個較小的問題采用同樣的方法，分解成兩個更小的問題，并且解決它們，這個過程一直持續下去知道易于求解的基值情況，就不用再分了。分治算法一般采用遞歸的方式實作。

進階排序

希爾排序：希爾排序是基于插入排序的更新版本，一般項目在初始階段都可以采用希爾排序，因為它足夠簡單，但是希爾排序不是效率是變動的。因為該算法的效率受間隔算法的影響。希爾排序通過逐漸變小的元素間隔使元素逐漸有序，直到最終有序為止，推薦使用的元素間隔為(h - 1)/3，h為元素個數，元素通過這個間隔進行排序，直到元素間隔為1為止，這是最後一次排序，之後會得到完整的排序後的元素集合。

快速排序：快速排序是最流行的排序算法，因為有充足的理由相信，在大多數情況下，快速排序都是最快的。建議快速排序采用三資料項取中法(最左，中間，最右)來決定分割樞紐，并在元素個數<=9的子分隔中采用插入排序，可以更好的實作快速排序算法。在快速排序中樞紐一般存儲在最右側，然後劃分整個數組，在左邊尋找大于樞紐的，在右邊尋找小于樞紐的，找到後交換它們的位置，直到左邊找到的元素值，大于後邊找到的元素值(這時候左邊位置标記在大于樞紐的元素集合的左側第一個位置，右邊位置标記在小于樞紐的元素集合的右側第一個位置，也有可能相同，這時候元素值等于樞紐值)，交換左邊找到的元素和樞紐元素的位置，完成一個劃分過程，重複此分治劃分的過程，直到整個元素集合有序。