JS数据结构与算法学习笔记大全（温故而知新，可以为师矣。）

傷城~ 2023-01-19 04:33 31阅读 0赞

### 目录： ###

*   *  一.数据结构简介（序）：
     *   *   *  1.1 概念
             *  1.2 概念
             *  1.3 分类
             *  1.4 作用
             *  1.5 结构
             *  1.6 常见的数据结构
     *  二.算法简介（序）：
     *   *   *  2.1 概念
             *  2.2 JS数组
     *  三.栈与队列：
     *   *   *  3.1简介
             *   *  3.1.1 js实现一个栈：
             *  3.2 清空数组的几种方法（扩展）：
             *  3.3 js调用栈
             *  3.4 递归
             *  3.5 队列
             *   *  3.5.1 js简单实现一个队列：
             *  3.6 js异步队列
     *  四.链表：
     *   *   *  4.1 概念
             *  4.2 js实现一个大致的单向链表：
             *  4.3 js原型链
             *   *  4.3.1 原型链实现继承：
     *  五.哈希表：
     *   *   *  5.1概念
             *  5.2 js实现一个简单哈希表：
             *  5.3 处理冲突
     *  六.树：
     *   *   *  6.1 概念
             *  6.2 树的存储结构
             *  6.3 二叉树
             *  6.4 二叉搜索树
             *  6.5 js实现二叉搜索树基本结构
             *  6.6 遍历
             *   *  6.6.1 先序遍历
                 *   *  6.6.1.1 js实现先序遍历：
                 *  6.2 中序遍历
                 *   *  6.2.1 js实现中序遍历
                 *  6.3 后序遍历：
                 *   *  6.3.1 js实现后序遍历
             *  6.7 完善6.5js实现二叉搜索树的基本结构
             *   *  6.7.1 添加输出最大值的方法：
                 *  6.7.2 添加输出最小值方法
                 *  6.7.3 查找看是否有特定的值
             *  6.8 二叉搜索树删除结点
             *   *  6.8.1 结点没有子树
                 *  6.8.1 结点有一个子树
                 *  6.8.1 结点有两个子树
             *  6.9 二叉搜索树总结
             *  6.10 二叉平衡树\*
             *  6.11 红黑树\*
     *  七.图：
     *   *   *  7.1 基本概念
             *  7.2 js实现一个简单的图结构
             *  7.3 图的遍历
             *   *  7.3.1 \*\*js实现广度优先遍历：\*\*
                 *  7.3.2 js实现深度优先遍历
             *  7.4 最短路径问题
     *  八.算法复杂度：
     *   *   *  8.1 基本概念
             *  8.2 时间维度
             *  8.3 空间维度
     *  九.排序算法
     *   *   *  9.1冒泡排序
             *  9.2选择排序
             *  9.3插入排序
     *  未完结，先发出来，每天都会更新一点！每天都会更新一点！每天都会更新一点！重要的话说三遍~~~来关注一起相互探讨打卡学习⑧~

## 一.数据结构简介（序）： ##

#### 1.1 概念 ####

程序设计 = 数据结构 + 算法。

#### 1.2 概念 ####

数据 = 符号  
(1). 其可以输入到计算机中。  
(2). 能够被计算机识别和处理。

#### 1.3 分类 ####

**数据分为：**  
(1).数据元素：数据的基本单位，也称为结点或者记录。  
(2).数据对象: 相同特性的数据元素的集合，是数据的一个子集。  
(3).数据项: 独立含义的数据的最小单位。

数据的目的是存储，存储的目的是后期的再利用。

#### 1.4 作用 ####

数据结构的主要作用是:阐述关系。  
如何存储具有复杂关系的数据更有助于后期对数据的再利用。

#### 1.5 结构 ####

**结构:**  
简单的理解就是关系，不同的数据元素之间不是独立的。而是存在特定的关系。  
**(1). 逻辑结构:**  
数据对象中数据元素之间的互相关系。  
**四种:**  
集合结构、线性结构、树形结构、图形结构.

**集合结构**: 数据元素同属于个集合， 他们之间没有其他的关系。他们的共同属性是:“同属于一个集合”。  
![在这里插入图片描述][20210507201930377.png_pic_center]

**线性结构:** 最典型的数据关系是一对一。线性结构是种有序数据的集合。除了第一个和最后一个数据元素之外，其他数据元素都是首尾相接的。  
1.必存在一个第一个元素。  
2.必存在最后的一个元素。  
3.除最后一个元素外，其他的数据元素均有一个唯一的后续”。  
4.除第一个元素之外，其他数据元素均有一个唯一的前驱。  
比如：数组， 栈，队列，等都是一个线性结构。  
![在这里插入图片描述][20210507202522197.png_pic_center]  
**树形结构**：数据元素一对多的关系。如 Dom Tree。  
![在这里插入图片描述][20210507202800108.png_pic_center]  
**图形结构**：多对多的关系。如 地图。  
![在这里插入图片描述][2021050720324358.png_pic_center]  
**（2）.物理结构：** 数据元素存储到计算中的存储器（内存）。数据的存储结构应该正确的反应数据元素之间的逻辑关系。包括顺序存储和链式存储。

**顺序存储：** 该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。  
![在这里插入图片描述][20210507204131267.png_pic_center]  
**链式存储：** 在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center]

#### 1.6 常见的数据结构 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 1]

## 二.算法简介（序）： ##

#### 2.1 概念 ####

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。简单来说，**算法是解决问题的方法和步骤**。数据结构的实现离不开算法。

#### 2.2 JS数组 ####

**声明**： JS数组不是真正意义上的数组。

传统数组是在内存中用一串连续的区域存放具有相同类型的元素。

但是，如一个js数组如下：

const arr = [123,'a',"啦啦"];

可以看出 JS 数组元素是可以任意类型的，内存地址是不连续的。所以它不是真正意义上的数组。但是它好用呀。

数组的优点：  
（1）按照索引查询元素速度快；  
（2）能存储大量数据；  
（3）按照索引遍历数组方便；  
（4）定义简单，而且访问灵活；

数组的缺点：  
（1）根据内容查找元素速度很慢；  
（2）数组的大小一经确定不能改变，不适合动态存储；  
（3）数组只能存储一种类型的数据；  
（4）增加、删除元素效率慢；  
（5）未封装任何方法，所有操作都需要用户自己定义；

## 三.栈与队列： ##

#### 3.1简介 ####

（1）内存中的堆栈和数据结构中的堆栈不是一个概念， 内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象数据存储结构。

（2）栈又名堆栈，它是一种运算受限的线性表。它遵循**后进先出**（LIFO）原则。

（3）受限制意思就是在新增数据、删除数据、查找等操作时，不能随心所欲，必须遵循一定的限制(规则)。  
（4）向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素。  
（5）从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为  
新的栈顶元素

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 2]

##### 3.1.1 js实现一个栈： #####

//定义一个类，相当函数
    class Stack{ 
        // 构造方法
        constructor(){ 
           this.items = [];
        }
        //添加方法，入栈顶
        push(ele){ 
            this.items.push(ele);
        }
        //出栈
        pop(){ 
            //pop() 方法用于删除并返回数组的最后一个元素。
            return this.items.pop();
        }
        //返回栈顶元素
        peek(){ 
            return this.items[this.items.length-1];
        }
        //判断是否为空
        isEmpty(){ 
            return this.items.length===0;
        }
        //返回元素个数
        size(){ 
            return this.items.length()
        }
        //清空
        clear(){ 
            this.items = [];
        }
    }

#### 3.2 清空数组的几种方法（扩展）： ####

let arr = [1,2,3];

arr.length = 0;

arr = [];

arr.splice(0,arr.length);

#### 3.3 js调用栈 ####

**执行上下文：** 就是当前JavaScript代码被解析和执行是所在环境的抽象概念，JavaScript中运行任何的代码都是在执行上下文中运行。（执行环境）。分为以下三种：

（1） **全局执行上下文：** 默认的，最基础的执行上下文。共两个过程：1.创建全局对象，在浏览器中这个全局对象就是window对象。2.将this指针指向这个全局对象。  
（2）**函数执行上下文：** 每次调用函数时，都会为该函数创建一个新的执行上下文。每个函数都拥有自己的执行上下文，但是只有在函数被调用的时候才会被创建。  
（3）**Eval函数执行上下文：** eval() 函数可计算某个字符串，并执行其中的的 JavaScript 代码。运行在eval函数中的代码也获得了自己的执行上下文。

**执行栈：** 执行栈，也叫调用栈，遵循LIFO原则。用于存储在代码执行期间创建的所有执行上下文。如下代码：

const one = ()=>{ 
               two();
               console.log('I am one');
           }
           const two = () =>{ 
               console.log('I am two');
           }
           one();

