JavaScript数据结构和算法

本文分为三部分，第一部分前言，介绍算法的必要性和基本概念；第二部分详细讲解九大类数据结构；第三部分详细讲解排序算法、搜索算法、diff算法等。

1.前言

1.1.web前端工程师有没有必要学习数据结构和算法？

一个web前端工程师需不需要学习数据结构，完全是要看你的个人职业规划。 如果你准备专注于前端开发，不打算转型或者走管理的话，你可以更专注于JavaScript，各种花样的JavaScript，毕竟这才是前端在实际中最多用到，需要多多学习的。 如果你不想仅仅当一个码农，想码代码一两年之后转为架构师，全栈工程师，或者管理者，那你肯定不能只懂前端，不光是数据结构，算法，设计模式，可能后端，底层你都需要了解或是精通，全都懂才能成为顶尖人才，才能让下属信服你，企业才愿意给你更高的工资，因为你什么都能做，还能帮他管理，为什么不把两个人的工资给你，同时你可以做三个人的事情呢?

我之前总结过《JavaScript设计模式》，举例20种常用的设计模式，这篇算是它的姐妹篇《JavaScript数据结构和算法》。

设计模式、算法，数据结构，对于任何程序员来说，都是需要修炼的内功，只有基本功扎实，学习其他编程语言的时候才会游刃有余。

1.2.算法相关概念

在讲解数据结构和算法前，需了解一些算法的概念，方便后续章节的阅读。 算法： 算法是指解题方案的准确而完整的描述，是一系列解决问腿的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

算法的效率： 是指算法执行的时间，算法执行时间需要通过算法编制的程序在计算机上运行时所消耗的时间来衡量。

一个算法的优劣可以用空间复杂度和时间复杂度来衡量。

时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。

空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

算法设计时，时间复杂要比空间复杂度更容易复杂。一般情况下，没有特殊说明，复杂度就是指时间复杂度。

时间频度： 一个算法中的语句执行次数称为语句频度或时间频度。

一个算法执行所消耗的时间，从理论上是不能算出来的，必须上机测试才知道。但我们不可能也没有必要对每个算法都上机测试，只需要知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句执行次数成正比例，哪个算法中执行语句次数多，它花费的时间就多。

时间复杂度： 执行程序所需的时间。

大O表示法： 算法的时间复杂度通常用大O符号表述，定义为T(n)=Of((n))。

推导大O阶：推导大O阶就是将算法的所有步骤转换为代数项，然后排除不会对问题的整体复杂度产生较大影响的较低阶常数和系数。

推导大O阶，按照下面的三个规则来推导，得到的结果就是大O表示法： 1.运行时间中所有的加减法常数用常数1代替 2.只保留最高阶项 3.去除最高项常数

先来看下图，对各个时间复杂度认下脸：

先说结论，通过图片直观的体现，能够得到常用的时间复杂度按照消耗时间从小到大排序依次是： O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

大概讲解下，这些是什么玩意儿... O(1)常数阶

let sum = 0,
    n = 100; // 执行一次
sum = (1+n)*n/2; // 执行一次
console.log(sum); // 执行一次 

上面算法的运行次数的函数是f(n)=3，则有O(f(n) = 3)即O(3)， 常数项用常数1表示，则最终的表示法为O(1)，我们称之为常数阶。

O(n)线性阶 线性阶主要分析循环结构的运行情况，如下：

for(let i = 0; i < n; i++){
    // 时间复杂度O(1)的算法
    ...
}

上面算法循环体中的代码执行了n次，因此时间复杂度是O(n)。

O(logn)对数阶

let number = 1;
while(number < n){
    number = number*2;
    // 时间复杂度O(1)的算法
    ...
}

上面的代码，随着number每次乘以2后，都会越来约接近n，当number不小于n时候就会退出循环。假设循环的次数为x，则由2^x=n得出x=log₂n，因此得到这个算法的时间复杂度为O(logn)。

O(n²)平方阶 平凡阶一般出现在嵌套的循环中，如下：

for(let i=0; i<n; i++){
    for(let j=i; j<n; j++){
        // 时间复杂度O(1)的算法
        ...
    }
}

上面的代码中，内循环的中是j=i。具体的算法过程如下：

