前端需要掌握的基础算法

目录

• • 排序
  • • 基本排序算法
    • 高级排序算法
    • 时间复杂度总结
    • 是否稳定
    • 辅助记忆
  • 递归
  • • Deep Clone
    • • 实战例题
  • 二叉树和二叉查找树
  • • 树的基本概念
    • 二叉查找树
    • • 二叉树的遍历
      • 二叉树的查找

排序

基本排序算法

基本排序的基本思想非常类似，重排列时用的技术基本都是一组嵌套的for循环: 外循环遍历数组的每一项，内循环则用于比较元素。

冒泡排序

function bubleSort(arr) {
    var len = arr.length;
    for (let outer = len ; outer >= 2; outer--) {
        for(let inner = 0; inner <=outer - 1; inner++) {
            if(arr[inner] > arr[inner + 1]) {
                let temp = arr[inner];
                arr[inner] = arr[inner + 1];
                arr[inner + 1] = temp;
            }
        }
    }
    return arr;
}

1. 外层循环，从最大值开始递减，因为内层是两两比较，因此最外层当>=2时即可停止；
2. 内层是两两比较，从0开始，比较inner与inner+1，因此，临界条件是inner<outer -1

优化如下：

//ES6解构赋值
function bubleSort(arr) {
    var len = arr.length;
    for (let outer = len ; outer >= 2; outer--) {
        for(let inner = 0; inner <=outer - 1; inner++) {
            if(arr[inner] > arr[inner + 1]) {
                [arr[inner],arr[inner+1]] = [arr[inner+1],arr[inner]]
            }
        }
    }
    return arr;
}

选择排序

选择排序是从数组的开头开始，将第一个元素和其他元素作比较，检查完所有的元素后，最小的放在第一个位置，接下来再开始从第二个元素开始，重复以上一直到最后。

function selectSort(arr) {
    var len = arr.length;
    for(let i = 0 ;i < len - 1; i++) {
        for(let j = i ; j<len; j++) {
            if(arr[j] < arr[i]) {
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr
}

1. 外层循环的i表示第几轮，arr[i]就表示当前轮次最靠前(小)的位置；
2. 内层从i开始，依次往后数，找到比开头小的，互换位置即可

插入排序

插入排序核心–扑克牌思想： 就想着自己在打扑克牌，接起来一张，放哪里无所谓，再接起来一张，比第一张小，放左边，继续接，可能是中间数，就插在中间…依次

function insertSort(arr) {
    for(let i = 1; i < arr.length; i++) {  //外循环从1开始，默认arr[0]是有序段
        for(let j = i; j > 0; j--) {  //j = i,将arr[j]依次插入有序段中
            if(arr[j] < arr[j-1]) {
                [arr[j],arr[j-1]] = [arr[j-1],arr[j]];
            } else {
                break;
            }
        }
    }
    return arr;
}

原理：

1. 首先将待排序的第一个记录作为一个有序段
2. 从第二个开始，到最后一个，依次和前面的有序段进行比较，确定插入位置

1. i是外循环，依次把后面的数插入前面的有序序列中，默认arr[0]为有序的，i就从1开始
2. j进来后，依次与前面队列的数进行比较，因为前面的序列是有序的，因此只需要循环比较、交换即可
3. 注意这里的break，因为前面是都是有序的序列，所以如果当前要插入的值arr[j]大于或等于arr[j-1]，则无需继续比较，直接下一次循环就可以了。

高级排序算法

快速排序

快排是处理大数据最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直至所有数据都是有序的。

原理：

1. 选择一个基准元素，将列表分割成两个子序列；
2. 对列表重新排序，将所有小于基准值的元素放在基准值前面，所有大于基准值的元素放在基准值的后面；
3. 分别对较小元素的子序列和较大元素的子序列重复步骤1和2

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;  //递归出口
    }
    var left = [],
        right = [],
        current = arr.splice(0,1); //注意splice后，数组长度少了一个
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < current) {
            left.push(arr[i])  //放在左边
        } else {
            right.push(arr[i]) //放在右边
        }
    }
    return quickSort(left).concat(current,quickSort(right)); //递归
}

希尔排序

希尔排序是插入排序的改良算法，但是核心理念与插入算法又不同，它会先比较距离较远的元素，而非相邻的元素。