结果：  
![在这里插入图片描述][20210511140330227.png_pic_center]  
  ·当上述代码在浏览器中加载时，JavaScript 引擎会创建一个全局执行上下文并且将它推入到当前的执行栈。  
 · 当调用 one函数时，JavaScript 引擎会为该函数创建了一个新的执行上下文并将其push推到当前执行栈的栈顶。  
 · 当在 one() 函数中调用 two() 函数时，Javascript 引擎为该函数创建了一个新的执行上下文并将其推到当前执行栈的栈顶。  
 · 当two() 函数执行完成后，它的执行上下文从当前执行栈中弹出。上下文控制权将移到当前执行栈的下一个执行上下文，即 one() 函数。

#### 3.4 递归 ####

从上可以知道，函数的调用的本质为压栈与出栈操作。  
 函数在调用栈里边有一个特例，叫做递归。  
 递归，就是在运行的过程中**调用自己**。会产生一个叫**递归栈**。  
 先进栈，到条件后就出栈。如果不出栈，由于递归调用次数过多，堆栈溢出。因为堆栈的大小是系统控制的，无法改变。

**递归例子，算阶乘：**

const factorial = (n) =>{ 
               //判断出口
               if(n===1){ 
                   return 1;
               }
               //递归
               return n*factorial(n-1);
           }
           //输出3阶乘
           console.log(factorial(3));

结果：  
![在这里插入图片描述][20210511150651657.png_pic_center]  
**递归例子，斐波那契数列：**

斐波那契数列指的是这样一个数列：  
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…  
第3项开始，每一项都等于前两项之和。  
现在求输入第几项后输出数列对应的数字：

const Fibonaqi = n=>{ 
               if(n<2){ 
                   return n;
               }
               return Fibonaqi(n-1)+Fibonaqi(n-2);
           }
           console.log(Fibonaqi(5));

这代码有个问题，会进行非常多重复的计算，需要同时保存多个调用帧，可能导致消耗内存，爆栈。假如 n 为 5 执行过程如下：

Fib(5)=Fib(4)+Fib(3) =5
    Fib(4)=Fib(3)+Fib(2) =3
    Fib(3)=Fib(2)+Fib(1) =2
    Fib(2)=Fib(1)+Fib(0) =1
    Fib(1)= 1
    Fib(0)= 0

可采用尾递归方式解决。首先理解概念：

**尾调用：** 尾调是在函数的执行过程中最后一个动作是一个函数的调用，即这个调用的返回值被当前函数直接返回。如下：

function g(x) {  }
    function f(x) {  
     return g(x)
    }

**尾递归：** 而尾递归指最后的尾调用位置上是这个函数本身。首先执行计算出一次的结果，然后执行递归调用，**将当前步骤的结果值传递给下一个递归步骤**。每次递归都不会增加调用栈的长度，只是更新当前的堆栈帧，只存在一个调用帧，避免了内存的消耗。

尾递归实现斐波那契数列：

int Fibonaqi(int n, int ret1, int ret2)  
    { 
          if (n ==0 )
          { 
          //结果
             return ret1;
         }
          else
        { 
             return Fib(n - 1, ret2, ret1 +ret2);
         }
     }

执行过程：

Fib (5, 0,1)=Fib (4, 1, 1)  =1
    Fib (4,1,1)=Fib (3, 1,2)  =1
    Fib (3, 1,2)=Fib (2,2, 3)  =2
    Fib (2,2,3)=Fib (1,3, 5)  =3
    Fib(1,3,5)=Fib (0,5, 8)  =5

![在这里插入图片描述][20210512141046345.png]  
尾递归的阶乘，这个好理解点：

int facttail(int n, int a)
    {   
        if (n < 0)
            return 0;    
        else if (n == 0)
            return 1;    
        else if (n == 1)
            return a;
        else
            return facttail(n - 1, n * a);
     
    }

#### 3.5 队列 ####

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。遵循 **FIFO**，先进先出。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。  
![在这里插入图片描述][20210512161926117.png_pic_center]

##### 3.5.1 js简单实现一个队列： #####

//定义一个类，实质也是一个函数
    class Queue{ 
      //定义一个构造方法
      constructor(){ 
          //实例对象
          this.items = [];
      }  
      //入队方法
      enqueue(ele){ 
        this.items.push(ele);
      }
      //出队方法
      dequeue(){ 
          //shift()方法可用于把数组的第一个元素从其中删除，并返回第一个元素的值。
         return this.items.shift();
      }
      //查看队首元素
      front(){ 
         return this.items[0];
      }
      //查看队尾
      rear(){ 
          return this.items[this.items.length-1];
      }
      //查看队尾是否为空
      isEmpty(){ 
          return this.items.length === 0;
      }
      //查看长度
      size(){ 
          return this.items.length;
      }
      //清空队列
      clear(){ 
          this.items = [];
      }
    }

使用看：

const queue = new Queue();
    queue.enqueue(2);
    queue.enqueue(5);
    queue.enqueue(5);
    console.log(queue);
    console.log(queue.size());

运行结果正确：  
![在这里插入图片描述][2021051216573059.png_pic_center]

#### 3.6 js异步队列 ####

>   首先JavaScript是单线程的，同一个时间只能做一件事。

>   为什么 JavaScript 是单线程 ？这主要和js的用途有关，js是作为浏览器的脚本语言，主要是实现用户与浏览器的交互，以及操作dom；这决定了它只能是单线程，否则会带来很复杂的同步问题。比如，假定JavaScript同时有两个线程，一个线程在某个 DOM 节点上添加内容，另一个线程删除了这个节点，这时浏览器就不知道以哪个线程为准。

>  为了利用多核 CPU 的计算能力，HTML5 提出 Web Worker 标准，允许 JavaScript  
> 脚本创建多个线程，但是子线程完全受主线程控制，且不得操作 DOM。所以，这个新标准并没有改变 JavaScript 单线程的本质。

>   单线程就意味着，所有任务需要排队，前一个任务结束，才会执行后一个任务。 如果前一个任务耗时很长，如发起一个请求， 网络很慢，那后面的那个任务是不是就要一直等着。这样就很不好，那肯定不可以呀，所以js这样解决。

>   如在I0的时候，(输入输出的时候) ,主线程不去管IO，挂起处于等待中的任务，先运行排在后面的任务，等待I0设备返回了结果，再回过头，把挂起等待的任务继续执行下去。

>   于是所有的任务可以分为: 同步任务，异步任务。

**同步任务:** 在主线程上排队执行的任务，只有前一个任务执行完毕以后，才能够去执行下一个任务。  
  **异步任务:** 不进入主线程，而是进入**任务队列**，（任务队列就是主线程维护的一个任务队列，保存着异步代码），只有任务队列通知主线程，某个异步任务可以执行了，这个任务才会进入主线程执行。

有下面的代码，说出输出顺序：

console.log(1);
    setTimeout(()=>{ 
      console.log(2);
    },60)
    setTimeout(()=>{ 
      console.log(3);
    },0)
    console.log(4);

答案如下：1,4,3,2  
![在这里插入图片描述][20210512201926826.png_pic_center]

1.  最先执行的是同步代码，执行完毕以后，立即出栈，让出主线程。
2.  同步代码执行完毕，立即出栈，此时主线程是处于空闲状态了。
3.  则此时主线程去读取**任务队列**，队列遵循的原则是先进先出。但是，有个条件，触发条件相等既优先级一样，会遵循先进先出。就是谁先进队列谁先出去主线程运行。但是如果触发条件不相同，则优先执行到达触发条件的代码先出去。明显等待0秒的优先级更高，主线程有空就立即执行。
4.  主线程执行完毕以后，从事件队列中去读取任务队列的过程，我们称之为事件循环。(Event Loop)

判断以下代码输出：

// 宏任务
    setTimeout(()=>{ 
        console.log('1');
    },0)
    // 同步任务
    const promise = new Promise((resolve,reject)=>{ 
        console.log('2');
        resolve();
    //微任务
    }).then(()=>{ 
        console.log('3');
    })

结果：  
![在这里插入图片描述][20210513105111790.png_pic_center]  
 **任务队列**里又存在着**宏任务队列**和**微任务队列**，执行完同步任务后，先执行微任务再执行宏任务。  
常见宏任务队列：lO、定时器、事件绑定、ajax …等  
常见微任务队列：Promise.then catch、 finally、 process.nextTick…等

## 四.链表： ##

#### 4.1 概念 ####

官方解释是：

>   链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。  
>   使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。

简单来说就是：

**链表：** 内存地址可以是连续的，也可以是不连续的。把数据元素存放在任意的存储单元里，指针来存放数据元素的地址。  
  **数组：** 大小是固定的，一经声明就要占用整块的连续的内存空间。如果说，声明的数组过大，系统可能没有足够的连续的内存空间用于分配，(out of memory)内存不足。如果声明的数组过小，当不够用时，又需要去重新一块更大的内存，还要数据拷贝。但是数组查找元素很快。