n+(n-1)+(n-2)+(n-3)+……+1
=(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+……
=(n+1)+(n+1)+(n+1)+(n+1)+……
=(n+1)n/2
=n(n+1)/2
=n²/2+n/2

根据上面说的推导大O阶的规则，得到上面这段代码的时间复杂度是O(n²)。

其他常见复杂度： f(n)=nlogn时，时间复杂度为O(nlogn)，可以称为nlogn阶。 f(n)=n³时，时间复杂度为O(n³)，可以称为立方阶。 f(n)=2ⁿ时，时间复杂度为O(2ⁿ)，可以称为指数阶。 f(n)=n!时，时间复杂度为O(n!)，可以称为阶乘阶。 f(n)=(√n时，时间复杂度为O(√n)，可以称为平方根阶。

最后总结一下，算法的效率是依据时间复杂度的大小决定的，最快的三个是常数阶O(1)、对数阶O(logn)、O(n)线性阶。

2.JavaScript数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互直接存在一种或多种特殊关系的数据元素的集合。通常情况下，精心选择数据结构可以带来更高的运行或者存储效率。作为一名程序猿，更需要了解下数据结构。

讲到数据结构，我们都会谈到线性结构和非线性结构。 1.线性结构是一个有序数据元素的集合。它应该满足下面的特征：

• 集合中必存在唯一的一个“第一个元素”
• 集合中必存在唯一的一个“最后的元素”
• 除最后一元素之外，其它数据元素均有唯一的“后继”
• 除第一个元素之外，其它数据元素均有唯一的“前驱”

符合条件的数据结构就有栈、队列...

2.非线性结构其特征是一个节点元素可以有多个直接前驱或多个直接后继。

符合条件的数据结构就有图、树...

嗯～了解一下就行。我们进入正题，数据结构大致分为九大类：

• 数组(Array)
• 栈(Stack)
• 队列(Queue)
• 链表(Linked)
• 字典(Dictionary)
• 集合(Set)
• 散列表/哈希表(Hash)
• 二叉查找树(Binary Sort Tree)
• 图(Graph)

2.1.数组(Array)

数组是一种线性结构，以十二生肖（鼠、牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪）排序为例：

来创建一个数组并打印出结果就一目了然了：

let arr = ['鼠', '牛', '虎', '兔', '龙', '蛇', '马', '羊', '猴', '鸡', '狗', '猪'];
arr.forEach((item, index) => {
	console.log(`[ ${index} ] => ${item}`);
});

// [ 0 ] => 鼠
// [ 1 ] => 牛
// [ 2 ] => 虎
// [ 3 ] => 兔
// [ 4 ] => 龙
// [ 5 ] => 蛇
// [ 6 ] => 马
// [ 7 ] => 羊
// [ 8 ] => 猴
// [ 9 ] => 鸡
// [ 10 ] => 狗
// [ 11 ] => 猪

我们提及的数据结构类似数组的声明，后面讲到的数据结构或多或少有数组的影子。

2.2.栈(Stack)

栈是一种后进先出线性表，是一种基于数组的数据结构。

• 后进先出，后进来的元素第一个弹出栈空间。类似于自动餐托盘，最后放上去的托盘，往往先被拿出来使用。
• 仅允许在表的一端进行插入和移除元素。这一端被称为栈顶，相对地，把另一端称为栈底。如下图的标识。
• 向一个栈插入新元素称作进栈、入栈或压栈，这是将新元素放在栈顶元素上面，使之成为新的栈顶元素。
• 从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

代码写下，熟悉下栈，我们定义一个Stack类，写几个方法：

class Stack {
    constructor(){
        this.items = [];
    }
    // 入栈操作
    push(element = ''){
        if(!element) return;
        this.items.push(element);
        return this;
    }
    // 出栈操作
    pop(){
        this.items.pop();
        return this;
    }
    // 对栈一瞥，理论上只能看到栈顶或者说即将处理的元素
    peek(){
        return this.items[this.size() - 1];
    }
    // 打印栈数据
    print(){
        return this.items.join(' ');
    }
    // 栈是否为空
    isEmpty(){
        return this.items.length == 0;
    }
    // 返回栈的元素个数
    size(){
        return this.items.length;
    }
}

let stack = new Stack(),
    arr = ['鼠', '牛', '虎', '兔', '龙', '蛇', '马', '羊', '猴', '鸡', '狗', '猪'];
arr.forEach(item => {
    stack.push(item);
});
console.log(stack.print()); // 鼠 牛 虎 兔 龙 蛇 马 羊 猴 鸡 狗 猪
console.log(stack.peek()); // 猪
stack.pop().pop().pop().pop();
console.log(stack.print()); // 鼠 牛 虎 兔 龙 蛇 马 羊
console.log(stack.isEmpty()); // false
console.log(stack.size()); // 8

2.3.队列(Queue)

队列是一种先进先出受限的线性表。受限体现于其允许在表的前端进行删除操作，在表的末尾进行插入【优先队列这些排除在外】操作。

代码写下，熟悉下队列，我们定义一个Queue类，写几个方法：：

class Queue {
    constructor(){
        this.items = [];
    }
    // 入队操作
    enqueue(element = ''){
        if(!element) return;
        this.items.push(element);
        return this;
    }
    // 出队操作
    dequeue(){
        this.items.shift();
        return this;
    }
    // 查看队前元素或者说即将处理的元素
    front(){
        return this.items[0];
    }
    // 查看队列是否为空
    isEmpty(){
        return this.items.length == 0;
    }
    // 查看队列的长度
    len(){
        return this.items.length;
    }
    // 打印队列数据
    print(){
        return this.items.join(' ');
    }
}

let queue = new Queue(),
    arr = ['鼠', '牛', '虎', '兔', '龙', '蛇', '马', '羊', '猴', '鸡', '狗', '猪'];
arr.forEach(item => {
    queue.enqueue(item);
});
console.log(queue.print()); // 鼠 牛 虎 兔 龙 蛇 马 羊 猴 鸡 狗 猪
console.log(queue.isEmpty()); // false
console.log(queue.len()); // 12
queue.dequeue().dequeue();
console.log(queue.front()); // 虎
console.log(queue.print()); // 虎 兔 龙 蛇 马 羊 猴 鸡 狗 猪

2.4.链表(Linked)

在进入正题之前，我们先来聊聊数组的优缺点。 优点：

• 存储多个元素，比较常用
• 访问便捷，使用下标[index]即可访问

缺点：

• 数组的创建通常需要申请一段连续的内存空间，并且大小是固定的，所以在进行扩容的时候难以掌控。（一般情况下，申请一个更大的数组，会是之前数组的倍数，比如两倍。然后，再将原数组中的元素复制过去）
• 插入数据越是靠前，其成本很高，因为需要进行大量元素的位移。

相对数组，链表亦可以存储多个元素，而且存储的元素在内容中不必是连续的空间；在插入和删除数据时，时间复杂度可以达到O(1)。在查找元素的时候，还是需要从头开始遍历的，但比数组快...

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。如上图。下面用代码实现下：

// 链表
class Node {
    constructor(element){
        this.element = element;
        this.next = null;
    }
}

class LinkedList {
    constructor(){
        this.length = 0; // 链表长度
        this.head = new Node('head'); // 表头节点
    }
    /**
     * @method find 查找元素的功能，找不到的情况下直接返回链尾节点
     * @param { String } item 要查找的元素
     * @return { Object } 返回查找到的节点 
     */
    find(item = ''){
        let currNode = this.head;
        while(currNode.element != item && currNode.next){
            currNode = currNode.next;
        }
        return currNode;
    }
    /**
    * @method findPrevious 查找链表指定元素的前一个节点
    * @param { String } item 指定的元素
    * @return { Object } 返回查找到的之前元素的前一个节点，找不到节点的话返回链尾节点
    */
    findPrevious(item){
        let currNode = this.head;
        while((currNode.next != null) && (currNode.next.element != item)){
            currNode = currNode.next;
        }
        return currNode;
    }
    /**
     * @method insert 插入功能
     * @param { String } newElement 要出入的元素
     * @param { String } item 想要追加在后的元素（此元素不一定存在）
     */
    insert(newElement = '', item){
        if(!newElement) return;
        let newNode = new Node(newElement),
            currNode = this.find(item);
        newNode.next = currNode.next;
        currNode.next = newNode;
        this.length++;
        return this;
    }
    // 展示链表元素
    display(){
        let currNode = this.head,
            arr = [];
        while(currNode.next != null){
            arr.push(currNode.next.element);
            currNode = currNode.next;
        }
        return arr.join(' ');
    }
    // 链表的长度
    size(){
        return this.length;
    }
    // 查看链表是否为空
    isEmpty(){
        return this.length == 0;
    }
    /**
     * @method indexOf 查看链表中元素的索引
     * @param { String } element 要查找的元素
     */
    indexOf(element){
        let currNode = this.head,
            index = 0;
        while(currNode.next != null){
            index++;
            if(currNode.next.element == element){
                return index;
            }
            currNode = currNode.next;
        }
        return -1;
    }
    /**
     * @method removeEl 移除指定的元素
     * @param { String } element 
     */
    removeEl(element){
        let preNode = this.findPrevious(element);
        preNode.next = preNode.next != null ? preNode.next.next : null;
    }
}

let linkedlist = new LinkedList();
console.log(linkedlist.isEmpty()); // true
linkedlist.insert('鼠').insert('虎').insert('牛', '鼠');
console.log(linkedlist.display()); // 鼠 牛 虎
console.log(linkedlist.find('猪')); // Node { element: '虎', next: null }
console.log(linkedlist.find('鼠')); // Node { element: '鼠', next: Node { element: '牛', next: Node { element: '虎', next: null } } }
console.log(linkedlist.size()); // 3
console.log(linkedlist.indexOf('鼠')); // 1
console.log(linkedlist.indexOf('猪')); // -1
console.log(linkedlist.findPrevious('虎')); // Node { element: '牛', next: Node { element: '虎', next: null } }
linkedlist.removeEl('鼠');
console.log(linkedlist.display()); // 牛 虎

2.5.字典(Dictionary)

字典的主要特点是键值一一对应的关系。可以比喻成我们现实学习中查不同语言翻译的字典。这里字典的键（key）理论上是可以使用任意的内容，但还是建议语意化一点，比如下面的十二生肖图：

class Dictionary {
    constructor(){
        this.items = {};
    }
    /**
     * @method set 设置字典的键值对
     * @param { String } key 键
     * @param {*} value 值
     */
    set(key = '', value = ''){
        this.items[key] = value;
        return this;
    }
    /**
     * @method get 获取某个值
     * @param { String } key 键
     */
    get(key = ''){
        return this.has(key) ? this.items[key] : undefined;
    }
    /**
     * @method has 判断是否含有某个键的值
     * @param { String } key 键
     */
    has(key = ''){
        return this.items.hasOwnProperty(key);
    }
    /**
     * @method remove 移除元素
     * @param { String } key 
     */
    remove(key){
        if(!this.has(key))  return false;
        delete this.items[key];
        return true;
    }
    // 展示字典的键
    keys(){
        return Object.keys(this.items).join(' ');
    }
    // 字典的大小
    size(){
        return Object.keys(this.items).length;
    }
    // 展示字典的值
    values(){
        return Object.values(this.items).join(' ');
    }
    // 清空字典
    clear(){
        this.items = {};
        return this;
    }
}

let dictionary = new Dictionary(),
    // 这里需要修改
    arr = [{ key: 'mouse', value: '鼠'}, {key: 'ox', value: '牛'}, {key: 'tiger', value: '虎'}, {key: 'rabbit', value: '兔'}, {key: 'dragon', value: '龙'}, {key: 'snake', value: '蛇'}, {key: 'horse', value: '马'}, {key: 'sheep', value: '羊'}, {key: 'monkey', value: '猴'}, {key: 'chicken', value: '鸡'}, {key: 'dog', value: '狗'}, {key: 'pig', value: '猪'}];
    arr.forEach(item => {
        dictionary.set(item.key, item.value);
    });
console.log(dictionary.keys()); // mouse ox tiger rabbit dragon snake horse sheep monkey chicken dog pig
console.log(dictionary.values()); // 鼠 牛 虎 兔 龙 蛇 马 羊 猴 鸡 狗 猪
console.log(dictionary.has('dragon')); // true
console.log(dictionary.get('tiger')); // 虎
console.log(dictionary.remove('pig')); // true
console.log(dictionary.size()); // 11
console.log(dictionary.clear().size()); // 0

2.6.集合(Set)

集合通常是由一组无序的，不能重复的元素构成。 一些常见的集合操作如图：

ES6中已经封装好可用的Set类。我们手动来写下相关的逻辑：

// 集合
class Set {
    constructor(){
        this.items = [];
    }
    /**
     * @method add 添加元素
     * @param { String } element 
     * @return { Boolean }
     */
    add(element = ''){
        if(this.items.indexOf(element) >= 0) return false;
        this.items.push(element);
        return true;
    }
    // 集合的大小
    size(){
        return this.items.length;
    }
    // 集合是否包含某指定元素
    has(element = ''){
        return this.items.indexOf(element) >= 0;
    }
    // 展示集合
    show(){
        return this.items.join(' ');
    }
    // 移除某个元素
    remove(element){
        let pos = this.items.indexOf(element);
        if(pos < 0) return false;
        this.items.splice(pos, 1);
        return true;
    }
    /**
     * @method union 并集
     * @param { Array } set 数组集合
     * @return { Object } 返回并集的对象
     */
    union(set = []){
        let tempSet = new Set();
        for(let i = 0; i < this.items.length; i++){
            tempSet.add(this.items[i]);
        }
        for(let i = 0; i < set.items.length; i++){
            if(tempSet.has(set.items[i])) continue;
            tempSet.items.push(set.items[i]);
        }
        return tempSet;
    }
    /**
     * @method intersect 交集
     * @param { Array } set 数组集合
     * @return { Object } 返回交集的对象
     */
    intersect(set = []){
        let tempSet = new Set();
        for(let i = 0; i < this.items.length; i++){
            if(set.has(this.items[i])){
                tempSet.add(this.items[i]);
            }
        }
        return tempSet;
    }
    /**
     * @method isSubsetOf 【A】是【B】的子集❓
     * @param { Array } set 数组集合
     * @return { Boolean } 返回真假值
     */
    isSubsetOf(set = []){
        if(this.size() > set.size()) return false;
        this.items.forEach*(item => {
            if(!set.has(item)) return false;
        });
        return true;
    }
}

let set = new Set(),
    arr = ['鼠', '牛', '虎', '兔', '龙', '蛇', '马', '羊', '猴'];
arr.forEach(item => {
    set.add(item);
});
console.log(set.show()); // 鼠 牛 虎 兔 龙 蛇 马 羊 猴
console.log(set.has('猪')); // false
console.log(set.size()); // 9
set.remove('鼠');
console.log(set.show()); // 牛 虎 兔 龙 蛇 马 羊 猴
let setAnother = new Set(),
    anotherArr = ['马', '羊', '猴', '鸡', '狗', '猪'];
anotherArr.forEach(item => {
    setAnother.add(item);
});
console.log(set.union(setAnother).show()); // 牛 虎 兔 龙 蛇 马 羊 猴 鸡 狗 猪
console.log(set.intersect(setAnother).show()); // 马 羊 猴
console.log(set.isSubsetOf(setAnother)); // false

2.7.散列表/哈希表(Hash)

散列是一种常用的存储技术，散列使用的数据结构叫做散列表/哈希表。在散列表上插入、删除和取用数据都非常快，但是对于查找操作来说却效率低下，比如查找一组数据中的最大值和最小值。查找的这些操作得求助其它数据结构，比如下面要讲的二叉树。

切入个案例感受下哈希表： 假如一家公司有1000个员工, 现在我们需要将这些员工的信息使用某种数据结构来保存起来。你会采用什么数据结构呢？ 方案一：数组

• 按照顺序将所有员工信息依次存入一个长度为1000的数组中。每个员工的信息都保存在该数组的某个位置上。
• 但是我们要查看某个员工的信息怎么办呢？一个个查找吗？不太好找。
• 数组最大的优势是什么？通过下标值获取信息。
• 所以为了可以通过数组快速定位到某个员工，最好给员工信息中添加一个员工编号，而编号对应的就是员工的下标值。
• 当查找某个员工信息时，通过员工号可以快速定位到员工的信息位置。

方案二：链表

• 链表对应插入和删除数据有一定的优势。
• 但是对于获取员工的信息，每次都必须从头遍历到尾，这种方式显然不是特别适合我们这里。

最终方案：

• 这么看最终方案似乎就是数组了，但是数组还是有缺点，什么缺点呢？
• 假如我们想查看下张三这位员工的信息，但是我们不知道张三的员工编号，怎么办呢？
• 当然，我们可以问他的员工编号。但是我们每查找一个员工都是要问一下这个员工的编号吗？不合适。【那我们还不如直接问他的信息嘞】
• 能不能有一种办法，让张三的名字和他的员工编号产生直接的关系呢？
• 也就是通过张三这个名字，我们就能获取到他的索引值，而再通过索引值我们就能获取张三的信息呢？
• 这样的方案已经存在了，就是使用哈希函数，让某个key的信息和索引值对应起来。

那么散列表的原理和实现又是怎样的呢，我们来聊聊。 我们的哈希表是基于数组完成的，我们从数组这里切入解析下。数组可以通过下标直接定位到相应的空间，哈希表的做法就是类似的实现。哈希表把key(键)通过一个固定的算法函数（此函数称为哈希函数/散列函数）转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value(值)存储在以该数字为下标的数组空间里，而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value。

结合下面的代码，也许你会更容易理解：

// 哈希表
class HashTable {
    constructor(){
        this.table = new Array(137);
    }
    /**
     * @method hashFn 哈希函数
     * @param { String } data 传入的字符串
     * @return { Number } 返回取余的数字
     */
    hashFn(data){
        let total = 0;
        for(let i = 0; i < data.length; i++){
            total += data.charCodeAt(i);
        }
        return total % this.table.length;
    }
    /**
     * 
     * @param { String } data 传入的字符串
     */
    put(data){
        let pos = this.hashFn(data);
        this.table[pos] = data;
        return this;
    }
    // 展示
    show(){
        this.table && this.table.forEach((item, index) => {
            if(item != undefined){
                console.log(index + ' => ' + item);
            }
        })
    }
    // ...获取值get函数等看官感兴趣的话自己补充测试啦
}

let hashtable = new HashTable(),
    arr = ['mouse', 'ox', 'tiger', 'rabbit', 'dragon', 'snake', 'horse', 'sheep', 'monkey', 'chicken', 'dog', 'pig'];
arr.forEach(item => {
    hashtable.put(item);
});
hashtable.show();
// 5 => mouse
// 40 => dog
// 46 => pig
// 80 => rabbit
// 87 => dragon
// 94 => ox
// 111 => monkey
// 119 => snake
// 122 => sheep
// 128 => tiger
// 134 => horse

// 那么问题来了，十二生肖里面的_小鸡_去哪里了呢❓
// 被_小萌狗_给覆盖了，因为其位置都是40（这个可以自己证明下）
// 问题又来了，那么应该如何解决这种被覆盖的冲突呢❓

针对上面的问题，我们存储数据的时候，产生冲突的话我们可以像下面这样解决： 1. 线性探测法 当发生碰撞（冲突）时，线性探测法检查散列表中的下一个位置【有可能非顺序查找位置，不一定是下一个位置】是否为空。如果为空，就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为止。该技术是基于一个事实：每个散列表都有很多空的单元格，可以使用它们存储数据。

2. 开链法 但是，当发生碰撞时，我们任然希望将key（键）存储到通过哈希函数产生的索引位置上，那么我们可以使用开链法。开链法是指实现哈希表底层的数组中，每个数组元素又是一个新的数据结构，比如另一个数组（这样结合起来就是二位数组了），链表等，这样就能存储多个键了。使用这种技术，即使两个key（键）散列后的值相同，依然是被保存在同样的位置，只不过它们是被保存在另一个数据结构上而已。以另一个数据结构是数组为例，存储的数据如下：

2.8.二叉查找树(Binary Sort Tree)

树的定义：

• 树（Tree）：n(n >= 0)个节点构成的有限集合。
  • 当n = 0时，称为空树；
  • 对任意一棵空树(n > 0)，它具备以下性质：
  • 树中有一个称为**根(Root)**的特殊节点，用r(root)表示；
  • 其余节点可分为m(m > 0)个互不相交的有限集T1,T2,...Tm，其中每个集合本省又是一棵树，称为原来树的子树（SubTree）
  • 注意：
    • 子树之间不可以相交；
    • 除了根节点外，每个节点有且仅有一个父节点；
    • 一个N个节点的树有N-1条边。

树的术语：

• 节点的度（Degree）：节点的子树个数。
• 树的度：树的所有节点中最大的度数（树的度通常为节点个数的N-1）。
• 叶节点（Leaf）：度为0的节点（也称叶子节点）。
• 父节点（Parent）：有子树的节点是其子树的父节点。
• 子节点（Child）：若A节点是B节点的父节点，则称B节点是A节点的子节点。
• 兄弟节点（Sibling）：具有同一个父节点的各节点彼此是兄弟节点。
• 路径和路径长度：从节点n1到nk的路径为一个节点序列n1,n2,n3,...,nk，ni是ni+1的父节点。路径所包含边的个数为路径长度。
• 节点的层次（Level）：规定根节点在第0层，它的子节点是第1层，子节点的子节点是第2层，以此类推。
• 树的深度（Depth）：树中所有节点中的最大层次是这棵树的深度（因为上面是从第0层开始，深度 = 第最大层数 + 1）

如下图：

二叉树的定义：

• 二叉树可以为空，也就是没有节点
• 二叉树若不为空，则它是由根节点和称为其左子树TL和右子树RT的两个不相交的二叉树组成
• 二叉树每个节点的子节点不允许超过两个

二叉树的五种形态：

• 空
• 只有根节点
• 只有左子树
• 只有右子树
• 左右子树均有

对应下图（从左至右）：

我们接下来要讲的是二叉查找树（BST，Binary Search Tree）。二叉查找树，也称二叉搜索树或二叉排序树，是一种特殊的二叉树，相对值较小的值保存在左节点中，较大的值保存在右节点中。二叉查找树特殊的结构使它能够快速的进行查找、插入和删除数据。下面我们来实现下：

// 二叉查找树
// 辅助节点类
class Node {
    constructor(data, left, right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
    // 展示节点信息
    show(){
        return this.data;
    }
}
class BST {
    constructor(){
        this.root = null;
    }
    // 插入数据
    insert(data){
        let n = new Node(data, null, null);
        if(this.root == null){
            this.root = n;
        }else{
            let current = this.root,
                parent = null;
            while(true){
                parent = current;
                if(data < current.data){
                    current = current.left;
                    if(current == null){
                        parent.left = n;
                        break;
                    }
                }else{
                    current = current.right;
                    if(current == null){
                        parent.right = n;
                        break;
                    }
                }
            }
        }
        return this;
    }
    // 中序遍历
    inOrder(node){
        if(!(node == null)){
            this.inOrder(node.left);
            console.log(node.show());
            this.inOrder(node.right);
        }
    }
    //   先序遍历
    preOrder(node){
        if(!(node == null)){
            console.log(node.show());
            this.preOrder(node.left);
            this.preOrder(node.right);
        }
    }
    // 后序遍历
    postOrder(node){
        if(!(node == null)){
            this.postOrder(node.left);
            this.postOrder(node.right);
            console.log(node.show());
        }
    }
    // 获取最小值
    getMin(){
        let current = this.root;
        while(!(current.left == null)){
            current = current.left;
        }
        return current.data;
    }
    // 获取最大值
    getMax(){
        let current = this.root;
        while(!(current.right == null)){
            current = current.right;
        }
        return current.data;
    }
    // 查找给定的值
    find(data){
        let current = this.root;
        while(current != null){
            if(current.data == data){
                return current;
            }else if(data < current.data){
                current = current.left;
            }else{
                current = current.right;
            }
        }
        return null;
    }
    // 移除给定的值
    remove(data){
        root = this.removeNode(this.root, data);
        return this;
    }
    // 移除给定值的辅助函数
    removeNode(node, data){
        if(node == null){
            return null;
        }
        if(data == node.data){
            // 叶子节点
            if(node.left == null && node.right == null){
                return null; // 此节点置空
            }
            // 没有左子树
            if(node.left == null){
                return node.right;
            }
            // 没有右子树
            if(node.right == null){
                return node.left;
            }
            // 有两个子节点的情况
            let tempNode = this.getSmallest(node.right); // 获取右子树
            node.data = tempNode.data; // 将其右子树的最小值赋值给删除的那个节点值
            node.right = this.removeNode(node.right, tempNode.data); // 删除指定节点的下的最小值，也就是置其为空
            return node;
        }else if(data < node.data){
            node.left = this.removeNode(node.left, data);
            return node;
        }else{
            node.right = this.removeNode(node.right, data);
            return node;
        }
    }
    // 获取给定节点下的二叉树最小值的辅助函数
    getSmallest(node){
        if(node.left == null){
            return node;
        }else{
            return this.getSmallest(node.left);
        }
    }
}

let bst = new BST();
bst.insert(56).insert(22).insert(10).insert(30).insert(81).insert(77).insert(92);
bst.inOrder(bst.root); // 10, 22, 30, 56, 77, 81, 92
console.log('--中序和先序遍历分割线--');
bst.preOrder(bst.root); // 56, 22, 10, 30, 81, 77, 92
console.log('--先序和后序遍历分割线--');
bst.postOrder(bst.root); // 10, 30, 22, 77, 92, 81, 56
console.log('--后序遍历和获取最小值分割线--');
console.log(bst.getMin()); // 10
console.log(bst.getMax()); // 92
console.log(bst.find(22)); // Node { data: 22, left: Node { data: 10, left: null, right: null }, right: Node { data: 30, left: null, right: null } }
// 我们删除节点值为22，然后用先序的方法遍历，如下
console.log('--移除22的分割线--')
console.log(bst.remove(22).inOrder(bst.root)); // 10, 30, 56, 77, 81, 92

看了上面的代码之后，你是否有些懵圈呢？我们借助几张图来了解下，或许你就豁然开朗了。

在遍历的时候，我们分为三种遍历方法--先序遍历，中序遍历和后序遍历：

删除节点是一个比较复杂的操作，考虑的情况比较多：

• 该节点没有叶子节点的时候，直接将该节点置空
• 该节点只有左子树，直接将该节点赋予左子树
• 该节点只有右子树，直接将该节点赋予右子树
• 该节点左右子树都有，有两种方法可以处理
  • 方案一：从待删除节点的左子树找节点值最大的节点A，替换待删除节点值，并删除节点A
  • 方案二：从待删除节点的右子树找节点值最小的节点A，替换待删除节点值，并删除节点A【上面的示例代码中就是这种方案】

删除两个节点的图解如下：

2.9.图(Graph)

图由边的集合及顶点的集合组成。 我们来了解下图的相关术语：

• 顶点：图中的一个节点。
• 边：表示顶点和顶点之间的连线。
• 相邻顶点：由一条边连接在一起的顶点称为相邻顶点。
• 度：一个顶点的度是相邻顶点的数量。比如0顶点和其它两个顶点相连，0顶点的度就是2
• 路径：路径是顶点v1,v2...,vn的一个连续序列。
  • 简单路径：简单路径要求不包含重复的顶点。
  • 回路：第一个顶点和最后一个顶点相同的路径称为回路。
• 有向图和无向图
  • 有向图表示图中的边是有方向的。
  • 无向图表示图中的边是无方向的。
• 带权图和无权图
  • 带权图表示图中的边有权重。
  • 无权图表示图中的边无权重。

如下图：

图可以用于现实中的很多系统建模，比如： 对交通流量建模

• 顶点可以表示街道的十字路口, 边可以表示街道.
• 加权的边可以表示限速或者车道的数量或者街道的距离.
• 建模人员可以用这个系统来判定最佳路线以及最可能堵车的街道.

图既然这么方便，我们来用代码实现下：

// 图
class Graph{
    constructor(v){
        this.vertices = v; // 顶点个数
        this.edges = 0; // 边的个数
        this.adj = []; // 邻接表或邻接表数组
        this.marked = []; // 存储顶点是否被访问过的标识
        this.init();
    }
    init(){
        for(let i = 0; i < this.vertices; i++){
            this.adj[i] = [];
            this.marked[i] = false;
        }
    }
    // 添加边
    addEdge(v, w){
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
        return this;
    }
    // 展示图
    showGraph(){
        for(let i = 0; i < this.vertices; i++){
            for(let j = 0; j < this.vertices; j++){
                if(this.adj[i][j] != undefined){
                    console.log(i +' => ' + this.adj[i][j]);
                }
            }
        }
    }
    // 深度优先搜索
    dfs(v){
        this.marked[v] = true;
        if(this.adj[v] != undefined){
            console.log("visited vertex: " + v);
        }
        this.adj[v].forEach(w => {
            if(!this.marked[w]){
                this.dfs(w);
            }
        })
    }
    // 广度优先搜索
    bfs(v){
        let queue = [];
        this.marked[v] = true;
        queue.push(v); // 添加到队尾
        while(queue.length > 0){
            let v = queue.shift(); // 从对首移除
            if(v != undefined){
                console.log("visited vertex: " + v);
            }
            this.adj[v].forEach(w => {
                if(!this.marked[w]){
                    this.marked[w] = true;
                    queue.push(w);
                }
            })
        }
    }
}

let graphFirstInstance = new Graph(5);
graphFirstInstance.addEdge(0, 1).addEdge(0, 2).addEdge(1, 3).addEdge(2, 4);
graphFirstInstance.showGraph();
// 0 => 1
// 0 => 2
// 1 => 0
// 1 => 3
// 2 => 0
// 2 => 4
// 3 => 1
// 4 => 2
// 为什么会出现这种数据呢？它对应的图是什么呢？可以思考下，动手画画图什么的
console.log('--展示图和深度优先搜索的分隔线--');
graphFirstInstance.dfs(0); // 从顶点 0 开始的深度搜索
// visited vertex: 0
// visited vertex: 1
// visited vertex: 3
// visited vertex: 2
// visited vertex: 4
console.log('--深度优先搜索和广度优先搜索的分隔线--');
let graphSecondInstance = new Graph(5);
graphSecondInstance.addEdge(0, 1).addEdge(0, 2).addEdge(1, 3).addEdge(2, 4);
graphSecondInstance.bfs(0); // 从顶点 0 开始的广度搜索
// visited vertex: 0
// visited vertex: 1
// visited vertex: 2
// visited vertex: 3
// visited vertex: 4

对于搜索图，在上面我们介绍了深度优先搜索 - DFS（Depth First Search）和广度优先搜索 - BFS（Breadth First Search），结合下面的图再回头看下上面的代码，你会更加容易理解这两种搜索图的方式。

3.基本算法

上一章主要是讲解数据结构，本章主要讲解的是基本算法，算法真的太多太多，只能抛转引入。 常见的算法：

• 排序算法
  • 冒泡排序
  • 选择排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序
• 搜索算法
  • 顺序查找
  • 二分查找算法
• Diff算法

3.1.排序算法

排序介绍：一旦我们将数据放置在某个数据结构（比如数组）中存储起来后，就可以根据需求对数据进行不同方式的排序：比如对姓名按字母排序，对商品按照价格排序... 排序算法又分为简单排序和高级排序。 简单排序包括冒泡排序、选择排序和插入排序。 高级排序包括希尔排序、归并排序和快速排序。 以上写出了六种排序的算法，当然还有其它的排序算法，你可以到《九大经典排序算法》文章中查看。

3.1.1.冒泡排序

之所以叫冒泡排序，是因为使用这种排序算法时，数据值就会像气泡那样从数组的一端漂浮到另一端。 假设正在将一组数字按照升序排列，较大的值会浮动在数组的右侧，而较小的值则会浮动到数组的左侧。 产生这种冒泡的现象是因为算法会多次在数组中移动过，比较相邻的数据，当左侧值大于右侧值的时候将它们互换。

后面讲到的排序算法如无说明，则默认为升序

比如下面的简单列表的例子。 E A D B H 经过第一次的排序后，列表会变成： A E D B H 前面两个元素进行了交互。接下来再次排序： A D E B H 第二个元素和第三个元素进行了交互。继续进行排序： A D B E H 第三个元素和第四个元素进行了交换。这一轮最后进行排序： A D B E H 因为第四个元素比最后一个元素小，所以比较后保持所在位置。反复对第一个元素执行上面的操作（已经固定的值不参与排序，如第一轮固定的H不参与第二轮的比较了），得到如下的最终结果： A B D E H 相关的动效图如下：

关键代码如下：

class Sequence{
    constructor(arr){
        this.arr = arr;
    }

    /**
     * @method swap 交换两个元素
     * @param { Number } index1 元素的索引值1
     * @param { Number } index2 元素的索引值2
     */
    swap(index1, index2){
        let aux = this.arr[index1];// 临时变量
        this.arr[index1] = this.arr[index2];
        this.arr[index2] = aux;
    }

    // 冒泡排序
    bubbleSort(){
        let numElements = this.arr.length;
        for(let outer = numElements-1; outer >= 2; --outer){
            for(let inner = 0; inner <= outer-1; ++inner){
                if(this.arr[inner] > this.arr[inner+1]){
                    this.swap(inner, inner+1);
                }
            }
        }
    }
}

运行如下：

let bubbleDemo = new Sequence([12, 30, 6, 8, 4, 10, 9, 100, 30, 60]);
bubbleDemo.bubbleSort();
bubbleDemo.arr; // [4,6,8,9,10,12,30,30,60,100]

3.1.2.选择排序

选择排序从数组的开头开始，将第一个元素和其它元素进行比较。检查完所有的元素之后，最小的元素会被放在数组的第一个位置，然后算法会从第二个位置继续。 这个过程进行到数组的倒数第二个位置时，所有的数据便完成了排序。

原理：选择排序用到双层嵌套循环。外循环从数组的第一个元素移动到倒数第二个元素；内循环从当前外循环所指元素的第二个元素开始移动到最后一个元素，查找比当前外循环所指元素小的元素。每次内循环迭代后，数组中最小的值都会被赋值到合适的位置。

下面是对五个元素的列表进行选择排序的简单例子。初始列表为： E A D H B 第一次排序会找到最小值，并将它和列表的第一个元素进行交换： A E D H B 接下查找第一个元素后面的最小值（第一个元素此时已经就位），并对它们进行交换： A B D H E D已经就位，因此下一步会对E H进行互换，列表已按顺序排列好如下： A B D E H 通过gif图可能容易理解：

关键代码如下：

class Sequence{
    constructor(arr){
        this.arr = arr;
    }

    /**
     * @method swap 交换两个元素
     * @param { Number } index1 元素的索引值1
     * @param { Number } index2 元素的索引值2
     */
    swap(index1, index2){
        let aux = this.arr[index1];
        this.arr[index1] = this.arr[index2];
        this.arr[index2] = aux;
    }
    
    // 选择排序
    selectionSort(){
        let min,
            numElements = this.arr.length;
        for(let outer = 0; outer <= numElements-2; outer++){
            min = outer;
            for(let inner = outer+1; inner <= numElements-1; inner++){
                if(this.arr[inner] < this.arr[min]){
                    min = inner;
                }
            }
            this.swap(outer, min);
        }
    }
}

运行代码如下：

let selectionDemo = new Sequence([8, 10, 80, 9, 6, 5, 5, 80]);
selectionDemo.selectionSort();
selectionDemo.arr; // [5,5,6,8,9,10,80,80]

3.1.3.插入排序

插入排序类似我们按照数字或字母的顺序对数据进行降序或升序排序整理～

原理：插入排序也用了双层的嵌套循环。外循环将数组挨个移动，而内循环则对外循环中选中的元素以及内循环数组后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素要小，那么内循环的数组元素会向右移动，腾出一个位置给外循环选定的元素。

上面表达的晦涩难懂。简单来说，插入排序就是未排序的元素对已经排序好的序列数据进行合适位置的插入。如果还是不懂，结合下面的排序示例来理解下： 下面对五个元素进行插入排序。初始列表如下： E B A H D 第一次插入排序，第二个元素挪动到第一位： B E A H D 第二次插入排序是对A进行操作： B A E H D A B E H D 第三次是对H进行操作，因为它比之前的元素都大，所以保持位置。最后一次是对D元素进行插入排序了，过程和最后结果如下： A B E D H A B D E H 相关的gif图了解一下：

关键代码如下：

class Sequence{
    constructor(arr){
        this.arr = arr;
    }
    
    // 插入排序
    insertionSort(){
        let temp,
            inner,
            numElements = this.arr.length;
        for(let outer = 1; outer <= numElements-1; outer++){
            temp = this.arr[outer];
            inner = outer;
            while(inner > 0 && this.arr[inner-1] >= temp){
                this.arr[inner] = this.arr[inner-1];
                inner--;
            }
            this.arr[inner] = temp;
        }
    }
}

运行代码如下：

let insertionDemo = new Sequence([100, 80, 98, 2, 5, 80, 8, 60]);
insertionDemo.insertionSort();
insertionDemo.arr; // [2,5,8,60,80,80,98,100]

3.1.4.希尔排序

希尔排序是插入排序的优化版，但是，其核心理念与插入排序不同，希尔排序会首先比较距离较远的元素，而非相邻的元素。

原理：希尔排序通过定义一个间隔序列来表示数据在排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过对于大部分的实际应用场景，算法用到的间隔序列可以提前定义好。

如下演示希尔排序中，间隔序列是如何运行的：

通过下面的gif图你也许会更好理解：

关键代码如下：

class Sequence{
    constructor(arr){
        this.arr = arr;
        this.gaps = [5, 3, 1]; // 用于希尔排序的间隔，️数组最后一个元素为1 
    }
    
    // 希尔排序
    shellSort(){
        let temp,
            j,
            numElements = this.arr.length;
        for(let g = 0; g < this.gaps.length; ++g){
            for(let i = this.gaps[g]; i < numElements; ++i){
                temp = this.arr[i];
                for(j = i; j >= this.gaps[g] && this.arr[j - this.gaps[g]] > temp; j -= this.gaps[g]){ // 之前的元素已经升序排好序的了
                    this.arr[j] = this.arr[j - this.gaps[g]];
                }
                this.arr[j] = temp; // 这里和上面的for循环是互换两个数据位置
            }
        }
    }
}

运行代码如下：

let shellDemo = new Sequence([6, 0, 2, 9, 3, 5, 8, 0, 5, 4]);
shellDemo.shellSort();
shellDemo.arr; // [0,0,2,3,4,5,5,6,8,9]

思考：[6, 0, 2, 9, 3, 5, 8, 0, 5, 4] 间隔为3的排序结果是什么呢？

3.1.5.归并排序

原理：把一系列的排好序的子序列合并成一个大的有序序列。从理论上讲，这个算法很容易实现。我们需要两个排好序的子数组，然后通过比较数据的大小，先从最小的数据开始插入，最后合并得到第三个数组。然而，实际上操作的相当大的数据的时候，使用归并排序是很耗内存的，这里我们了解一下就行。

实现归并排序一般有两种方法，一种是自顶向下和自底向上的方法。 上面的gif图是自顶向下的方法，那么何为自顶向下呢？

自顶向下的归并排序算法就是把数组元素不断的二分，直到子数组的元素个数为一个，因为这个时候子数组必定是有序的，然后再将两个有序的序列合并成一个新的有序序列，连个有序序列又可以合并成另一个新的有序序列，以此类推，直到合并一个有序的数组。如下图：

自底向上的归并排序算法的思想是将数组先一个一个归并成两两有序的序列，两两有序的序列归并成四个四个有序的序列，以此类推，直到归并的长度大于整个数组的长度，此时整个数组有序。

关键代码如下：

class Sequence{
    constructor(arr){
        this.arr = arr;
    }
    mergeSort() {
        this.arr = this.mergeSortMethod(this.arr)
    }
    // 归并排序
    mergeSortMethod ( arr ) {
        var len = arr.length;
        if( len < 2 ){
            return arr;
        }
        var middle = Math.floor(len / 2),
            left = arr.slice(0, middle),
            right = arr.slice(middle);
        return this.merge(this.mergeSortMethod(left), this.mergeSortMethod(right));
    }
    
    merge(left, right) {
        var result = [];
        while (left.length && right.length) {
            if (left[0] <= right[0]) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
        while (left.length)
            result.push(left.shift());
        while (right.length)
            result.push(right.shift());
        return result;
    }
}

运行代码如下：

let mergeDemo = new Sequence([4, 2, 1, 5, 7, 6, 3]);
mergeDemo.mergeSort();
mergeDemo.arr; // [1,2,3,4,5,6,7]

注意：数组按照归并长度划分，最后一个子数组可能不满足长度要求，这种情况就要特殊处理了。

3.1.6.快速排序

快速排序是处理大数据集最快的排序算法之一，时间复杂度 最好的情况也也是和归并排序一样，为O(nlogn)。

原理：快速排序是一种**分而治之（分治）**的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列，然后不断重复这个步骤，直到所有的数据都是有序的。

可以更清晰的表达快速排序算法步骤如下： 1.选择一个基准元素（pivot，枢纽），将列表分隔成两个子序列； 2.对列表重新排序，将所有小于基准值的元素放在基准值的前面，将所有大于基准值的元素放在基准值的后面； 3.分别对较小元素的子序列和较大元素的子序列重复步骤1 和 2。

关键代码如下：

class Sequence{
    constructor(arr){
        this.arr = arr;
    }
    
    // 快速排序
    quickSort(){
        this.arr = this.quickAux(this.arr);
    }

    // aux函数 - 快排的辅助函数
    quickAux(arr){
        let numElements = arr.length;
        if(numElements == 0){
            return [];
        }
        let left = [],
            right = [],
            pivot = arr[0]; // 取数组的第一个元素作为基准值
        for(let i = 1; i < numElements; i++){
            if(arr[i] < pivot){
                left.push(arr[i]);
            }else{
                right.push(arr[i]);
            }
        }
        return this.quickAux(left).concat(pivot, this.quickAux(right));
    }
}

运行代码如下：

let quickDemo = new Sequence([68, 80, 12, 80, 95, 70, 79, 27, 88, 93]);
quickDemo.quickSort();
quickDemo.arr; // [12,27,68,70,79,80,80,88,93,95]

至此，常见的六种排序算法就介绍完了。

3.2.搜索算法

在列表中查找数据有两种方式：顺序查找和二分查找。顺序查找适用于元素随机排列的列表；而二分查找适用于元素已排序的列表。二分查找效率更高，但是我们必须在进行查找之前花费额外的时间将列表中的元素进行排序。

3.2.1.顺序查找

对于查找数据来说，最简单的就是从列表中的第一个元素开始对列表元素逐个进行判断，直到找到了想要的元素，或者直到列表结尾也没有找到。这种方法称为顺序查找或者线性查找。

这种查找的代码实现方式很简单，如下：

/*
* @param { Array } arr 目标数组
* @param { Number } data 要查找的数组
* @return { Boolean } 是否查找成功
**/
function seqSearch(arr, data){
	for(let i = 0; i < arr.length; i++){
		if(arr[i] === data){
			return true;
		}
	}
	return false;
}

当然，看到上面的代码，你也许会简化成下面的这样的代码：

function seqSearch(arr, data){
	return arr.indexOf(data) >= 0 ? true : false;
}

实现的方式有多种，但是原理都是一样的，要从第一个元素开始遍历，有可能会遍历到最后一个元素都找不到要查找的元素。所以，这是一种暴力查找技巧的一种。

那么，有什么更加高效的查找方法嘛？这就是我们接下来要讲的了。

3.2.2.二分查找算法

在开始之前，我们来玩一个猜数字游戏：

• 规则：在数字1-100之间，你朋友选择要猜的数字之后，由你来猜数字。你每猜一个数字，你的朋友将会作出下面三种回应之一：
  • 猜对了
  • 猜大了
  • 猜小了

这个游戏很简单，如果我们使用二分查找的策略进行的话，我们只需要经过短短的几次就确定我们要查找的数据了。

那么二分查找的原理是什么呢？ 二分查找又称为折半查找，对有序的列表每次进行对半查找。就是这么简单@～@！

注意：二分查找的前提是数列必须是有序的。 特点：每个节点的key值大于左节点，小于右节点。

代码实现走一波：

/*
* @param { Array } arr 有序的数组 ⚠️注意：是有序的有序的有序的
* @param { Number } data 要查找的数据
* @return { Number } 返回查找到的位置，未查找到放回-1值
**/
function search (arr, data) {
    // 声明变量左节点、右节点，中间节点
    var left = 0,
        right = arr.length - 1, mid;
    // 左节点小于等于右节点则进入
    while(left <= right){
        mid = Math.floor((left + right) / 2);
        // 目标值与数组值相同，则返回下标
        if(data === arr[mid]){
            return mid;
        // 目标值大于数组值时，干掉左侧
        } else if(data > arr[mid]){
            left = mid + 1;
        } else {
        // 目标值小于数组值时，干掉右侧
            right = mid - 1;
        }
    }
    // 左节点大于右节点，表示没找到，返回-1
    return -1;
}

执行结果：

search([-1,0,3,5,9,12], 9) //返回4
search([-1,0,3,5,9,12], 2) //返回-1

3.3.Diff算法

在前端领域，目前最火的框架无非这两个，vue和react。 diff算法是一种优化手段，将前后两个模块进行差异对比，修补(更新)差异的过程叫做patch(打补丁)。 为什么vue,react这些框架中都会有diff算法呢? 我们都知道渲染真实dom的开销是很大的，这个跟性能优化中的**重绘重排**意义类似, 回到正题来, 有时候我们修改了页面中的某个数据，如果直接渲染到真实DOM中会引起整棵数的重绘重排, 那么我们能不能只让我们修改的数据映射到真实DOM, 做一个最少化重绘重排呢，说到这里你应该对为什么使用diff算法有一个简单的概念了

3.3.1 Vue Diff算法

在VirtualDOM方案被提出之后，社区中不断涌现出对diff的改进算： 最开始经典的深度优先遍历DFS算法，其复杂度为O(n^3)，存在高昂的diff成本，然后是cito.js的横空出世，它对今后所有虚拟DOM的算法都有重大影响。它采用两端同时进行比较的算法，将diff速度拉高到几个层次。紧随其后的是kivi.js，在cito.js的基出提出两项优化方案，使用key实现移动追踪及基于key的编辑长度距离算法应用（算法复杂度 为O(n^2)）。但这样的diff算法太过复杂了，于是后来者snabbdom.js将kivi.js进行简化，去掉编辑长度距离算法，调整两端比较算法，将算法复杂度降为O(n)。再之后，就是著名的vue2.0 把snabbdom整个库整合掉了。

vue目前的diff算法用的是snabbdom.js，与react的reconilation方式基本相同。

3.3.2 React Diff算法

react diff具体内容可以参考react官方文档reconilation： https://reactjs.org/docs/reconciliation.html

再说说react元老，React 中最值得称道的部分莫过于 Virtual DOM 与 diff 的完美结合，特别是其高效的 diff 算法，让用户可以无需顾忌性能问题而”任性自由”的刷新页面，让开发者也可以无需关心 Virtual DOM 背后的运作原理，因为 React diff 会帮助我们计算出 Virtual DOM 中真正变化的部分，并只针对该部分进行实际 DOM 操作，而非重新渲染整个页面，从而保证了每次操作更新后页面的高效渲染，因此 Virtual DOM 与 diff 是保证 React 性能口碑的幕后推手。

如果 React 只是单纯的引入 diff 算法而没有任何的优化改进，那么其效率是远远无法满足前端渲染所要求的性能。

因此，想要将 diff 思想引入 Virtual DOM，就需要设计一种稳定高效的 diff 算法，而 React 做到了。

3.3.3 Diff优化实现思路

大概解释下：当Virtual DOM发生变化的时，如上图的第二个和第三个 p 的sonx被删除了，这时候，我们就通过diff算法，计算出前后Virtual DOM的差异->补丁对象patches，然后根据这个patches对象中的信息来遍历之前的老Virtual DOM树，对其需要更新的地方进行更新，使其变成新VIrtual DOM。

有关具体的diff算法具体的实现，可参考文章： 《React源码分析与实现(三)：实操DOM Diff》， 地址：https://www.jianshu.com/p/7b580d2e51d5

最后，总结一下，JavaScript这门语言入门很容易，精通很难。JavaScript有太多值得去学习和深耕的地方，设计模式、数据结构、算法、各类框架及其衍生物... 能看完到最后的人都是好样的，希望对你们能有所帮助。