insertSort(arr,[3,2,1]);
function shellSort(arr,gap) {
    console.log(arr)//为了方便观察过程，使用时去除
    for(let i = 0; i<gap.length; i++) {  //最外层循环，一次取不同的步长，步长需要预先给出
        let n = gap[i]; //步长为n
        for(let j = i + n; j < arr.length; j++) { //接下类和插入排序一样，j循环依次取后面的数
            for(let k = j; k > 0; k-=n) { //k循环进行比较，和直接插入的唯一区别是1变为了n
                if(arr[k] < arr[k-n]) {
                    [arr[k],arr[k-n]] = [arr[k-n],arr[k]];
                    console.log(`当前序列为[${arr}] \n 交换了${arr[k]}和${arr[k-n]}`)//为了观察过程
                } else {
                    continue;
                }
            }
        }
    }
    return arr;
}

直接看这个三层循环嵌套的内容，会稍显复杂，这也是为什么先把插入排序写在前面做一个对照。 其实三层循环的内两层完全就是一个插入排序，只不过原来插入排序间隔为1，而希尔排序的间隔是变换的n， 如果把n修改为1，就会发现是完全一样的了。

时间复杂度总结

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
冒泡排序	O(n²)	O(n²)	O(1)	是
选择排序	O(n²)	O(n²)	O(1)	不是
直接插入排序	O(n²)	O(n²)	O(1)	是
快速排序	O(nlogn)	O(n²)	O(logn)	不是
希尔序	O(nlogn)	O(n^s)	O(1)	不是

是否稳定

通俗的讲有两个相同的数A和B，在排序之前A在B的前面，而经过排序之后，B跑到了A的前面，对于这种情况的发生，我们管他叫做排序的不稳定性，而快速排序在对存在相同数进行排序时就有可能发生这种情况。