单向链表结构图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 3]  
**  链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成。**

> 总而言之：
> 
> 1.  插入和删除： 链表性能更好。
> 2.  查询和修改： 数组性能更好。

#### 4.2 js实现一个大致的单向链表： ####

// 结点的类
    class Node { 
        constructor(element){ 
            this.element = element;
            this.next = null;
        }
    }
    // 链表类
    class LinkedList { 
        constructor(){ 
            //有个链表头
            this.head = null;
            //链表长度
            this.length = 0;
        }
        // 实现在链表尾部追加元素
        append(element){ 
            //新建一个结点
            let node = new Node(element);
            //先看链表是不是空
            if(this.length===0){ 
                //为空这个结点就为表头
                this.head = node;
            }else{ 
                //变量,当前结点，通过从head开始遍历找到最后的结点
                let current = this.head;
                while(current.next){ 
                    current = current.next;
                }
                //循环结束，则current为最后一个结点
            //添加新结点
            current.next = node;
            }
            // 长度加1
            this.length+=1;
        }
        //获取链表头
        getHead(){ 
            return this.head;
        }
        //toString方法,就是输出链表内容
        toString(){ 
            let current = this.head;
            let linkString = '';
            //遍历链表，把每个结点内容用linkString拼接起来
            while(current.next){ 
                linkString+= ','+current.element;
                current = current.next;
            }
            //添加最后一个结点内容
            linkString+= ','+current.element;
            //返回内容
            return linkString.slice(1);
        }
        //插入在任意位置插入元素，element是内容，position是位置
        insert(element,position){ 
            //先判断位置是有效值
            if(position<0||position>this.length){ 
                return false;
            }
            // 以下是位置有效
            // 记录索引
            let index = 0;
            //当前结点
            let current = this.head;
            //上一个结点
            let previous = null;
            //创建元素
            let node = new Node(element);
            //判断插入是不是第一个
            if(position===0){ 
                node.next=this.head;
                this.head=node;
            }else{ 
                while(index<position){ 
                    //一直更新保存着上一个结点
                    previous = current;
                    current = current.next;
                    index++;
                }
                //插入结点,就是当前上一个结点指向改变为新增结点，新增结点指向原本的当前结点
                node.next = current;
                previous.next = node;
                //length++
                this.length+=1;
                return true;
            }
        }
        // 获取对应位置的元素
        get(position){ 
             //先判断位置是有效值
             if(position<0||position>this.length){ 
                return false;
            }
            //当前结点从头开始
            let current = this.head;
            let index = 0;
            //老样子遍历
            while(index<current.next){ 
               current = current.next;
               index++;
            }
            //返回该结点内容
            return current.element;
        }
        //删除结点
        removeAt(position){ 
             //先判断位置是有效值
             if(position<0||position>this.length){ 
                return false;
            }
             // 以下是位置有效
            // 记录索引
            let index = 0;
            //当前结点
            let current = this.head;
            //上一个结点
            let previous = null;
             //判断插入是不是第一个
             if(position===0){ 
                 //头结点变为第二个
                this.head = this.head.next;
            }else{ 
                while(index<position){ 
                    //一直更新保存着上一个结点
                    previous = current;
                    current = current.next;
                    index++;
                }
                //就是当前的上一个结点改为指向当前的下一个结点，没人指向当前结点了，相当删除
                previous.next =current.next;
                // length--
                this.length--;
                return current.element
            }
        }
    }

测试下：

const linkedList = new LinkedList();
    //添加1,2,3,4,
    linkedList.append(1);
    linkedList.append(2);
    linkedList.append(3);
    linkedList.append(4);
     //删除第二个
    linkedList.removeAt(2); 
    //输出长度
    console.log(linkedList.length);
    //输出内容
    console.log(linkedList.toString());
    
    console.log(linkedList);

结果没问题：  
![在这里插入图片描述][20210514011800384.png_pic_center]

#### 4.3 js原型链 ####

首先知道，JS是**基于对象**设计和开发出来的语言。而**面向对象**有三大特点: (封装、 继承于多态)。但是基于对象是使用对象，我们无法利用现有的对象模板去产生新的对象类型，继而去产生一个新的对象，也就是说基于对象是没有继承的特点。但是面向对象对象实现了继承和多态，基于现象是没有实现这些的。  
 oop面向对象的支持两种继承方式:接口继承、实现继承。  
 ECMAscript是无法去实现去接口继承的，JS只支持实现继承。实现继承主要依靠**原型链**去实现。

接下来简单介绍 **prototype** 和 **\_ \_ proto \_ \_** 。

