Java進階專題(十六) 資料結構與演算法的應用(上)

itread01 2020-11-06 20:27:50
java 算法 演算法 演算 十六


# 前言 ​ 學習演算法,我們不需要死記硬背那些冗長複雜的背景知識、底層原理、指令語法……需要做的是領悟演算法思想、理解演算法對記憶體空間和效能的影響,以及開動腦筋去尋求解決問題的最佳方案。相比程式設計領域的其他技術,演算法更純粹,更接近數學,也更具有趣味性。 ​ 本文將回顧資料結構與演算法的基礎知識,學習日常所接觸場景中的一些演算法和策略,以及這些演算法的原理和他背後的思想,最後會動手寫程式碼,用java裡的資料結構來實現這些演算法,如何去做? ​ 本文基本知識概念有借鑑《漫畫演算法-小灰的演算法之旅》相關篇幅與圖片。 # 基本概念回顧 ## 什麼是資料結構 1)概述 資料結構是計算機儲存、組織資料的方式。資料結構是指相互之間存在一種或多種特定關係的資料元素的集合。通常情況下,精心選擇的資料結構可以帶來更高的執行或者儲存效率。 2)劃分 從關注的維度看,資料結構可以劃分為資料的邏輯結構和物理結構,同一邏輯結構可以對應不同的儲存結構。邏輯結構反映的是資料元素之間的邏輯關係,邏輯關係是指資料元素之間的前後間以什麼形式相互關聯,這與他們在計算機中的儲存位置無關。邏輯結構包括: **集合**:只是扎堆湊在一起,沒有互相之間的關聯 **線性結構**:一對一關聯,隊形 **樹形結構**:一對多關聯,樹形 **圖形結構**:多對多關聯,網狀 資料物理結構指的是邏輯結構在計算機儲存空間中的存放形式(也稱為儲存結構)。一般來說,一種資料結構的邏輯結構根據需要可以表示成多種儲存結構,常用的儲存結構有順序儲存、鏈式儲存、索引儲存和雜湊儲存等。 **順序儲存**:用一組地址連續的儲存單元依次儲存集合的各個資料元素,可隨機存取,但增刪需要大批移動 **鏈式儲存**:不要求連續,每個節點都由資料域和指標域組成,佔據額外空間,增刪快,查詢慢需要遍歷 **索引儲存**:除建立儲存結點資訊外,還建立附加的索引表來標識結點的地址。檢索快,空間佔用大 **雜湊儲存**:將資料元素的儲存位置與關鍵碼之間建立確定對應關係,檢索快,存在對映函式碰撞問題 3)程式中常見的資料結構 **陣列**(Array):連續儲存,線性結構,可根據偏移量隨機讀取,擴容困難 **棧**( Stack):線性儲存,只允許一端操作,先進後出,類似水桶 **佇列**(Queue):類似棧,可以雙端操作。先進先出,類似水管 **連結串列**( LinkedList):鏈式儲存,配備前後節點的指標,可以是雙向的 **樹**( Tree):典型的非線性結構,從唯一的根節點開始,子節點單向執行前驅(父節點) **圖**(Graph):另一種非線性結構,由節點和關係組成,沒有根的概念,互相之間存在關聯 **堆**(Heap):特殊的樹,特點是根結點的值是所有結點中最小的或者最大的,且子樹也是堆 **散列表**(Hash):源自於雜湊函式,將值做一個函式式對映,對映的輸出作為儲存的地址 ## 什麼是演算法 ​ 演算法指的是基於儲存結構下,對資料如何有效的操作,採用什麼方式可以更有效的處理資料,提高資料運算效率。資料的運算是定義在資料的邏輯結構上,但運算的具體實現要在儲存結構上進行。一般涉及的操作有以下幾種: **檢索**:在資料結構裡查詢滿足一定條件的節點。 **插入**:往資料結構中增加新的節點,一般有一點位置上的要求。 **刪除**:把指定的結點從資料結構中去掉,本身可能隱含有檢索的需求。 **更新**:改變指定節點的一個或多個欄位的值,同樣隱含檢索。 **排序**:把節點裡的資料,按某種指定的順序重新排列,例如遞增或遞減。 #資料結構基礎 ## 陣列 ​ 陣列對應的英文是array,是有限個相同型別的變數所組成的有序集合,陣列中的每一個變數被稱為元素。陣列是最為簡單、最為常用的資料結構。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160533477-547316772.png) 陣列的另一個特點,是在記憶體中順序儲存,因此可以很好地實現邏輯上的順序表。 記憶體是由一個個連續的記憶體單元組成的,每一個記憶體單元都有自己的地址。在這些記憶體單元中,有些被其他資料佔用了,有些是空閒的。 陣列中的每一個元素,都儲存在小小的記憶體單元中,並且元素之間緊密排列,既不能打亂元素的儲存順序,也不能跳過某個儲存單元進行儲存。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160533677-235359505.png) ## 連結串列 連結串列(linked list)是一種在物理上非連續、非順序的資料結構,由若干節點(node)所組成。 單向連結串列的每一個節點又包含兩部分,一部分是存放資料的變數data,另一部分是指向下一個節點的指標next。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160542215-1524883818.png) 雙向連結串列比單向連結串列稍微複雜一些,它的每一個節點除了擁有data和next指標,還擁有指向前置節點的prev指標。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160549821-1525760646.png) 如果說陣列在記憶體中的儲存方式是順序儲存,那麼連結串列在記憶體中的儲存方式則是隨機儲存。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160557488-248927271.png) ## 棧和佇列 ​ **棧**(stack)是一種線性資料結構,它就像一個上圖所示的放入乒乓球的圓筒容器,棧中的元素只能先入後出(First In Last Out,簡稱FILO)。最早進入的元素存放的位置叫作棧底(bottom),最後進入的元素存放的位置叫作棧頂(top)。 棧這種資料結構既可以用陣列來實現,也可以用連結串列來實現。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160605274-1145152888.png) **佇列**(queue)是一種線性資料結構,它的特徵和行駛車輛的單行隧道很相似。不同於棧的先入後出,佇列中的元素只能先入先出(First In First Out,簡稱FIFO)。佇列的出口端叫作隊頭(front),佇列的入口端叫作隊尾(rear)。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160612717-686040122.png) ## 散列表 ​ 散列表也叫作雜湊表(hash table),這種資料結構提供了鍵(Key)和值(Value)的對映關係。只要給出一個Key,就可以高效查詢到它所匹配的Value,時間複雜度接近於O(1)。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160620602-723968889.png) ​ 由於陣列的長度是有限的,當插入的Entry越來越多時,不同的Key通過雜湊函式獲得的下標有可能是相同的。這種情況,就叫作雜湊衝突。 解決雜湊衝突的方法主要有兩種,一種是**開放定址法**,一種是**連結串列法**。 開放定址法的原理很簡單,當一個Key通過雜湊函式獲得對應的陣列下標已被佔用時,我們可以“另謀高就”,尋找下一個空檔位置。 這就是開放定址法的基本思路。當然,在遇到雜湊衝突時,定址方式有很多種,並不一定只是簡單地尋找當前元素的後一個元素,這裡只是舉一個簡單的示例而已。在Java中,ThreadLocal所使用的就是開放定址法。 接下來,重點講一下解決雜湊衝突的另一種方法——**連結串列法**。這種方法被應用在了Java的集合類HashMap當中。 HashMap陣列的每一個元素不僅是一個Entry物件,還是一個連結串列的頭節點。每一個Entry物件通過next指標指向它的下一個Entry節點。當新來的Entry對映到與之衝突的陣列位置時,只需要插入到對應的連結串列中即可。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160629184-1546296876.png) ## 樹 樹和圖就是典型的非線性資料結構,我們首先講一講樹的知識。 樹(tree)是n(n≥0)個節點的有限集。當n=0時,稱為空樹。在任意一個非空樹中,有如下特點。 1. 有且僅有一個特定的稱為根的節點。 2. 當n>1時,其餘節點可分為m(m>0)個互不相交的有限集,每一個集合本身又是一個樹,並稱為根的子樹。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160637110-1786160888.png) ### 二叉樹 **二叉樹**(binary tree)是樹的一種特殊形式。二叉,顧名思義,這種樹的每個節點最多有2個孩子節點。注意,這裡是最多有2個,也可能只有1個,或者沒有孩子節點。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160644730-1465014156.png) ​ 二叉樹節點的兩個孩子節點,一個被稱為左孩子(left chi ld),一個被稱為右孩子(right chi ld)。這兩個孩子節點的順序是固定的,就像人的左手就是左手,右手就是右手,不能夠顛倒或混淆。此外,二叉樹還有兩種特殊形式,一個叫作**滿二叉樹**,另一個叫作**完全二叉樹**。 **二叉樹儲存結構** 1. 鏈式儲存結構。 2. 陣列。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160652942-1883413147.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160701431-1476191012.png) ## 小結 **什麼是陣列** 陣列是由有限個相同型別的變數所組成的有序集合,它的物理儲存方式是順序儲存,訪問方式是隨機訪問。利用下標查詢陣列元素的時間複雜度是O(1),中間插入、刪除陣列元素的時間複雜度是O(n)。 **什麼是連結串列** 連結串列是一種鏈式資料結構,由若干節點組成,每個節點包含指向下一節點的指標。連結串列的物理儲存方式是隨機儲存,訪問方式是順序訪問。查詢連結串列節點的時間複雜度是O(n),中間插入、刪除節點的時間複雜度是O(1)。 **什麼是棧** 棧是一種線性邏輯結構,可以用陣列實現,也可以用連結串列實現。棧包含入棧和出棧操作,遵循先入後出的原則(FILO)。 **什麼是佇列** 佇列也是一種線性邏輯結構,可以用陣列實現,也可以用連結串列實現。佇列包含入隊和出隊操作,遵循先入先出的原則(FIFO)。 **什麼是散列表** 散列表也叫雜湊表,是儲存Key-Value對映的集合。對於某一個Key,散列表可以在接近O(1)的時間內進行讀寫操作。散列表通過雜湊函式實現Key和陣列下標的轉換,通過開放定址法和連結串列法來解決雜湊衝突。 **什麼是樹** 樹是n個節點的有限集,有且僅有一個特定的稱為根的節點。當n>1時,其餘節點可分為m個互不相交的有限集,每一個集合本身又是一個樹,並稱為根的子樹。 **什麼是二叉樹** 二叉樹是樹的一種特殊形式,每一個節點最多有兩個孩子節點。二叉樹包含完全二叉樹和滿二叉樹兩種特殊形式。 **二叉樹的遍歷方式有幾種** 根據遍歷節點之間的關係,可以分為前序遍歷、中序遍歷、後序遍歷、層序遍歷這4種方式;從更巨集觀的角度劃分,可以劃分為深度優先遍歷和廣度優先遍歷兩大類。 **什麼是二叉堆** 二叉堆是一種特殊的完全二叉樹,分為最大堆和最小堆。 在最大堆中,任何一個父節點的值,都大於或等於它左、右孩子節點的值。 在最小堆中,任何一個父節點的值,都小於或等於它左、右孩子節點的值。 **什麼是優先佇列** 優先佇列分為最大優先佇列和最小優先佇列。 在最大優先佇列中,無論入隊順序如何,當前最大的元素都會優先出隊,這是基於最大堆實現的。 在最小優先佇列中,無論入隊順序如何,當前最小的元素都會優先出隊,這是基於最小堆實現的。 # 排序演算法 ## 氣泡排序 氣泡排序的英文是bubble sort,它是一種基礎的交換排序。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160714432-2145324432.png) 按照氣泡排序的思想,我們要把相鄰的元素兩兩比較,當一個元素大於右側相鄰元素時,交換它們的位置;當一個元素小於或等於右側相鄰元素時,位置不變。 排序過程如下 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160724131-357428186.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160732005-803804173.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160739380-529072320.png) 到此為止,所有元素都是有序的了,這就是氣泡排序的整體思路。 **氣泡排序是一種穩定排序,值相等的元素並不會打亂原本的順序。由於該排序演算法的每一輪都要遍歷所有元素,總共遍歷(元素數量-1)輪,所以平均時間複雜度是O(n2)。** ## 快速排序 同氣泡排序一樣**,快速排序也屬於交換排序**,通過元素之間的比較和交換位置來達到排序的目的。 不同的是,氣泡排序在每一輪中只把1個元素冒泡到數列的一端,而快速排序則在每一輪挑選一個基準元素,並讓其他比它大的元素移動到數列一邊,比它小的元素移動到數列的另一邊,從而把數列拆解成兩個部分。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160747967-699865314.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160755145-1467755809.png) 在分治法的思想下,原數列在每一輪都被拆分成兩部分,每一部分在下一輪又分別被拆分成兩部分,直到不可再分為止。 每一輪的比較和交換,需要把陣列全部元素都遍歷一遍,時間複雜度是O(n)。這樣的遍歷一共需要多少輪呢?假如元素個數是n,那麼平均情況下需要logn輪,因此快速排序演算法總體的平均時間複雜度是O(nlogn)。 ## 堆排序 堆排序演算法的步驟。 1. 把無序陣列構建成二叉堆。 2. 迴圈刪除堆頂元素,並將該元素移到集合尾部,調整堆產生新的堆頂。 第1步,把無序陣列構建成二叉堆,這一步的時間複雜度是O(n)。 第2步,需要進行n-1次迴圈。每次迴圈呼叫一次downAdjust方法,所以第2步的計算規模是 (n-1)×logn ,時間複雜度為O(nlogn)。兩個步驟是並列關係,所以整體的時間複雜度是O(nlogn)。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160803209-2070405092.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160810345-617936514.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160819773-713427471.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160827317-395546824.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160835875-1969167018.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160843222-1283241656.png) ## 計數排序和桶排序 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160852979-1182785436.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160900692-580985226.png) 讓我們來看看桶排序的工作原理。 桶排序的第1步,就是建立這些桶,並確定每一個桶的區間範圍。 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160908160-1655159688.png) ## 小結 ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160916021-14027729
版权声明
本文为[itread01]所创,转载请带上原文链接,感谢
https://www.itread01.com/content/1604665445.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云