有哪些JAVA必須掌握的數據結構和算法

本篇內容主要講解“有哪些JAVA必須掌握的數據結構和算法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“有哪些JAVA必須掌握的數據結構和算法”吧!

常見的數據結構

鏈表

LinkedHashSet LinkedList 底層數據結構由鏈表和哈希表組成。
數據的添加和刪除都較為方便，就是訪問比較耗費時間。

數組

ArrayList 訪問數據十分簡單，而添加和刪除數據比較耗工夫

堆

• 堆是一種圖的樹形結構，被用于實現“優先隊列",優先隊列是一種數據結構，可以自由添加數據，但取出數據時要從最小值開始按順序取出

• 堆的特點：
  ①堆中的每個結點最多有兩個子結點
  ②子結點必定大于父結點
  ③把新數據放在最下面一行靠左的位置。當最下面一行里沒有多余空間時，就再往下另起一行，把數據加在這一行的最左端
  ④如果子結點的數字小于父結點的，就將父結點與其左右兩個子結點中較小的一個進行交換
  堆中最頂端的數據始終最小，所以無論數據量有多少，取出最小值的時間復雜度都為O（1）
  可知樹的高度為log2n，那么重構樹的時間復雜度便為O（logn）

棧 （LIFO）

略

隊列 (FIFO)

略

哈希表 HashSet

• TreeSet底層數據結構是紅黑樹

• 哈希函數（Hash）計算key,哈希值除以數組的長度5，求得其余數。這個余數就是key的編號即位置

• 如果發生哈希沖突，就使用鏈表進行存儲（鏈地址法）給數組設定合適的空間非常重要
  除了鏈地址法以外，還有幾種解決沖突的方法。其中，應用較為廣泛的是“開放地址法”。這種方法是指當沖突發生時，立刻計算出一個候補地址（數組上的位置）并將數據存進去。如果仍然有沖突，便繼續計算下一個候補地址，直到有空地址為止。可以通過多次使用哈希函數或“線性探測法”等方法計算候補地址。

二叉樹

• 特點：
  ①第一個是每個結點的值均大于其左子樹上任意一個結點的值
  ②是每個結點的值均小于其右子樹上任意一個結點的值
  ③二叉查找樹的最小結點要從頂端開始，往其左下的末端尋找。此處最小值為3。
  ④二叉查找樹的最大結點要從頂端開始，往其右下的末端尋找
  添加數據的時候 與頂端數據比較 如果比他小就往左移，左邊沒有節點了就把插入的數據作為新節點添加到左下方，大于他則往右移（左小右大）

刪除數據的時候 如果節點沒有子節點 直接刪 如果有一個 刪了后子節點補上，如果有兩個，刪掉后從左子樹中中找最大的補上

比較的次數取決于樹的高度。所以如果結點數為n，而且樹的形狀又較為均衡的話，比較大小和移動的次數最多就是log2n。因此，時間復雜度為O（logn）。但是，如果樹的形狀朝單側縱向延伸，樹就會變得很高，此時時間復雜度也就變成了O（n）。

常見的算法整理

排序

• 冒泡排序
  冒泡排序就是重復“從序列右邊開始比較相鄰兩個數字的大小，再根據結果交換兩個數字的位置”這一操作的算法。在這個過程中，數字會像泡泡一樣，慢慢從右往左“浮”到序列的頂端，所以這個算法才被稱為“冒泡排序”
  冒泡排序的時間復雜度為O（n2）

• 選擇排序
  選擇排序就是重復“從待排序的數據中尋找最小值，將其與序列最左邊的數字進行交換”這一操作的算法。在序列中尋找最小值時使用的是線性查找
  每輪中交換數字的次數最多為1次。如果輸入數據就是按從小到大的順序排列的，便不需要進行任何交換。選擇排序的時間復雜度也和冒泡排序的一樣，都為O（n2）。

• 插入排序
  插入排序的思路就是從右側的未排序區域內取出一個數據，然后將它插入到已排序區域內合適的位置上
  時間復雜度和冒泡排序的一樣，都為O（n2）。

• 堆排序
  首先堆中存儲所有的數據，并按降序來構建堆，然后從降序排列的堆中取出數據時會從最大的數據開始取，所以將取出的數據反序輸出，排序就完成了。
  堆排序的時間復雜度為O（nlogn）。