1.  所有的引用类型(数组、函数、对象)可以自由的扩展属性(nul除外）。
2.  所有的引用类型都有一个\_ \_ proto \_ \_属性(隐式原型，其实就是一个普通的对象。
3.  所有的函数都有一个prototype 属性，(显式原型，它也是一个普通的对象)。
4.  所有的引用类型，它的\_ \_ proto \_ \_属性指向它的构造函数的prototype属性。
5.  当你试图得到一个对象的属性时，如果这个对象的本身不存在这个属性，那么就会去它的\_ \_ proto \_ \_属性中去寻找(去它的构造函数的protorype属性)中去寻找。

**当调用这个对象本身并不存在的属性或者是方法时，它会一层层地往上找，一直找到null为止，null表示空的对象\{ \}。**

##### 4.3.1 原型链实现继承： #####

//有一个构造函数
    function People(name,age){ 
        this.name = name;
        this.age = age;
        //它有一个say函数方法
        this.say = function(){ 
          console.log('哈哈哈，你也能用我啦~');
        }
    }
    
    // 空的构造方法
    function Xiaoming(){ }
    // 我想让Xiaoming也有People里面的say方法。
    // 利用原型链机制，让一个引用类型继承另一个引用类型的属性和方法
    Xiaoming.prototype = new People('小明',18);
    var xiaoming = new Xiaoming();
    xiaoming.say();
    //它会像链子一样一层一层往上找，直到找到null，找到null则无路可走了证明找到了

运行结果：  
![在这里插入图片描述][20210514133224105.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 4]

## 五.哈希表： ##

#### 5.1概念 ####

**哈希：**  
  hash，一般可以称为散列。其是把**任意长度的输入通过散列算法变换成固定长度的输出**，那么输出的值就是散列值。这种转换是一种压缩映射。 映射表达是一 一对应的关系， 也就是说，散列值的空间通常会小于输入的空间。而且注意的是，哈希算法不能从结果去推算出输入，也就是说哈希算法是不可逆的。既然哈希特性是不可逆，那么哈希算法是可以当作一种加密算法存在的。哈希算法可以运用在加密算法上。

众所周知，数组的查询效率很高，但是，有个前提，那就是按照索引进行查找效率才高，如果是按照内容查找的话效率还是比较低的。

如下：

//有一个数组
    const arr = [
        { name:'xiaoming',age:18},
        { name:'xiaobai',age:20}
    ]
    //直接从索引找xiaoming，速度快
    console.log(arr[0]);
    //按照内容找xiaoming，速度慢
    for(let i=0;i<arr.length;i++){ 
        if(arr[i].age===18){ 
            console.log(arr[i].name);
        }
    }

那有没有一种方法，能将名字**name**作为**索引**，来提高查找速度呢？就是将字符串作为数组的索引。当然，肯定有呀，那就是----**哈希表**。  
  哈希表通常是基于数组实现的，但是相对于数组，它有很多的优势。那就是它可以提供非常非常**快速**的插入、删除、查找等操作。其实哈希表的**结构**就是**数组**，但是它和数组的也有不一样的地方就是哈希表对于**索引**的一种**转换**。这种转换我们通常称之为**哈希函数**。

1.  一个单词如何转换为数字索引呢？  
      我们可以通过**ASCLL码**转换，每个字母都有一个对应的ASCLL码，我们可以通过把每个码相加的**和**作为其的数字索引。  
      如，有一个 name：xiao，那么xiao的ASCLL码和如下：

xiao = x + i + a + o = 120+105+97+111 = 433

那么，我们可以这样存：

arr[433] = { name:'xiao',age:20} ;

这样就可以通过索引快速查找。可以更好理解以下哈希表概念：

**哈希表：**

> 哈希表(Hash table) ，也叫散列表，是根据关键码值(Key value) 而直接进行访问的数据结构。

> 它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

> 这个起到映射作用的叫做散列函数(Hash Function) ,存放记录的数组叫做哈希表(或者散列表)。

> 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址。

发现一个问题，上面每个码相加的和作为其的数字索引的这个哈希函数得的结果会出现重复，比如 xiao 和 xioa 得到的关键码是一样的。总而来说就是对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为**冲突**，这个后面可能讲。

#### 5.2 js实现一个简单哈希表： ####

class HashTable{ 
        constructor(){ 
            // 用数组表示哈希表
            this.table = [];
        }
        // 哈希函数
        loseloseHashCode(key){ 
            let hash = 0;
            for(let i=0;i<key.length;i++){ 
                //计算unicode码
                hash += key[i].charCodeAt();
            }
            //取模，相当取余 ，37是质数，能大概率避免碰撞
            return hash % 37;
        }
        // 新增元素
        put(key,value){ 
            const posotion = this.loseloseHashCode(key);
            this.table[posotion] = value;
        }
        //获取元素
        get(key){ 
            return this.table[this.loseloseHashCode(key)];
        }
        //移除元素
        remove(key){ 
            this.table[this.loseloseHashCode(key)] = undefined;
        }
    }

测试测试：

onst hashtable = new HashTable();
    //添加两个元素
    hashtable.put('小明','age:18');
    hashtable.put('小红','age:20');
    // 找小明的年纪
    console.log(hashtable.get('小明'));

结果：  
![在这里插入图片描述][20210516001930383.png_pic_center]

#### 5.3 处理冲突 ####

通过哈希函数得的重复的结果会产生覆盖问题，就是后面添加的覆盖前面添加的。这样一来前面的数据不就丢失了？那咋办呢？如下：

1.  线性探测法：  
      假如如下图，我们要存一个35，哈希函数就是对其除10取余，经过哈希化得到的是index = 5,但是在插入的时候，发现这个5位置已经有了值78,那怎么办呢，那我们可以去index+1的位置，看看有没有空的位置，不空的话继续往下一点点的查找合适的位置来放置35。总结就是寻找空白的位置来放置冲突的数据项。  
    ![在这里插入图片描述][20210516131747881.png_pic_center]  这样的话查找的时候也是一样，看看对应的关键码位置的值是不是自己想要的，如果不是就往下一点一点查找对比是不是自己想要的，如果一直查到空的位置都没有，那就停下查找了。因为既然有的话它会放在这个空位置的。当然，这个方法缺点也很明显，那就是万一很多连续的数据一起的，那就要找很久，耗性能。 需要注意的是对于利用开放地址法处理冲突所产生的哈希表中删除一个元素时不能直接地删除和设置为空，因为这样将会截断其他具有相同哈希地址的元素的查找地址，通常可以采用设定一个特殊的标志以示该元素已被删除。
2.  链地址法：  
      链地址法前面也是一样的，通过哈希函数计算关键码然后插入数值，不同的是它是插入是链表。就是说如果有关键码一样的，就插在这个关键码地址对应的链表上。  
    就是下面这种感觉：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 5]  
    最后，也看出了，哈希表的缺点，就是空间利用率不高。

## 六.树： ##

#### 6.1 概念 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 6]

1.  树是一种数据结构，它是由n(n>=0)个有限结点组成一个具有层次关系的集合。若n=0，称为空树。
2.  有如下特点：

> 每个结点有零个或多个子结点。  
> 没有父结点的结点称为根结点。  
> 每一个非根结点有且只有一个父结点。  
> 除了根结点外，每个子结点可以分为多个不相交的子树。  
> 具有递归的特性，（任何一颗子树又满足树的概念）。  
> 树形结构种的数据元素之间存在的关系的是一对多, 或者是多对一的关系。

1.  树的相关术语：  
    （1）结点的度：一个结点含有的子树的个数称为该结点的度。  
    （2）树的度：一棵树中，最大的结点的度称为树的度；  
    （3）叶结点或终端结点：度为0的结点称为叶结点；  
    （4）分支结或非终端结点：就是度不为0的结点。父节点称为开始结点，其它称为内部节点。  
    （5）孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点。  
    （6）双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点。  
    （7）兄弟结点：具有相同父结点的结点互称为兄弟结点。  
    （8）子孙：以某结点为根的子树中任一结点都称为该结点的子孙。  
    （9）结点的祖先：从根到该结点所经分支上的所有结点。  
    （10）路径：这个结点自上而下的通过每条路径上的每条边。  
    （11）结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。  
    （12）树的高度或深度：树中结点的最大层次。  
    （13）森林：由棵互不相交的树的集合称为森林。

#### 6.2 树的存储结构 ####

> 计算机只能是顺序或者是链式的存储，所以树这样的结构是不能够直接存储的，要将其转换为顺序或者是链式存储。

1.  双亲表示法: 采用数组存储普通的树，就是顺序存储每个结点的同时，给各个结点添加一个记录其父结点位置的变量，其实就是父节点的下标。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 7]

1.  孩子表示法：给各个结点配备一个链表，用于存储各结点的孩子结点位于数组中的位置（也是下标），如果说，结点没有子结点(叶子结点)，则该结点的链表为空链表。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 8]  
3. 孩子兄弟表示法：从树的根节点开始，依次用链表存储各个节点的孩子节点和兄弟节点。  
链表结点包括三部分内容：

[孩子指针域][数据][兄弟指针域]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 9]

#### 6.3 二叉树 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 10]

[官方解释为][Link 1]：

> 二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

> 二叉树（binarytree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。

> 左子树和右子树是有顺序的，次序不能任意的颠倒的。所以，即使树中某个结点只有一棵子树，也要去区分它是左子树还是右子树。还有，在二叉树中，第 i 层上最多有 2^（i-1） 个结点 (i>=1) 。如果深度为k，则总共最多有2^k-1个结点。

五种形态：  
![在这里插入图片描述][20210517154303721.png_pic_center]  
1、空二叉树——如图（a）；  
2、只有一个根结点的二叉树——如图（b） ；  
3、只有左子树——如图（c） ；  
4、只有右子树——如图（d） ；  
5、左右子树都有——如图（e） 。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 11]

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 12]

完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。满二叉树一定是完全二叉树，反过来不一定成立。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 13]

#### 6.4 二叉搜索树 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 14]  
                   图 6.4  
官方解释为：

>  二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

#### 6.5 js实现二叉搜索树基本结构 ####

//一个结点的结构
    class Node{ 
        constructor(value){ 
            //值
            this.value = value;
            // 保存左子树，就是比当前小的值
            this.left = null;
            //保存右子树，就是比当前大的值
            this.right = null;
        }
    }
    //二叉搜索树的结构
    class BinarySearchTree{ 
        constructor(){ 
            //有个根节点
            this.root = null;
        }
        //对于插入的新结点（值）的走向方法,就是新结点从根结点开始向下一一比较
        insertNode(node,newNode){ 
            //如果新结点更大，往右走
            if(newNode.value>node.value){ 
                //往右走后发现没数据了
                if(node.right === null){ 
                   node.right = newNode;
                }else{ 
                    //往右走后还有结点，“当前结点更新为该结点”，递归重新判断大小后走
                    this.insertNode(node.right,newNode);
                }
            //如果新结点更小，往左走 
            }else if(newNode.value<node.value){ 
                //往左走后发现没数据了
                if(node.left === null){ 
                    node.left = newNode;
                 }else{ 
                     //往左走后还有结点，“当前结点更新为该结点”，递归重新判断大小后走
                     this.insertNode(node.left,newNode);
                 }                    
            }      
        }
        //插入新结点
        insert(value){ 
            //用结点保存数据
            let newNode = new Node(value);
            // 如果空树该结点为根结点
            if(this.root === null){ 
                this.root = newNode;
            }else{ 
                //则走insertNode(node,newNode)方法，判断该结点往哪里走,新结点从根结点开始向下一一比较
                this.insertNode(this.root,newNode);
            }
        }
    }

测试一下（就上面那个**6.4的图**的数据,后面代码都用这个图做例子）：

结果：  
![在这里插入图片描述][20210518214810841.png_pic_center]

#### 6.6 遍历 ####

> 所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

##### 6.6.1 先序遍历 #####

> 先序遍历(Pre-order)，按照根左右的顺序沿一定路径经过路径上所有的结点。在二叉树中，先根后左再右。巧记：根左右。

特点：  
⑴ 访问根结点；  
⑵ 先遍历左子树；  
⑶ 再遍历右子树。

就这种感觉，对于进入到**当前**的某个结点时，它都会执行遍历左子树和遍历右子树。若它遍历左子树那个结点时，**当前结点更新**为左子树那个结点，而**当前结点又**会遍历左子树和遍历右子树，在当前结点左子树和右子树都都没时（相当叶子了），会返回其父节点遍历没遍历过的子树，父结点也都遍历完时，又再向上返回。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 15]  
**结果应为 8-3-1-6-4-7-10-14-13**

###### 6.6.1.1 js实现先序遍历： ######

在6.5的基础上添加一个先序遍历方法：

