# algorithm **Repository Path**: dr_dark/algorithm ## Basic Information - **Project Name**: algorithm - **Description**: 算法学习 - **Primary Language**: Java - **License**: MulanPSL-1.0 - **Default Branch**: dev - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 2 - **Forks**: 0 - **Created**: 2020-06-08 - **Last Updated**: 2021-06-29 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # algorithm #### 介绍 算法学习(algorithm studying) #### 软件架构 仅为java项目，j2ee,个人学习使用，如有问题，请指出 #### 安装教程 1. 使用git直接拉取dev分支即可： git clone https://gitee.com/dr_dark/algorithm.git --origin dev 2. 使用git直接拉取dev分支即可： git clone https://github.com/dlq123/algorithm.git --origin dev #### 项目说明 1. dichotomy项目:二分法查找 ```` 二分法查找背景：当数组或者集合数据量很大的时候，想要定位某一个元素，或者查询某一个元素是否存在的时候， 常用的方法是使用使用循环的方式，遍历每一个元素，直到查询到所需元素位置，这样的方式查询效率非常低 这个时候，就需要二分法查找' 二分法查找时间复杂度：O(log n)==(log n即是log2 n),也称对数时间 算法问题： //第一种： int mid = (low + high) / 2; //第二种 int mid = low + (high - low)/2; 看着没啥区别，但是第一种存在在极端情况下，(low + high)存在着溢出的风险，进而得到错误的mid结果，导致程序错误。 但是第二种能够保证计算出来的mid，一定大于low，小于high，不存在溢出的问题。 缺点：首先，数组一定要排序，无序的话不能使用二分法，使用二叉树进行操作，其次只能使用在数组上，不能使用在链表中， 数组在查找的时候时间复杂度是O(1)，但是在删除和修改的时间复杂度是O(n)，所以在排序的时候，就要花费大量的时间。降低效率 时间复杂度算法计算规则 ```` ```` 这里使用循环和递归方式查询，在使用递归的时候，注意它的基线条件(终止循环的条件)和递归条件(继续调自己的条件) ```` ``` 但是二分法的缺点：原始数据必须有序的 ``` 2. quicksort项目:快速排序（快排） ``` 介绍： 快速排序由在1962年提出。 它的基本思想是：从选择一个数(基值)，通过一趟排序将要排序的数据分割成独立的两部分， 其中一边(一部分)都大于这个数(基值)，另一边都小于这个数(基值),然后将按照形同的方式(分别两边都再次选择一个基值)，对独立的两部分进行排序， 以次方式进行递归，最后达到整个数据变成一个有序的序列 ``` ``` 第一趟：： start 0, end 7 选择一个基值 arr[arr.length-1]即最后一个元素作为基值 第一次就要遍历成结果就要变成，一遍全部比基值大，一遍全部比基值小 基值 arr[arr.length-1] = 5 初始数组:{16,2,1,11,19,3,3,5} 第一趟 <-->:比较，满足条件并且兑换位置 5 <--> 16 {5,2,1,11,19,3,3,16} 5 <--> 3 {3,2,1,11,19,3,5,16} 5 <--> 2 {3,2,1,11,19,3,5,16} 5 <--> 1 {3,2,1,11,19,3,5,16} 5 <--> 11 {3,2,1,5,19,3,11,16} 5 <--> 3 {3,2,1,3,19,5,11,16} 5 <--> 19 {3,2,1,3,5,19,11,16} 此时 5 的索引位置为 arr[index] = 5 index = 4 第一趟排序完毕，以 5 为节点，左边所有小于5 右边所有大于5 第二趟 以 5 为分界点，两边，同时进行 左边的索引范围 0 - index-1 , 有变边的索引范围 index+1 arr.length-1 第二趟 初始数组 : {3,2,1,3,5,19,11,16} 第一趟排序完毕，第二趟以 5 为节点，左边所有小于5 右边所有大于5，左右两边以 第一趟的规则继续拆分下去 ``` ``` 快排以 "快" 著称，因为它同时能对数组的左右两边同时进行排序，互不影响，但是快排是一种不稳定的排序，其实 O(nlog n) 只是它的平均时间复杂度， 不是每一个通过快排排序的数组的时间复杂度是O(nlog n)，它最坏的时候时间复杂度为O(n*n) 注意：快排时间复杂度为O(n*n)情况 我们将每次排好序的两边分成A边，B边 ，当A边一直为空的时候，B边是一直有满元素(所有元素),这种情况，一直是B边在排序，而A边其实没有做任何排序工作，此时的时间复杂度是O(n*n), 这样的数组如：已经排好序的数组、数组一样的(如{1,1,1,1,1})等 ``` 3. hash-table项目--简单实现一个hash表也叫散列表---hashMap ``` 什么是hash表,hash表有键和值组成， 通过键(key)直接访问在内存存储的值(value)的数据结构, 换句话说通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度, 这个映射函数称做散列函数,存放记录的数组称做散列表,键(key)可以说是索引值index,表示在内存的地址，值(value)表示索引index地址的存储其中的数据 通过一个索引值,直接返回一个数，达到时间复杂度为O(1)的效果. hash表的内部几大特点： (1).实现:进行存(put)与取(get)的，还包括扩容(resize)等多种功能的实现 (2)冲突: 给两个不同值，分配相同的位置(通过不同的key,hash函数计算出相同的hash值--索引值) 1)我们理想情况下, 比如,抽屉放苹果,有多少苹果就有多少抽屉,如有9个苹果,有9个抽屉, 但是现实是只有9个抽屉，有10个的苹果,所以必然有一个抽屉要放2个苹果，这就是著名的抽屉原理。 对于散列表而言，无论设置的存储区域（n）有多大，当需要存储的数据大于 n 时，那么必然会存在哈希值相同的情况。这就是所谓的散列冲突 2) 常用的散列冲突解决方法有两类,链表法（chaining），jdk1.8中hashmap就有这个， 其他还有开放寻址法、线性探测方法（Linear Probing）、二次探测（Quadratic probing）和 双重散列（Double hashing）等 3) 如何尽量避免冲突: 良好的散列函数：当数据量存储大的时候,可能也存在许多冲突 较低的装填因子(负载因子)：负载因子= (3)hash函数： 1) hash表中最主要的就是hash函数，顾名思义就是一个函数,假设hash函数的hash(key),通过key，经过hash(key)散列函数进过计算得到一个散列值。 2) hash函数是这样的，无论你给它什么数据，它返回你一个数字， 其特点是:必须一致性.同样的输入，映射到相同的索引,输入apple 返回 4,那么每次输入apple都要返回4; 它应将不同的输入映射到不同的索引(这样要和冲突区别是,冲突传入的值不一样,只不过最后计算的值一样的); 散列函数知道数组有多大，只返回有效的索引.如数组有5个元素，散列函数就不会返回无效索引100； ``` 4. bfs项目---广度优先搜索(bfs)实现 ``` 它的思想是： 1.从图中某个节点A出发，在访问了A之后接着依次访问A的各个未曾访问过的邻接点， 2.然后分别从A的邻接点出发依次访问A邻节点的邻接点，这里一定要先访问最近的邻节点，然后由进到远依次访问，直至图中所有已被访问的顶点的邻接点都被访问到 3.以次重复上面的操作，遍历所有节点. 在图列2中，我们以A节点作为出发点(以单个放心为例) A的邻节点是B和C B的邻节点是D C的邻节点是D和F D的邻节点是F和G F的邻节点是D和G 可以说 B和C是A一度关系,D和F是A的二度关系,G是A的三度关系,如果还有更多的节点,依次往后进行推如xxx度 要明确遍历是一度关系胜过二度,二度胜过三度,依次类推 我们总结上面的思想就是： 搜索的时候从A点开始，逐渐向外延伸,即先遍历第一度的关系,然后在在遍历二度关系,然后三度,四度.....依次进行遍历 广度搜索不仅仅查找A到某个点路径,而且是找到最短的路径(不是时间最短/消费最短路径) 在进行广度搜索的时候,要注意 1 在添加节点的时候，一定按顺序进行存放, A [ C,B] B [D] C[D F] D[G] F[G] 整合在一起就是 ============>遍历的顺序,先B [G G F D D C B](重复元素因为B中有D ,C中D) 要有这个顺序,且遍历一个就是丢失一个元素的数据结构可以用队列(Queue) 使用Queue存储,使用poll遍历取出元素 2 访问过的元素一定要做标记,存储起来,以防止死循环,(这边在无向图中突显很明确) 假如如图例3(可能举例不准确) (其实可以说无向图就会造成,因为上述我已经将图例2设置成一个有向图) D 和 A 有一条关系 , A是D的领节点 A是D的邻节点,如果不进行标记, A 遍历完 B和C 遍历B后,遍历B的邻节点D 发现A ,然后遍历A,遍历A的邻节点B和C A 又遍历完 B和C 遍历B后,遍历B的邻节点D 发现邻节点A ,然后遍历A,遍历A的邻节点B和C . . . . . 无限循环 所以,一定要进行标记并且存储，在遍历的时候检查是否遍历过这个元素.已经遍历过的就不在遍历 ``` ```angular2html 广度优先搜索时间复杂度: O(V+E) V表示节点数,E表示边数 ``` #### 参与贡献 1. Fork 本仓库 2. 新建 Feat_xxx 分支 3. 提交代码 4. 新建 Pull Request 5. 如需转载，请附上原地址和作者，谢谢。 ****