介绍

算法其实是个很宽泛的概念。不要被 “算法” 吓住，虽然看起来复杂，但只要方法得当，搞清原理，就跟编程一样，再复杂的见招拆招一步一步搞。

话说国内的教研书写得跟个屎一样，看都看不懂，整得很高大上，还是那句话。个人觉得只要真正懂了，写的东西才会让人迎刃而解，不是什么名词一大堆。

《程序员小灰》：学习算法，我们不需要死记硬背那些冗长复杂的背景知识，底层原理，指令语法……需要做的是领悟算法思想，理解算法对内存空间和性能的影响，以及开动脑筋去寻求解决问题的最佳方案。

跟着我这小脑袋瓜一起走进算法的大门=-=

算法（概念）（初中数学就有了）

算法对应的英文单词是 algorithm；
1+2+3+4+……一直加到 1000 的结果。

1 + 10000 = 10001
2 + 9999 = 10001
3 + 9998 = 10001
4 + 9997 = 10001

一共有多少组这样的结果相同的和呢？
10000 / 2 即 5000组
（1 + 10000） x 10 000 / 2 = 50005000
这种等差数列求和的方法，被称为 高斯算法。
这是数学领域中算法的一个简单示例。在数学领域，算法是用于解决某一类问题的公式和思想。

算法有简单的，也有复杂的

给出一组整数，找出最大的数。
复杂的算法，诸如在多种物品里选择装入背包的物品，使背包里的物品总价值最大。，或找出从一个城市到另一个城市的最短路线。
在计算机领域，我们同样会遇到各种高效和拙劣的算法。衡量算法好坏的重要标准有两个。

• 时间复杂度
• 空间复杂度

1. 运算
   计算两个超大整数的和，按照正常方式来计算肯定会导致变量溢出。
2. 查找
   当谷歌搜素一个词，或数据库执行某SQL语句时，您有没有思考数据和信息是如何被查出来的？
3. 排序
   排序算法是实现诸多复杂程序的基石。例如，当浏览电商网站，商品价格从低到高进行排序，学生管理网站，学生资料按照学号大小进行排序。
4. 最优决策
   在游戏中，可以让 AI 角色找到迷宫的最佳路线，这涉及A星寻路算法。

数据结构

《程序员小灰》：数据结构是算法的基石。如果把算法比喻成美丽灵动的舞者，那么数据结构就是舞者脚下广阔而坚实的舞台。
数据结构，对应的英单词是 data structure ,是数据的组织，管理，和存储格式，其使用的目的是为了高效地访问和修改数据。

数据结构有哪些组成方式呢

1. 线性结构
   线性结构是最简单的数据结构，包括数组，链表，以及由它们衍生出来的栈，队列，哈希表等。
2. 树
   树是相对复杂的数据结构，其中比较有代表性的是二叉树，由它又衍生出了二叉堆之类的数据结构。
3. 图
   图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。
4. 其他数据结构
   还有很多千齐百怪的数据结构。它们由基本数据结构变形而来，用于解决某些特定问题，如跳表，哈希链表，位图等。

有了数据结构这个舞台，算法才可以尽情舞蹈。在解决问题时，不同的算法会选用不同的数据结构。例如排序算法中的堆排序，利用的就是二叉堆这种一种数据结构；

时间复杂度

1. 运行时间长
2. 占用空间大

对程序基本操作执行次数的统计

个人觉得算法跟代码结合在一起，我们应该多刷点算法题。

n个整数，其中有两个整数是重复的，要求找出这两个重复的整数。

let arr = [1,3,3,4,5,2];

for(let i = 0;i<arr.length;i++){
    for(let y = 0;y<i;y++){
         if(arr[i] ==arr[y]){
             console.log(arr[i])
         }
    }
}

双重循环虽然可以得到最终结果，但它显然并不是一个好的算法。

递归空间

递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合，但是计算机在执行程序时，会专门分配一块内存，用来存储 “方法调用栈”。

“方法调用栈” 包括进展和出栈两个行为。

当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。

当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出。

void fun4(int n){
    if(n<=1){
      return;
}
fun4(n-1);
}

假如初始传入参数值 n=5，那么方法fun4（参数n=5）的调用信息先入栈

接下来递归调用相同的方法，方法fun4（参数n=4）的调用信息入栈

以此内推

当 n = 1，时，达到递归结束条件时，执行 return 指令，方法出栈。

最终，“方法调用栈”的全部元素会–出栈。

数据结构

• array

  是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。

  数组是最为简单，最为常用的数据结构

  数组的另一个特定，是在内存中顺序存储，因此可以很好地实现逻辑上的顺序表。

  数组是由一个个连续的内存单元组成的，每一个内存单元都有自己的地址。在这些内存中，有些被其他数据占用了，有些是空闲的。

  数组中的每一个元素，都存储在小小的内存单元中，并且元素之间紧密排列，既不能打乱元素的存储顺序，也不能跳过某个存储单元进行存储。