// 添加先序遍历方法
        //开始从根节点开始遍历，cb相当于获取每一个结点的数据的函数，后面打印出来
        preOrderTraverasl(cb){ 
            this.proOrderTraveraslNode(this.root,cb);
        }
        // 通过递归实现遍历
        proOrderTraveraslNode(node,cb){ 
            // 若没结点，空结点，直接返回
            if(node===null) return;
            // cb添加一个结点数据
            cb(node.value);
            // 遍历左子树，同样采用递归，就想象成当前结点的更新又要重新遍历左右子树
            this.proOrderTraveraslNode(node.left,cb);
            // 遍历右子树，同样采用递归，就想象成当前结点的更新又要重新遍历左右子树
            this.proOrderTraveraslNode(node.right,cb);
        }

测试下：

const tree = new BinarySearchTree();
    tree.insert(8);
    tree.insert(3);
    tree.insert(10);
    tree.insert(1);
    tree.insert(6);
    tree.insert(14);
    tree.insert(4);
    tree.insert(7);
    tree.insert(13);
    /* console.log(tree); */
    
    const rst = [];
    const cb = function(val){ 
        rst.push(val);
    }
    tree.preOrderTraverasl(cb);
    console.log(rst);

结果没毛病：  
![在这里插入图片描述][20210518223531154.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 16]

##### 6.2 中序遍历 #####

>  中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

特点：  
（1）中序遍历左子树  
（2）访问根结点  
（3）中序遍历右子树

有个巧妙的方法就是二叉树的中序遍历就是将节点投影到一条水平的坐标上。如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 17]  
这个图的中序遍历结果就是5-10-6-15-2

###### 6.2.1 js实现中序遍历 ######

同样在6.5基础上添加一个中序遍历：

// 添加中序遍历方法
        //开始从根节点开始遍历，cb相当于获取每一个结点的数据的函数，后面打印出来
        inOrderTraverasl(cb){ 
            this.inOrderTraveraslNode(this.root,cb);
        }
        // 通过递归实现遍历
        inOrderTraveraslNode(node,cb){ 
            // 若没结点，空结点，直接返回
            if(node===null) return;
             // 遍历左子树
             this.inOrderTraveraslNode(node.left,cb);
            // cb添加一个结点数据
            cb(node.value);
            // 遍历右子树
            this.inOrderTraveraslNode(node.right,cb);
        }

测试：

结果：  
![在这里插入图片描述][20210519141138523.png_pic_center]

##### 6.3 后序遍历： #####

> 后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

特点：  
（1）后序遍历左子树  
（2）后序遍历右子树  
（3）访问根结点

###### 6.3.1 js实现后序遍历 ######

同样在6.5基础上添加一个后序遍历：

// 添加后序遍历方法
        //开始从根节点开始遍历
        postOrderTraverasl(cb){ 
            this.postOrderTraveraslNode(this.root,cb);
        }
        // 通过递归实现遍历
        postOrderTraveraslNode(node,cb){ 
            // 若没结点，空结点，直接返回
            if(node===null) return;
             // 遍历左子树
             this.postOrderTraveraslNode(node.left,cb);
            // 遍历右子树
            this.postOrderTraveraslNode(node.right,cb);
             // cb添加一个结点数据
             cb(node.value);
        }

同样测试下，结果为：

const rst = [];
    const cb = function(val){ 
        rst.push(val);
    }
     tree.postOrderTraverasl(cb); 
    console.log(rst);

![在这里插入图片描述][20210519142800382.png_pic_center]

#### 6.7 完善6.5js实现二叉搜索树的基本结构 ####

##### 6.7.1 添加输出最大值的方法： #####

//输出最大值
         max(){ 
             let node = this.root;
             //按照二叉搜索树特性，一直往右走
             while(node.right !== null){ 
                 node = node.right;
             }
             return node.value;
         }

测试下：

console.log(tree.max());

![在这里插入图片描述][20210519144144187.png_pic_center]

##### 6.7.2 添加输出最小值方法 #####

//输出最小值
          max(){ 
            let node = this.root;
            //按照二叉搜索树特性，一直往左走
            while(node.left != null){ 
                node = node.left;
            }
            return node.value;
        }

测试：

console.log(tree.min());

![在这里插入图片描述][20210519144511769.png_pic_center]

##### 6.7.3 查找看是否有特定的值 #####

//参数为要寻找的值
        search(val){ 
            let node = this.root;
            while(node != null){ 
                if(node.value > val){ 
                    node = node.left;
                }else if(node.value < val){ 
                    node = node.right;
                }else { 
                    //就是node.value == val 时，返回true,没有的话会undefined
                    return true;
                }
            }
        }

测试下，给一个 13 和一个 不存在的 5 看看：

console.log(tree.search(13));
    console.log(tree.search(5));

![在这里插入图片描述][20210519145837429.png_pic_center]

#### 6.8 二叉搜索树删除结点 ####

##### 6.8.1 结点没有子树 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 18]  
直接删除结点就可，对树结构影响不大。

##### 6.8.1 结点有一个子树 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 19]  
对于只有一个子树的情况，考虑将其子树作为其父结点的子树，当然要根据被删除的结点确定是放左子树还是右子树。

##### 6.8.1 结点有两个子树 #####

网上这么解释：

> 用被删除节点A的左子树的最右节点或者A的右子树的最左节点作为替代A的节点，并修改相应的最左或最右节点的父节点的指针。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 20]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 21]

#### 6.9 二叉搜索树总结 ####

> 二叉搜索树的优点:作为数据存储的结构有重要的意义,可以快速的找到给定的关键字的数据项,并且可以快速的插入和删除数据。

> 二叉搜索树的缺点:具有局限性。同样的数据，可以对应不同的二叉搜索树。比较好的二叉搜索树的结构是左右分布均匀的。但是在我们插入连续的数据的时候，也会有导致数据分布不均匀的二叉搜索树。我们就把这个分布不均匀的树叫做非平衡树。如下：它其实就是一个链表，甚至比链表查询速度还要慢。所以这就很不好。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 22]

#### 6.10 二叉平衡树\* ####

> 概念: 也叫平衡二叉搜索树，也叫做AVL树， 是一种自平衡的树。除了规定左结点小于根结点，右结点大于根结点以外，还规定了左子树和右子树的高度差不得超过1。

**平衡因子:每个结点的左子树的高度减去其右子树的高度。  
平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。  
如果绝对值超过1，就是失衡了。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 23]  
可以通过旋转来操作来达到平衡，有以下几种旋转：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 24]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 25]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 26]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 27]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 28]

#### 6.11 红黑树\* ####

**官方概念：**

>    红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。  
>     红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。  
>    红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。  
>    它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

有如下特征：

1.  结点是红色或者黑色。（结点上有一个color的属性）。
2.  根结点是黑色。
3.  叶子结点都是黑色，都为null。（也叫NIL结点，为配合红黑树特性假想出来的结点）。
4.  连接红色结点的两个子结点都是黑色，就是说红色结点的父结点都是黑色，红色结点的子结点也是黑色。
5.  从任一节结点出发到每个叶子的路径都包含相同数目的黑色结点。

**以上的5个特性就是红黑树能自动维持平衡的的准则。**

这都是为了保证从根节点到叶子结点的最长路径不大于最短路径的2倍。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 29]

> 当插入和删除结点时，就会导致红黑树的平衡被破坏，这个时候就需要对红黑树进行调整,从而使他符合5个特性,以此保证红黑树的平衡。

> 红黑树的平衡调整有两种方式: 变色，旋转(左旋转和右旋转)。

## 七.图： ##

#### 7.1 基本概念 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 30]  
**概念：**

1.  它是一种比树更为复杂的数据结构。前面的树结点之间是一对多的关系，并且存在着一个父与子的层级划分。而图是**多对多**的关系，且所有的顶点都是平等的。在图中，最基本的单元是**顶点**(vertex) ，顶点相当于树中的结点，顶点之间的关系被称为**边**(edge)。
2.  线性表可以没有元素，称为空表。树中可以没有节点，称为空树。但是，在图中不允许没有顶点（有穷非空性）。

**分类：**

1.  无向图: 边没有方向的图称为无向图，边的作用仅仅是连接两个顶点，没有其他的含义。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 31]
2.  有向图: 边不仅连接两个顶点，并且具有方向性，可能是单向也可能是双向的。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 32]
3.  带权图: 边可以带权重。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 33]  
**相关术语：**

> **1. 相邻顶点: 当两个顶点通过一条边相连时，我们称这两个顶点是相连的，并且是依附于这两个顶点的。  
> 2. 度: 指某个顶点的度，是依附于这个顶点的边的个数。  
> 3. 子图: 一幅图中，所有边的子集组成的图，包含这些边的依附的顶点。  
> 4. 路径: 是由边顺序连接的一系列的顶点组成。  
> 5. 环: 是一条至少含有一条边且终点和起点相同的路径。  
> 6. 连通图: 如果图中，任意一个顶点都存在一条路径到达另外-一个顶点,那么这 副图我们就称之为连通图。  
> 7. 连通子图: 一个非连通图由若干个连通的部分组成， 每一个连通的部分就可以称为该图的连通子图。  
> 8.自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。**

