itread01
2020-11-06 20:27:50

application
data
structure
algorithm
java

# Preface Learning algorithms , We don't have to memorize the long and complicated background knowledge 、 Underlying principle 、 Instruction syntax …… What we need to do is to understand the idea of algorithm 、 Understanding the impact of algorithms on memory space and performance , And use your brain to find the best solution to the problem . Compared with other technologies in the field of programming , The algorithm is more pure , Closer to Mathematics , It's also more interesting . This article reviews the basics of data structure and algorithms , Learn some algorithms and strategies in everyday scenes , And the principles of these algorithms and the ideas behind him , Finally, I will move the handwritten code , use java To implement these algorithms , How to do it ？ The concept of basic knowledge in this paper can be used for reference 《 Cartoon algorithm - Xiao Hui's calculus tour 》 Relevant space and pictures . # Review of basic concepts ## What is data structure 1） summary Data structure is computer storage 、 The way you organize your data . Data structure refers to the collection of data elements that have one or more specific relationships with each other . Usually , Carefully chosen data structures can lead to higher execution or storage efficiency . 2） Division From the dimension of concern , Data structure can be divided into logical structure and physical structure of data , The same logical structure can correspond to different storage structures . The logical structure reflects the logical relationship between data elements , Logical relation refers to the form in which data elements are related to each other , It's not about where they store in the computer . The logical structure includes ： ** aggregate **： It's just a bunch of them , There's no correlation between them ** Linear structure **： One to one connection , Formation ** Tree structure **： One to many connection , Tree form ** Graphic structure **： Many to many Association , Mesh Physical structure of data refers to the storage form of logical structure in computer storage space ( Also known as storage structure ). In general , The logical structure of a data structure can be expressed as a variety of storage structures as needed , The common storage structure is sequential storage 、 Chain storage 、 Index storage and hash storage, etc . ** Sequential storage **： A set of address contiguous storage units are used to store the data elements of a collection in turn , Random access , But adding and deleting requires a lot of moving ** Chain storage **： No continuity is required , Each node consists of data field and indicator field , Take up extra space , Add and delete quickly , Query slow, need to traverse ** Index storage **： In addition to creating and storing node information , Additional index tables are also established to identify the address of the node . Search fast , It takes up a lot of space ** Hash storage **： The storage location of the data element and the key are established to determine the corresponding relationship , Search fast , There is a problem of the collision of the mapping functions 3） The structure of the program ** Array **(Array)： Continuous storage , Linear structure , It can be read randomly according to the offset , It's difficult to expand ** Stack **( Stack)： Linear storage , Only one side is allowed to operate , First in first out , It's like a bucket ** Waiting for **(Queue)： It's like a stack , It can be operated on both ends . First in, first out , It's like a water pipe ** Link string **( LinkedList)： Chain storage , Equipped with indicators of the front and rear nodes , It can be two-way ** Tree **( Tree)： Typical nonlinear structures , Start with the unique root node , The child node performs one-way precursor （ Parent node ） ** Graph **(Graph)： Another nonlinear structure , It consists of nodes and relationships , There is no concept of roots , There's a connection between them ** Pile up **(Heap)： Special trees , The characteristic is that the value of the root node is the smallest or the largest among all nodes , And the subtree is also a heap ** Hash table **(Hash)： From the hash function , The value is mapped as a function , The output of the map is used as the stored address ## What is algorithm Algorithms are based on the storage structure , How to operate data effectively , What kind of method can be used to process data more effectively , Improve the efficiency of data operation . Data operations are defined in the logical structure of the data , But the concrete implementation of the operation should be carried out in the storage structure . The following operations are generally involved ： ** Retrieve **： Query nodes that satisfy certain conditions in the data structure . ** Insert **： Add new nodes to the data structure , Generally, there is a bit of position requirement . ** Delete **： Remove the specified node from the data structure , It may imply the need for retrieval . ** to update **： Change the value of one or more fields of a specified node , Also implied Retrieval . ** Sort **： Put the data in the node , Rearrange in a specified order , For example, increasing or decreasing . # Data structure basis ## Array The corresponding English of array is array, Is an ordered set of finite variables of the same type , Each variable in an array is called an element . Arrays are the simplest 、 The most commonly used data structure . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160533477-547316772.png) Another feature of the array , It's stored sequentially in memory , So it can be implemented logically in order table . Memory is made up of successive memory units , Each memory unit has its own address . In these memory units , Some are occupied by other data , Some are free . Every element in the array , It's stored in small memory cells , And the elements are closely aligned , It can't disturb the storage order of elements , You can't skip a storage unit to store . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160533677-235359505.png) ## Link string Link string （linked list） It's a physical discontinuity 、 Non sequential data structures , By a number of nodes （node） It consists of . Each node in a unidirectional concatenation contains two parts , Part of it is the variables that hold the data data, The other part is the indicator pointing to the next node next. ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160542215-1524883818.png) Bidirectional concatenation is a little more complicated than unidirectional concatenation , Every node in it has data and next Indicators , It also has... Pointing to the front node prev Indicators . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160549821-1525760646.png) If the array is stored in memory in a sequential way , Then the storage method of concatenation in memory is random storage . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160557488-248927271.png) ## Stacks and queues ** Stack **（stack） It's a linear data structure , It's like a cylindrical container in the table tennis ball shown above , The elements in the stack can only be put in first and then out （First In Last Out, Abbreviation FILO）. The earliest entry to the location of the element storage is called the stack bottom （bottom）, The last entry element is stored at the top of the stack （top）. Stack this data structure can be implemented by array , You can also use concatenation to achieve . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160605274-1145152888.png) ** Waiting for **（queue） It's a linear data structure , Its characteristics are similar to those of a one-way tunnel . Different from the first in and then out of the stack , Elements in the queue can only be FIFO （First In First Out, Abbreviation FIFO）. The exit end of the queue is called the team leader （front）, The entry end of a queue is called the tail of the queue （rear）. ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160612717-686040122.png) ## Hash table Hash tables are also called hash tables （hash table）, This data structure provides the key （Key） And the value （Value） The mapping of . Just give one Key, It can efficiently query the matching Value, The time complexity is close to O(1). ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160620602-723968889.png) Because the length of the array is finite , When inserted Entry More and more , Different Key It is possible that the subscript obtained by the hash function is the same . This is the case , It's called a hash conflict . There are two main ways to solve hash conflicts , One is ** Open addressing **, One is ** Concatenation **. The principle of open addressing is very simple , When a Key When the corresponding array subscript is occupied by hash function , We can “ Look for another job ”, Look for the next neutral position . This is the basic idea of open addressing . Of course , In the case of a hash conflict , There are many ways to address , It doesn't have to be simply looking for the next element of the current element , Here is just a simple example . stay Java in ,ThreadLocal The open addressing method is used . Next , Focus on another way to solve the hash conflict ——** Concatenation **. This method has been applied to Java The collection class of HashMap Among them . HashMap Every element of the array is more than just one Entry thing , It's also a header node that connects columns . Every one of them Entry The object passes through next The indicator points to its next Entry Node . When the new comer Entry When mapping to a conflicting array position , Just insert it into the corresponding link string . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160629184-1546296876.png) ## Tree Trees and graphs are typical nonlinear data structures , Let's first talk about the knowledge of trees . Tree （tree） yes n（n≥0） A finite set of nodes . When n=0 When , It's called an empty tree . In any non empty tree , It has the following characteristics . 1. There is and only one specific node called the root . 2. When n>1 When , The rest of the nodes can be divided into m（m>0） A finite set of disjoint sets , Each set itself is a tree , And called the subtree of the root . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160637110-1786160888.png) ### Binary tree ** Binary tree **（binary tree） It's a special form of tree . binary , As the name suggests , Each node of this tree has at most 2 A child node . Be careful , There are at most 2 One , Maybe it's just 1 One , Or no child nodes . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160644730-1465014156.png) Two child nodes of a binary tree node , One is called the left child （left chi ld）, One is called the right child （right chi ld）. The order of the two child nodes is fixed , It's like a person's left hand is his left hand , Right hand is right hand , Cannot be reversed or confused . Besides , There are two special forms of binary trees , One is called ** Full of binary trees **, The other is called ** A complete binary tree **. ** Binary tree storage structure ** 1. Chain storage structure . 2. Array . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160652942-1883413147.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160701431-1476191012.png) ## Summary ** What is an array ** An array is an ordered set of variables of the same type , Its physical storage is sequential storage , The access method is random access . The time complexity of using subscript to query array elements is O(1), Insert in the middle 、 The time complexity of deleting array elements is O(n). ** What is concatenation ** A linked column is a chained data structure , It consists of several nodes , Each node contains indicators pointing to the next node . The physical storage of linked serial columns is random storage , The access method is sequential access . The time complexity of querying the link serial node is O(n), Insert in the middle 、 The time complexity of deleting nodes is O(1). ** What is a stack ** A stack is a linear logical structure , It can be implemented with arrays , It can also be implemented by concatenation . Stack includes stack in and out operations , Follow the principle of first in, then out （FILO）. ** What is a queue ** Queuing is also a linear logical structure , It can be implemented with arrays , It can also be implemented by concatenation . Queues include queueing and dequeueing operations , Follow the first in, first out principle （FIFO）. ** What is a hash table ** Hash tables are also called hash tables , It's storage Key-Value The set of antiphones . To some one Key, Hash table can be close to O(1) Read and write operations within the time of . Hash tables are implemented by hash functions Key And array subscript conversion , Hash conflicts are resolved by open addressing and concatenation . ** What is a tree ** The tree is n A finite set of nodes , There is and only one specific node called the root . When n>1 When , The rest of the nodes can be divided into m A finite set of disjoint sets , Each set itself is a tree , And called the subtree of the root . ** What is a binary tree ** Binary tree is a special form of tree , Each node has up to two child nodes . Binary tree contains two special forms: complete binary tree and full binary tree . ** There are several ways to traverse a binary tree ** According to the relationship between traversal nodes , It can be divided into preorder traversal 、 Middle order traversal 、 Postorder traversal 、 Sequence traverses this 4 In a way ; From the perspective of a more macro view , It can be divided into depth first traversal and breadth first traversal . ** What is a fork pile ** Binary pile is a special complete binary tree , It is divided into the largest heap and the smallest heap . In the largest pile , The value of any parent node , Both greater than or equal to its left 、 The value of the right child node . In the smallest pile , The value of any parent node , Less than or equal to its left 、 The value of the right child node . ** What is priority queuing ** Priority queue is divided into maximum priority queue and minimum priority queue . In the maximum priority queue , No matter what the order , The biggest elements at the moment will take precedence out of the team , This is based on the maximum heap . In the minimum priority queue , No matter what the order , The smallest element at the moment will take precedence , This is based on the minimum heap . # Sorting algorithm ## Bubble sorting Bubble sort bubble sort, It's a basic sort of exchange sort . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160714432-2145324432.png) According to the idea of sorting bubbles , We're going to compare the adjacent elements in pairs , When an element is larger than the adjacent element on the right , Exchange their positions ; When an element is less than or equal to an adjacent element on the right , The position doesn't change . The sorting process is as follows ![](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) Dear Jane , All the elements are in order , This is the whole idea of bubble sorting . ** Bubble sort is a kind of stable sort , Elements with equal values do not upset the original order . Since every round of the sorting algorithm has to traverse all the elements , Total traversal （ Number of elements -1） Wheel , So the average time complexity is O(n2).** ## Quick sort Just like bubble sorting **, Quicksort also belongs to exchange sort **, By comparing and exchanging positions between elements to achieve the purpose of sorting . The difference is , Bubble sorting puts only... In each round 1 Elements bubble to one end of the sequence , Quicksort selects a benchmark element in each round , And let the other elements larger than it move to the side of the sequence , The smaller element moves to the other side of the sequence , So we can break the sequence into two parts . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160747967-699865314.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160755145-1467755809.png) Under the idea of divide and conquer , The original sequence is split into two parts in each round , Each part is split into two parts in the next round , Until it can't be divided again . Every round of comparison and exchange , You need to traverse all the elements of the array , Time complexity is O(n). How many rounds of traversal do you need ？ If the number of elements is n, So on average, you need logn Wheel , Therefore, the overall average time complexity of the Quicksort algorithm is O(nlogn). ## Heap sort The steps of the heap sort algorithm . 1. Building an unordered array into a binary heap . 2. Loop around to delete the heap top elements , And move the element to the end of the collection , Adjust the heap to produce a new top . The first 1 Step , Building an unordered array into a binary heap , The time complexity of this step is O(n). The first 2 Step , It needs to be done n-1 The second loop . One call at a time downAdjust Method , So the first 2 The calculation scale of step is (n-1)×logn , Time complexity is O(nlogn). The two steps are juxtaposed , So the overall time complexity is 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) ## Count sort and bucket sort ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160852979-1182785436.png) ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160900692-580985226.png) Let's take a look at how bucket sorting works . The number of buckets is 1 Step , It's about building these buckets , And determine the interval range of each bucket . ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160908160-1655159688.png) ## Summary ![](https://img2020.cnblogs.com/blog/874710/202011/874710-20201106160916021-14027729

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