• 歸并排序
  歸并排序算法會把序列分成長度相同的兩個子序列，當無法繼續往下分時（也就是每個子序列中只有一個數據時），就對子序列進行歸并。歸并指的是把兩個排好序的子序列合并成一個有序序列。該操作會一直重復執行，直到所有子序列都歸并為一個整體為止。
  運行時間復雜度為O（nlogn）

• 快速排序
  快速排序算法首先會在序列中隨機選擇一個基準值（pivot），然后將除了基準值以外的數分為“比基準值小的數”和“比基準值大的數”這兩個類別。解決子問題的時候會再次使用快速排序，甚至在這個快速排序里仍然要使用快速排序。只有在子問題里只剩一個數字的時候，排序才算完成。
  整體的時間復雜度為O（nlogn）。

數組查找

• 線性查找
  線性查找需要從頭開始不斷地按順序檢查數據，因此在數據量大且目標數據靠后，或者目標數據不存在時，比較的次數就會更多，也更為耗時。若數據量為n，線性查找的時間復雜度便為O（n）。

• 二分查找（略）

圖的搜索

• 廣度優先搜索
  廣度優先搜索是一種對圖進行搜索的算法。假設我們一開始位于某個頂點（即起點），此時并不知道圖的整體結構，而我們的目的是從起點開始順著邊搜索，直到到達指定頂點（即終點）。在此過程中每走到一個頂點，就會判斷一次它是否為終點。廣度優先搜索會優先從離起點近的頂點開始搜索

• 深度優先搜索
  深度優先搜索和廣度優先搜索一樣，都是對圖進行搜索的算法，目的也都是從起點開始搜索直到到達指定頂點（終點）。深度優先搜索會沿著一條路徑不斷往下搜索直到不能再繼續為止，然后再折返，開始搜索下一條候補路徑。

• 貝爾曼-福特算法（略）
  貝爾曼-福特（Bellman-Ford）算法是一種在圖中求解最短路徑問題的算法

• 狄克斯特拉算法（略）

• A*算法（略）

安全算法

• 共享密鑰加密

• 公開密鑰加密

• 混合加密

• 迪菲-赫爾曼交換

其他算法

• k-means 算法

• 歐幾里得算法

• 素性測試

• 網頁排名

• 漢諾塔

【拓展】

1. 圖的表示：鄰接矩陣和鄰接表
   遍歷算法：深度搜索和廣度搜索(必學)
   最短路徑算法：Floyd，Dijkstra（必學）
   最小生成樹算法：Prim，Kruskal（必學）
   實際常用算法：關鍵路徑、拓撲排序（原理與應用）
   二分圖匹配：配對、匈牙利算法（原理與應用）
   拓展：中心性算法、社區發現算法（原理與應用）

2.圖還是比較難的，不過我覺得圖涉及到的挺多算法都是挺實用的，例如最短路徑的計算等，圖相關的，我這里還是建議看書的，可以看《算法第四版》。

3、搜索與回溯算法

貪心算法（必學）
啟發式搜索算法：A*尋路算法（了解）
地圖著色算法、N 皇后問題、最優加工順序
旅行商問題

這方便的只是都是一些算法相關的，我覺得如果可以，都學一下。像貪心算法的思想，就必須學的了。建議通過刷題來學習，leetcode 直接專題刷。

4、動態規劃

樹形DP：01背包問題
線性DP：最長公共子序列、最長公共子串
區間DP：矩陣最大值（和以及積）
數位DP：數字游戲
狀態壓縮DP：旅行商

我覺得動態規劃是最難的一個算法思想了，記得當初第一次接觸動態規劃的時候，是看01背包問題的，看了好久都不大懂，懵懵懂懂，后面懂了基本思想，可是做題下不了手，但是看的懂答案。一氣之下，再leetcdoe專題連續刷了幾十道，才掌握了動態規劃的套路，也有了自己的一套模板。不過說實話，動態規劃，是考的真他媽多，學習算法、刷題，一定要掌握。這里建議先了解動態規劃是什么，之后 leetcode 專題刷，反正就一般上面這幾種題型。

5、字符匹配算法

正則表達式
模式匹配：KMP、Boyer-Moore

6、流相關算法

最大流：最短增廣路、Dinic 算法
最大流最小割：最大收益問題、方格取數問題
最小費用最大流：最小費用路、消遣

到此，相信大家對“有哪些JAVA必須掌握的數據結構和算法”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！