**存储结构：**

1.  **邻接矩阵**\------表示顶点间相连关系的矩阵。矩阵中的 \[i,j\] 代表其对应的第i个顶点与第j个顶点是否连接。其中用 1 表示顶点与顶点有连接接的关系，用 0 表示没有连接关系。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 34]  
缺点：非常消耗内存。

1.  **邻接表**\------由图中的每个顶点以及和顶点相邻的顶点列表组成。用数组/链表/字典等等实现都可以。  
    如：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 35]

#### 7.2 js实现一个简单的图结构 ####

就拿下面这个图做例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 36]

// 定义一个类
    class Graph{ 
        constructor(){ 
            // 数组存储每个顶点
            this.verties = [];
            // 对象存储边，如有： 'A': ['B','C','D'];
            this.edgeList = { };
        }
        // 添加顶点方法
        addVerTex(v){ 
            //直接在末尾添加
            this.verties.push(v);
            //同时在对象里定义该顶点与哪个顶点有边的数组
            this.edgeList[v]=[];
        }
        // 添加边方法
        addEdge(a,b){ 
            // a与b相连的话，对方都应该存储对方
            this.edgeList[a].push(b);
            this.edgeList[b].push(a);
        }
        // 输出该图方法
        toString(){ 
            let rst = '';
            //循环顶点数组
            this.verties.forEach(item=>{ 
               //添加每个顶点
               rst += `${ item}=>`;
               // 循环边数组
               this.edgeList[item].forEach(currentValue=>{ 
                   // 添加该顶点对应的边
                  rst += `${ currentValue},`;
               })
                // 换行
                rst += '\n';
            })
            return rst;       
        }
    }

测试一波：

const graph = new Graph();
    // 添加顶点
    graph.addVerTex('A');
    graph.addVerTex('B');
    graph.addVerTex('C');
    graph.addVerTex('D');
    graph.addVerTex('E');
    graph.addVerTex('F');
    //添加边
    graph.addEdge('A','B');
    graph.addEdge('A','C');
    graph.addEdge('A','D');
    graph.addEdge('B','E');
    graph.addEdge('B','F');
    graph.addEdge('C','D');
    //输出
    console.log(graph);
    console.log(graph.toString());

结果很nice：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 37]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 38]

#### 7.3 图的遍历 ####

**官方解释**：

> 图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。

1.  广度优先遍历（BFS）：  
      广度优先的思想，从图中的某个顶点v出发，在访问了v以后，依次去访问的各个未曾访问过的邻接点，然后分别从这些邻接点出发，依次访问它们的邻接点。图中所有的顶点都要被访问到。
2.  深度优先遍历（DFS）：  
      从图中的某个顶点v出发，判断是否有邻接点和是否访问过，如果没有访问过访问该邻接点。如果该邻接点还有邻接点就继续访问下去，直到到达没有邻接点可以访问的顶点，就回退到上一个顶点。

**遍历思想**：

1.  每一个顶点有三种状态：  
    （1）未发现(没有发现这个顶点)。  
    （2）已被发现(发现其他的顶点连接到这里，但是没有去查找这个顶点的全部连接的顶点)。  
    （3）已被探索(已经发现这个顶点连接的全部顶点)。
2.  记录顶点是否被访问过，使用3三种颜色来反映他们的状态。  
    （1）白色(未发现)。  
    （2）灰色(已被发现)。  
    （3）黑色(已被探索)。
3.  广度优先的遍历过程（BFS）：  
    （1）发现未发现的顶点后，存放到队列中，等待查找，并且将这些顶点标记为已发现状态。  
    （2）在队列中拿出已经发现的顶点，开始探索全部顶点,并且要跳过已经探索过的顶点。  
    （3）遍历完这个顶点以后，将这个顶点标志为已经探索。  
    （4）循环在队列中探索下一个顶点。
4.  深度优先的遍历过程（DFS）：  
    （1）从某顶点开始查找,并且将这个顶点标记为已经发现(灰色)。  
    （2）从这个顶点开始探索其他的全部的顶点，并且跳过已经发现的顶点。  
    （3）遍历完这个顶点以后，将这个顶点标记为已探索(黑色)。  
    （4）递归返回，继续探索下一个路径的最深顶点。

##### 7.3.1 **js实现广度优先遍历：** #####

**注意：里面使用的基本队列结构是在 3.5.1 中定义的，下面代码不粘贴出来了，上面已经实现图的基本结构也不粘贴出来了，直接在Graph类里添加以下方法：**

// 广度优先
        // 初始化颜色，每个顶点先为白色。
        initColor(){ 
            let colors = { };
            this.verties.forEach(item=>{ 
                //每个顶点先为白色
                colors[item] = 'white';
            })
            return colors;
        }
         //实现BFS,v为开始遍历结点，callback为输出函数
         bfs(v,callback){ 
             //初始化颜色
             let color = this.initColor();
             //新建一个队列
             let queue = new Queue();
             // v入队列，v为开始遍历顶点
             queue.enqueue(v);
             // 实现遍历，入队和出队和数据的放入与取出
             //判断队列是否为空
             while(!queue.isEmpty()){ 
                // 保存出队列的顶点,第一个v出
                const qVertex = queue.dequeue();
                // 获取与qVertex的所有连接的顶点
                const edge = this.edgeList[qVertex];
                // 遍历所有与qVertex的连接的顶点
                for(let i=0;i<edge.length;i++){ 
                    //当前的顶点
                    const e =edge[i];
                    // 若为白色未发现顶点入队列
                    if(color[e] === 'white'){ 
                        //变灰色后入队
                        color[e] = 'gray';
                        queue.enqueue(e);
                    }
                }
                // 此时已被探索的qVertex可变黑色了
                color[qVertex] = 'black';
                // 输出顶点
                if(callback){ 
                    callback(qVertex);
                }
             }
         }

**测试下：**

**结果**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 39]

##### 7.3.2 js实现深度优先遍历 #####

就在7.3.1基础上再添加一个深度优先遍历的方法：

// 深度优先DFS，递归实现,v开始遍历
         dfsVisit(v,color,callback){ 
             // v修改为灰色
             color[v] = 'gray';
             // 输出 v
             if(callback){ 
                 callback(v);
             }
             // 得到与 v 相邻的全部顶点
            let edge = this.edgeList[v];
            // 遍历与 v 相邻的全部顶点
            edge.forEach(item=>{ 
                //保存当前顶点
                let e = item;
                //又通过递归实现遍历该顶点还是白色的相邻顶点
                if(color[e]==='white'){ 
                    this.dfsVisit(e,color,callback);
                }
            })
            // 被探索的顶点变黑
            color[v] = 'black';
         }
         //深度优先DFS入口
         dfs(v,callback){ 
             //初始化颜色
            const color = this.initColor();
            // 递归
            this.dfsVisit(v,color,callback);
         }

**测试测试**：

//输出
    console.log('DFS:');
    graph.dfs('A',e=>{ 
        console.log(e);
    })

**结果没问题**：  
![在这里插入图片描述][20210522131435628.png_pic_center]

#### 7.4 最短路径问题 ####

**最短路径**：  
  是指如果从图中的某一个顶点(起点)出发到达另外一个顶点(终点)的所有路径中最短的那条路径。也就是计算路径权值最小的那条。

## 八.算法复杂度： ##

#### 8.1 基本概念 ####

说概念前首先先看下面一个题：

假如有 a+b+c=1000,并且 a^2 + b^2 = c^2, 请求出所有的a\b\c的组合。

我们显然可以用以下方法得出结果和运行时间：

//启动一个计时器来跟踪某一个操作的占用时长。每一个计时器必须拥有唯一的名字。
    console.time('消耗时间');
    for(let a=0;a<1000;a++){ 
        for(let b=0;b<1000;b++){ 
            for(let c=0;c<1000;c++){ 
                  if(a+b+c===1000&&Math.pow(a,2)+Math.pow(b,2)===Math.pow(c,2)){ 
                      console.log(a,b,c);
                  }
            }
        }
    }
    console.timeEnd('消耗时间');

结果：  
![在这里插入图片描述][20210522153018559.png_pic_center]  
我们还可以用以下方法得出结果和运行时间：

console.time('消耗时间');
    for(let a=0;a<1000;a++){ 
        for(let b=0;b<1000;b++){ 
           let c = 1000 - a - b;
           if(Math.pow(a,2)+Math.pow(b,2)===Math.pow(c,2)){ 
               console.log(a,b,c);
           }
        }
    }
    console.timeEnd('消耗时间');