/*
比如对(5，3A，6，3B ) 进行排序，排序之前相同的数3A与3B，A在B的前面，经过排序之后会变成  
	（3B，3A，5，6）
所以说快速排序是一个不稳定的排序
/*

稳定性有什么意义？ 个人理解对于前端来说，比如我们熟知框架中的虚拟DOM的比较，我们对一个

• 列表进行渲染，当数据改变后需要比较变化时，不稳定排序或操作将会使本身不需要变化的东西变化，导致重新渲染，带来性能的损耗。

辅助记忆

• 时间复杂度记忆
  • 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)(一遍找元素O(n)，一遍找位置O(n)）
  • 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)(一遍找元素O(n)，一遍找位置O(logn))
• 稳定性记忆-“快希选堆”（快牺牲稳定性）

递归

递归步骤：

1. 找出递归终结条件
2. 编写本层逻辑代码
3. 进到下一层条件
4. 清理本层

Deep Clone

//所谓深度克隆，就是当对象的某个属性值为object或array的时候，要获得一份copy，而不是直接拿到引用值
function deepClone(origin,target) {  //origin是被克隆对象，target是我们获得copy
    var target = target || {}; //定义target
    for(var key in origin) {  //遍历原对象
        if(origin.hasOwnProperty(key)) {
            if(Array.isArray(origin[key])) { //如果是数组
                target[key] = [];
                deepClone(origin[key],target[key]) //递归
            } else if (typeof origin[key] === 'object' && origin[key] !== null) {
                target[key] = {};
                deepClone(origin[key],target[key]) //递归
            } else {
                target[key] = origin[key];
            }
        }
    }
    return target;
}

实战例题

Q1：Array数组的flat方法实现

Array.prototype.flat = function() {
    var arr = [];
    this.forEach((item,idx) => {
        if(Array.isArray(item)) {
            arr = arr.concat(item.flat()); //递归去处理数组元素
        } else {
            arr.push(item)   //非数组直接push进去
        }
    })
    return arr;   //递归出口
}

Q2 实现简易版的co，自动执行generator

function run(generat) {
    const iterator = generat();
    function autoRun(iteration) {
        if(iteration.done) {return iteration.value}  //出口
        const anotherPromise = iteration.value;
        anoterPromise.then(x => {
            return autoRun(iterator.next(x))  //递归条件
        })
    }
    return autoRun(iterator.next()) 
}

Q3. 爬楼梯问题

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？
分析： 这个问题要倒过来看，要到达n级楼梯，只有两种方式，从（n-1）级 或 （n-2）级到达的。所以可以用递推的思想去想这题，假设有一个数组s[n], 那么s[1] = 1（由于一开始就在第一级，只有一种方法）， s[2] = 1（只能从s[1]上去 没有其他方法）。那么就可以推出s[3] ~ s[n]了。
下面继续模拟一下， s[3] = s[1] + s[2]， 因为只能从第一级跨两步， 或者第二级跨一步。

function cStairs(n) {
    if(n === 1 || n === 2) {
        return 1;
    } else {
        return cStairs(n-1) + cStairs(n-2)
    }
}

Q4.二分查找

二分查找，是在一个有序的序列里查找某一个值，与小时候玩的猜数字游戏非常相啦：

A: 0 ~ 100 猜一个数字
B: 50
A: 大了
B: 25
A: 对头，就是25

因此，思路也就非常清楚了，这里有递归和非递归两种写法，先说下递归的方法吧：

• 设定区间,low和high
• 找出口： 找到target，返回target；
• 否则寻找，当前次序没有找到，把区间缩小后递归

function binaryFind(arr,target,low = 0,high = arr.length - 1) {
    const n = Math.floor((low+high) /2);
    const cur = arr[n];
    if(cur === target) {
        return `找到了${target},在第${n+1}个`;
    } else if(cur > target) {
        return binaryFind(arr,target,low, n-1);
    } else if (cur < target) {
        return binaryFind(arr,target,n+1,high);
    }
    return -1;
}

接下来，使用循环来做一下二分查找，其实思路基本一致：

function binaryFind(arr, target) {
    var low = 0,
        high = arr.length - 1,
        mid;
    while (low <= high) {
        mid = Math.floor((low + high) / 2);
        if (target === arr[mid]) {
            return `找到了${target},在第${mid + 1}个`
        }
        if (target > arr[mid]) {
            low = mid + 1;
        } else if (target < arr[mid]) {
            high = mid - 1;
        }
    }
    return -1
}

二叉树和二叉查找树

树的基本概念

如图所示，一棵树最上面的几点称为根节点，如果一个节点下面连接多个节点，那么该节点成为父节点，它下面的节点称为子节点，一个节点可以有0个、1个或更多节点，没有子节点的节点叫叶子节点。

二叉树，是一种特殊的树，即子节点最多只有两个，这个限制可以使得写出高效的插入、删除、和查找数据。在二叉树中，子节点分别叫左节点和右节点。

二叉查找树

二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中，这一特性使得查找的效率很高，对于数值型和非数值型数据，比如字母和字符串，都是如此。现在通过JS实现一个二叉查找树。

function insert(data) {
    var node = new Node(data,null,null);
    if(this.root === null) {
        this.root = node
    } else {
        var current = this.root;
        var parent;
        while(true) {
            parent = current;
            if(data < current.data) {
                current = current.left; //到左子树
                if(current === null) {  //如果左子树为空，说明可以将node插入在这里
                    parent.left = node;
                    break;  //跳出while循环
                }
            } else {
                current = current.right;
                if(current === null) {
                    parent.right = node;
                    break;
                }
            }
        }
    }
}

二叉树的遍历

我们知道，树的遍历主要包括

• 前序遍历 (根左右)
• 中序遍历 (左根右)
• 后序遍历 (左右根)

这个只是为了好记忆，我们拿下面的图做一个遍历

前序遍历: 56 22 10 30 81 77 92

中序遍历: 10 22 30 56 77 81 92

后序遍历: 10 30 22 77 92 81 56

这里发现了一些规律：

1. 前序遍历，因为是根左右，所以最后一个一定是最大的；
2. 第一个一定是root节点； 中序遍历，在查找二叉树中，一定是从小到大的顺序；
3. 根节点56左边(10/22/30)的一定是左子树的，右边的(77/81/92)一定是右子树的。 后序遍历，根节点一定在最后

中序遍历的实现

function inOrder(node) {
    if(node !== null) {
        //如果不是null，就一直查找左变，因此递归
        inOrder(node.left);
        //递归结束，打印当前值
        console.log(node.show());
        //上一次递归已经把左边搞完了，右边
        inOrder(node.right);
    }
}

//在刚才已有bst的基础上执行命令
inOrder(bst.root);

前序遍历

function preOrder(node) {
    if(node !== null) {
        //根左右
        console.log(node.show());
        preOrder(node.left);
        preOrder(node.right);
    }
}

后序遍历

function postOrder(node) {
    if(node !== null) {
        //左右根
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.show())
    }
}

二叉树的查找

• 最小值： 最左子树的叶子节点
• 最大值： 最右子树的叶子节点
• 特定值： target与current进行比较，如果比current大，在current.right进行查找，反之类似。

//最小值
function getMin(bst) {
    var current = bst.root;
    while(current.left !== null) {
        current = current.left;
    }
    return current.data;
}

//最大值
function getMax(bst) {
    var current = bst.root;
    while(current.right !== null) {
        current = current.right;
    }
    return current.data;
}

//查找值
function find(target,bst) {
    var current = bst.root;
    while(current !== null) {
        if(target === current.data) {
            return true;
        }
        else if(target > current.data) {
            current = current.right;
        } else if(target < current.data) {
            current = current.left;
        }
    }
    return -1;
}

本文地址：https://blog.csdn.net/cpa0701/article/details/109237340