插入数组元素的操作存在三种情况。

1. 尾部插入

2. 中间插入

3. 超范围插入

中间插入，稍微复杂一些，由于数组每一个元都有其固定下标，所以不得不首先插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。

let arr = [1,2,3,4,5,6,7,8];
function indexof(index,a){
  for(let i=arr.length-1;i>=index;i--){
  arr[i+1] = arr[i]
}
  arr[index] = a
}

indexof(5,99)

可是，如果数组不断插入新的元素，元素数量超过了数组的最大长度，数组岂不是要 ”撑腰“ 了？

超范围插入

超范围插入，假如现在有一个长度为 6 的数组，已经装满了元素，这时还想插入一个新元素

数组扩容

创建一个新数组，长度是旧数组的2倍，再把旧数组中的元素统统复制过去，这样就实现了数组的扩容。

数组的优势和劣势

优势

数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。有一种高效查找元素的算法叫作二分查找，就是利用了数组的这个优势。

劣势

至于数组的劣势，体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入，删除元素都会导致大量元素被迫移动，影响效率。

数组适合 读操作多，写操作少

链表

如果说数组是纪律严明的 “正规军” 。那么链表就是灵活多变的 “地下党”

链表是一种在物理上非连续，非顺序的数据结构，由若干节点（node）所组成。

单向 链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next

private static class Node{
    int data;
    Node next;
}

链表的第一个节点被称为头节点，最后一个节点被称为尾节点；尾节点的next指针执行空。

于数组按照下标来随机寻找元素不同，对于链表的其中一个节点A，我们只能根据节点A的next指针来找到该节点的下一个节点B，再根据节点B的next指针找到下一个节点C

双向链表，双向链表，它的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。

如果说数组在内存中的存储方式，那么链表在内存中的存储方式则是随机存储

什么叫随机存储呢？

链表采用了见缝插针的方式，链表的每一个节点分别在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用离散的碎片空间。

链表基本操作

1. 查找节点

链表不像数组那样那样可以通过下标快速进行定位，只能从头节点开始向后一个一个节点琢一查找。

例如给出一个链表，需要查找从头节点开始的第三个节点。

1. 将查找的指针定位到头节点。

2. 根据头节点的next指针，定位到第二个节点。

3. 根据第二个节点的next指针，定位到第三个节点，查找完毕。

4. 更新节点

如果不考虑查找节点的过程，链表的更新过程会像数组那么简单，直接把旧数据替换成新数据即可。

插入节点

• 尾巴插入

• 头部插入

• 中间插入

尾巴插入，是最简单的情况，把最后一个节点的 next 指针指向新插入的节点即可。

头部插入，可以分成两个步骤。

1. 第一步，把新节点的 next 指针指向原先的头节点。

2. 第二步，把新节点变为链表的头节点

中间插入，同样分为两个步骤。

1. 新节点的 next 指针，指向插入位置的节点

2. 插入位置前置节点的next指针，指向新节点

只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题。

删除元素

1. 尾部删除

2. 头部删除

3. 中间删除

尾巴删除，是最简单的情况，把倒数第2个节点的next指针指向空即可。

头部删除，也很简单，把链表的头节点设为原先头节点的next指针即可。

中间删除，同样很简单，把要删除节点的前置节点的 next 指针，指向要删除元素的下一个节点即可。

高级语言，如 java，拥有自动化的垃圾回收机制，所以我们不用刻意去释放被删除的节点，只要没有外包引用指向它们，被删除的节点会被自动回收。

数组VS链表

数组在于能够快速定位元素，对于读操作多，多操作少的场景来说，用数组更合适一些。

链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入，删除元素，用链表更合适一些呢

物理结构和逻辑结果

常用的数据结构有很多，但大多数都以数组或链表作为存储方式，数组和链表可以被看作数据储存的 “物理结构”。

常用数据结构：栈和队列。这两者都属于逻辑结构，它们的物理实现既可以利用数组，也可以利用链表来完成。

逻辑结构是抽象的概念，它依赖于物理结构而存在。

栈

栈（stack）是一种线性数据结构，栈中的元素只能先入后出。

最早进入的元素存放的位置叫作栈底，最后进入的元素存放的位置叫栈顶

栈这种数据结构既可以用数组来实现，也可以用链表来实现。

队列

队列(queue)是一种线性数据结构，它的特征和行驶车辆的单行隧道很相似，不同栈的先入后出，队列中的元素只能先入先出。队列的出口端叫作队头，队列的入口端叫作队尾。（数组循环队列）不但充分利用数组空间，还避免数组元素整体移动的麻烦。

栈和队列的应用

1. 栈的应用

递归逻辑，就可以用栈代替，因为栈可以回溯方法的调用链。

面包屑导航

2. 队列

网络爬虫实现网站抓取

双端队列

先入先出，先入后出

优先队列

谁优先级高，谁先出队。（不是线性结构是二叉堆）