结果：  
![在这里插入图片描述][20210522153454798.png_pic_center]  
![在这里插入图片描述][20210522153627879.png_pic_center]  
  可以发现**一样的结果消耗的时间却相差如此之多**。所以说，一个优秀的算法在程序中，能占用最少的内存空间区完成需求和花最少的时间去完成需求。  
  结论: 算法研究就是的如何花最少的时间和占用最少的内存空间去完成相同的需求。

**算法复杂度概念：**  
  算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。  
  可以分为:时间占用和空间占用。有关算法的时间耗费分析，我们称为算法的时间复杂度分析，算法空间的耗费分析，我们称为空间的复杂度分析。

#### 8.2 时间维度 ####

**时间维度**: 是指执行当前算法所消耗的时间，时间越短，算法会越好。相对的代码执行次数越多,耗费时间越长，效率就越差。而**时间复杂度就看作是一个算法的执行时间根据数据规模增长的一个趋势**。执行次数与执行参数是与时间复杂度息息相关。可以这样假设，一个问题的规模是n,解决这个问题的某一算法所需要的时间为T(n)。

> T(n) = O(fn(n))    //大O表示法表示时间复杂度

> O（）括号里是一个函数，表示某个算法耗时与数据增长间的**关系**。比如常数阶O(1),对数阶O(log2n)等等…

> n 为输入数据的量。

> T 为算法需要执行的总时间。

总之，记住时间复杂度表示的是一种变化趋势（一种关系），不是真正的时间多少，真正时间多少要看n的大小等等。

**分析算法的时间复杂度时有以下三种**:

1.  算法完成工作最少需要的基本操作，为最优的时间复杂度。（反映最乐观，理想情况，意义不大）
2.  算法完成工作最多需要的基本操作，为最坏的时间复杂度。（提供了一种保证，表明算法在这个程序的基本操作中一定可以完成需求）
3.  算法完成工作平均需要的基本操作, 为平均时间复杂度。（比较全面的评价）

**常见的时间复杂度**：

看我在网上找的这张图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 40]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 41]

1.  常数阶: O(1)， T(n) = O(1),时间复杂度是常数级别的。表示无论n的规模如何增长，它的执行时间基本是不变的。常数阶是最低的时间复杂度。

int i = 1;
    int j = 2;
    int sum = i + j;

1.  线性阶: O(n), T(n)= O(n),代表数据量增大几倍,耗时也增大几倍。如遍历。

for(i=1; i<=n; i++)
    { 
       sum+=i;
    }

1.  平方阶: O(n^2), T(n) = O(n^2),代表的是数据量增大n倍时，耗时增大n的平方倍。如两层循环。

for(i=1; i<=n; i++)
    { 
      for(j=1; j<=n; j++)
    { 
       sum+=i+j;
     }
    }

1.  立方阶: O(n^3), T(n) = O(n^3),代表的是数据量增大n倍时，耗时增大n的立方倍。如三层循环。
2.  对数阶: O(logn), T(n) = O(logn),当数据增大n倍时，耗时增大logn倍，如二分查找。

int i = 1;
    while(i<n)
    { 
        i = i * 2;
    }

1.  线性对数阶: O(nlogn), T(n) = O(nlogN),就是n乘以logn,当数据增大n倍，耗时会增大n \* logn倍。

for(j=1; j<n; j++)
    { 
        i = 1;
        while(i<n)
        { 
            i = i * 2;
        }
    }

1.  指数阶: O(2^n), T(n) = O(2^n),当数据增大n倍时候。耗时增大 2^n倍。

对比: O(1)< O(logn) < 0(n) < O(nlogn) < O(n^2)< O(n^3)< O(2^n)

**计算时间复杂度**：

1.  基本操作，即只有常数项，认为这个时间复杂度就是O(1)。
2.  顺序结构，时间复杂度按加法。
3.  循环结构，时间复杂度按乘法。
4.  分支结构，时间复杂度取最大值。

判断一个算法的效率的时候，往往只需要取关注操作数量的最高次项。

#### 8.3 空间维度 ####

**空间维度**:是指执行当前算法所消耗的内存空间。  
 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))，表示算法存储空间与输入值之间的关系。

S(n)=O(f(n))

通常来讲，只要我们的算法不涉及到动态的空间，递归，栈，空间复杂度通常为常数O(1)。算法的空间复杂度，并不是计算实际占用的空间，而是计算整个算法的辅助空间单元(变量)的个数,与问题的规模没有关系，空间复杂度主要看新开辟的变量个数。

## 九.排序算法 ##

![在这里插入图片描述][20210523143336266.gif_pic_center]

#### 9.1冒泡排序 ####

>    这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

**核心思想（升序）**：

比如有以下一个无序的数组：

arr=[5,89,1,45,18,28];

**第一轮比较**：（目的是把最大的（89）放在数组的最后一个元素位置）  
先第一项（5）跟第二项（89）比，如果第一项比第二项大，则交换位置。这里显然不用交换位置。接下来，第二项（89）跟第三项（1）比，如果第二项比第项大，则交换位置，89显然比1大，交换位置。就是数组变成：arr=\[5,1,89,45,18,28\]; 接下来到第三项跟第四项比，一直重复操作，最终会达到第一轮比较的目的，最大的（89）会放在数组的最后一个元素位置了。arr=\[5,1,45,18,28，89\]; 一共比了5次。  
**第二轮比较**：（（目的是把第二大的（45）放在最大的元素（89）前的一个位置））  
也是跟第一轮比较一样，第一项跟第二项比，如果第一项比第二项大，则交换位置。一直重复这样的操作，最终也会达成第二轮比较的目的。需要注意的是，这里显然数组最后一项跟倒数第二项不用比了，所以比较次数会比第一轮少一次。  
**第三，第四，第五轮等等…比较**  
一直重复，直到排序好。

**js实现冒泡排序：**

// 定义一个无序数组
    var arr = [5,89,1,45,18,28];
    // 比较轮数
    for(let i=0;i<arr.length-1;i++){ 
        //每轮比较次数
        for(let j=0;j<arr.length-1-i;j++){ 
            // 判断大小
            if(arr[j]>arr[j+1]){ 
                // 利用解构赋值交换两个变量的值
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]];
            }
        }
    }
    // 输出看看
    console.log(arr);

结果：  
![在这里插入图片描述][20210523154334821.png_pic_center]

#### 9.2选择排序 ####

官方解释是：

> 选择排序（Selectionsort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

我觉得官方解释得也差不多，再配合下面这张图理解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 42]  
需要注意的是，当找到最小值要放到起始位置的时候，是要保存对应的下标索引后交换两元素位置，不是直接赋值。

**js实现选择排序：**

结果：  
![在这里插入图片描述][20210523193725165.png_pic_center]

#### 9.3插入排序 ####

官方解释：

>     插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌

简单来说就是比如有下面这个无序数组：

arr=[5,89,1,45,18,28];

然后我新建一个空数组 night = \[ \]。第一次把 arr\[0\] 放进 night = \[ \]，然后有了 night = \[5\]。  
    然后我又拿 arr\[1\] 出来，把 arr\[1\] 和night = \[5\]里的全部元素一一比较，注意是从后往前比较，因为先比大的再比小的，发现89大于5，就直接在5的位置的下一个位置添加89，就有了 night = \[5，89\]。  
   然后我又拿 arr\[2\] 出来（也就是1），把 arr\[2\] 和night = \[5,89\]里的全部元素一一比较，注意是从后往前比较，发现没有大于night = \[5,89\]里任意一个元素的，那就直接在night = \[5，89\]的开头添加1，就有了 night = \[1，5，89\]。  
   然后我又拿 arr\[3\] 出来（也就是45），把 arr\[3\] 和night = \[1，5，89\]里的全部元素一一比较，注意是从后往前比较，比到5的时候发现45大于5，那就直接在5的位置的下一个位置添加45，其它的自然往后移动了，就有了 night =night = \[1，5，45，89\]。  
   以此类推，直到排序好，看下面代码更好理解。

**js实现：**

// 新建一个无序数组，相当桌面的牌
    const arr = [5,89,1,45,18,28,77,2]; 
    // 新建一个数组，相当手上抓的牌
    const night = [];
    //添加arr【0】，抓第一张牌
    night.push(arr[0]);
    // 从arr里取牌次数
    for(let i=1;i<=arr.length-1;i++){ 
        //保存当前牌
       let A = arr[i];
       // 从night后往前遍历，就是从大往小比较
       for(let j=night.length-1;j>=0;j--){ 
           // 保存已排好的牌，后面用来比较
           let B = night[j];
           // 比较，如果A>B
           if(A>B){ 
               //把A放进B的下一个位置，退出循环
               night.splice(j+1,0,A);
               break;
           }
           // 比完了，A都没有比night里任意一个大
           if(j===0){ 
               // 把A放在night开头位置
               night.unshift(A);
           }
       }
    }
    
    console.log(night);

splice() 方法向/从数组中添加/删除项目，然后返回被删除的项目。我们这里用添加。（规定添加/删除项目的位置；是否要删除的项目数量。如果设置为 0，则不会删除项目；向数组添加的新项目。）  
unshift() 方法可向数组的开头添加一个或更多元素，并返回新的长度。  
结果：  
![在这里插入图片描述][20210524000506951.png_pic_center]  
**其实也不用新建一个数组，上面解释和写法反而变麻烦了，默认当前数组前面的是排好的就行，直接如下：**

//无序数组
    const arr = [5,89,1,45,18,28,77,2,45]; 
    //拿牌次数
    for(let i=1;i<arr.length;i++){ 
        // 这是拿到的牌，用中间变量保存起来，后面用来比较已经排好的牌
        var temp = arr[i];
        //这是排好的牌，就是数组下标 0到j-1 的牌都是排好的
        var j = i-1;
        // 如果拿到牌比我排好的牌里面里面任意一张大（从后往前比），执行里面代码
        while(j>=0&&arr[j]>temp){ 
            // 给前面挪个位置，拿到的牌要往前走
            arr[j+1]=arr[j];
            // 还没比出来？继续往前比
            j--;
        }
        //不执行循环了，看来比完了，拿到的牌插入对应位置
        arr[j+1]=temp;
    }
    
    console.log(arr);

结果：  
![在这里插入图片描述][20210524135825888.png_pic_center]

## 未完结，先发出来，每天都会更新一点！每天都会更新一点！每天都会更新一点！重要的话说三遍~~~来关注一起相互探讨打卡学习⑧~ ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 43]

[20210507201930377.png_pic_center]: /images/20221021/3b8bd6ca481f40088cf4e61548102f2d.png
[20210507202522197.png_pic_center]: /images/20221021/fceb2a698eab42018c95bd332649784a.png
[20210507202800108.png_pic_center]: /images/20221021/a2151db4a62c422e94ecb4581a5a739e.png
[2021050720324358.png_pic_center]: /images/20221021/38a8fb2ba6174fc5bc55d2c721a548d2.png
[20210507204131267.png_pic_center]: /images/20221021/2591c15f0fe544c0b0eaa7da032e832b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/1a9d7385a01540dc9e04e4ade2afa509.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221021/39071f9b6e244090a69a92bd4e716c63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221021/cc744a05b5dc45feaa4f8f3939ff8a16.png
[20210511140330227.png_pic_center]: /images/20221021/ca949d5ea56846fa8a0270588fd6d1d7.png
[20210511150651657.png_pic_center]: /images/20221021/37414046c516467197fa34e19f5fd818.png
[20210512141046345.png]: /images/20221021/a60c4f48534441fd9d4ff222fb9abd94.png
[20210512161926117.png_pic_center]: /images/20221021/8b5306cbd04e4fd7b63d8d202df47e18.png
[2021051216573059.png_pic_center]: /images/20221021/ac1165768f7d4ce5af2a9ead29ae76f6.png
[20210512201926826.png_pic_center]: /images/20221021/3ef14f20311246469b3bb3a8d492a940.png
[20210513105111790.png_pic_center]: /images/20221021/3336849fc46846f2844150a7b0d1922a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221021/6433a5b7a42f4e4a800cc9a471d9a177.png
[20210514011800384.png_pic_center]: /images/20221021/798c17bf8c7f45639d2caea6a5701be6.png
[20210514133224105.png_pic_center]: /images/20221021/d1879fc7478a438088e8a3545c0ef62f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221021/93ef4315dca049b09c64e376089745cf.png
[20210516001930383.png_pic_center]: /images/20221021/6c6c008b6a8a408bba29167a32b110b0.png
[20210516131747881.png_pic_center]: /images/20221021/332e8cdc229b43dcbcd5d4c5513a2210.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221021/5de0f68e478c4134a920a997488fc4fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221021/cef30b9870844aa5ad56420b07eaa2e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221021/9e5e9df705444320a09a816e4e3d12d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221021/e839517326e540abaa7e49bcfb57ce3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221021/64ebbb33c8f4471e8c388abf0abaa935.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221021/56dca65b94a54d25bed2379c01ad15e9.png
[Link 1]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91
[20210517154303721.png_pic_center]: /images/20221021/5df8e7827002468d9e76834863043c93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221021/d7676ac4827d4b128227a38b78243392.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221021/3321b6dd7b7149c8b47ff04e603366c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221021/6b9c3c3d338d473d9dcca332138f7f1c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221021/7f3e961d894340b4a68c26124a79d930.png
[20210518214810841.png_pic_center]: /images/20221021/f144265faeea42b8a5ca2049cdd7062f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221021/1aee5aa1d59d46cbb26af29992551278.png
[20210518223531154.png_pic_center]: /images/20221021/6f264a1985464f48b185d13ef44816c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20221021/95221367adef43ed9249b9ba1e08c588.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 17]: /images/20221021/09d8c5f16d6b406185f3567dc14558f3.png
[20210519141138523.png_pic_center]: /images/20221021/2699440aa155465689be3284900d7a2f.png
[20210519142800382.png_pic_center]: /images/20221021/56832ca645ec4832b0d4d96ff1d7ad0a.png
[20210519144144187.png_pic_center]: /images/20221021/cfa909ce9d37408d8caabdffcbfc703e.png
[20210519144511769.png_pic_center]: /images/20221021/fb09f47662914e00b7bb0dd793c82784.png
[20210519145837429.png_pic_center]: /images/20221021/cc4d0b7d5c604dc39843fb0d19286e33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 18]: /images/20221021/96363f273e1349dd82b4b93ec8e216f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 19]: /images/20221021/19849a1bfe2f4216b64296d169ffacd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 20]: /images/20221021/40ae97dc85794951b3c1df2c977f826f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 21]: /images/20221021/506d46edf1444d269089785a55637bd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 22]: /images/20221021/0675a29eabd04ea293d9301a0e4c737c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 23]: /images/20221021/6e83b6dbf32d4fb1b577da9545337264.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 24]: /images/20221021/6c65f88abc3944e690c3cb352aa2fa66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 25]: /images/20221021/6b6e7f4345904d6dbd213a20257b006c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 26]: /images/20221021/a7b270187e664cbdb4c022cc4a6d33b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 27]: /images/20221021/3f21c53d2f1a42ee9ec59317658918f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 28]: /images/20221021/6c0ee6b1885241f497a8474079558e4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 29]: /images/20221021/052cc7f7ce39456393f177ce4eb0da99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 30]: /images/20221021/13e1024b1323442ca5a9c6e6ed149e30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 31]: /images/20221021/7fc3fab9961143d09cf78f78e4553678.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 32]: /images/20221021/afcfaae8af244c2d96a6ad8cfd18fa7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 33]: /images/20221021/f8d6938a43be4990bdcdc342d765800d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 34]: /images/20221021/f4a31032a35846d28f410e9f9ac39ce8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 35]: /images/20221021/c7728fba6bad4fc0b135ca7c9f28c54c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 36]: /images/20221021/82e816f95fe84370bf035f087a30e6ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 37]: /images/20221021/a8f00a2b61a243ca85eb78608a013c02.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 38]: /images/20221021/431908884e5c47adad8ca76cb23d1bab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 39]: /images/20221021/d1a21fbb2d064c1ea15f9d132bdc308f.png
[20210522131435628.png_pic_center]: /images/20221021/19fe8f6da6fc45368392bdc358dd15df.png
[20210522153018559.png_pic_center]: /images/20221021/b8a1ebadb3a74dc5810d4ef7772678dc.png
[20210522153454798.png_pic_center]: /images/20221021/ad0adce0c6474e8ca4dce891c8d11b20.png
[20210522153627879.png_pic_center]: /images/20221021/5cb4a849f4a34df48d2b9fe6d2552e0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 40]: /images/20221021/58123ca459094afc9a42a77a69c3ef33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 41]: /images/20221021/bb97489df193405289ed8c717371e398.png
[20210523143336266.gif_pic_center]: /images/20221021/53bef10a93834a5b90b3bb69b9e37477.png
[20210523154334821.png_pic_center]: /images/20221021/42e8616ea1b34d49ab8b79728b3afd20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 42]: /images/20221021/659477e6f63c4f96bdaf121f5ed2fe8c.png
[20210523193725165.png_pic_center]: /images/20221021/19a24cbb643349d9ba75628aa772ebe6.png
[20210524000506951.png_pic_center]: /images/20221021/0737cced253c4955b46d59ab7c6a07ac.png
[20210524135825888.png_pic_center]: /images/20221021/c3a90e89969e4341b9b024d5c57cd619.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzE4MzEyNTEzODc_size_16_color_FFFFFF_t_70_pic_center 43]: /images/20221021/cb1bd1b729f44ae0ae031727faee67e7.png