黑马程序员技术交流社区

标题: 【上海校区】前端笔试&面试爬坑系列---算法 [打印本页]
作者: 不二晨    时间: 2018-8-20 09:41
标题: 【上海校区】前端笔试&面试爬坑系列---算法
排序JS本身数组的sort方法，可以满足日常业务操作中很多的场景了，所以我认为这也是为什么基本面试会直接让写一个快速排序，因为好像其他排序方法在JS中似乎没什么意义了。
但是在拼多多的面试中，面试官还是让我手写选择排序 冒泡排序 和快速排序 的伪代码。 既然有机会总结，干脆就全部写一遍好了，从基本排序到高级排序来说。
基本排序算法基本排序的基本思想非常类似，重排列时用的技术基本都是一组嵌套的for循环: 外循环遍历数组的每一项，内循环则用于比较元素。
冒泡排序最笨最基本最经典点的方法，不管学什么语言，说到排序，第一个接触的就是它了吧。基本思想什么的太经典了，就不复数了，直接用例子说明过程吧：
E A D B H复制代码经过一次排列后，变成
A E D B H复制代码前两个元素互换了，接下来变成：
A D E B H复制代码第二个和第三个互换，继续：
A D B E H复制代码第三个和第四个互换，最后，第二个和第三个元素还会互换一次，得到最终的顺序为：
A B D E H复制代码

好了，其实基本思想就是逐个的比较，下面就实现一下：
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;}复制代码这里有两点需要注意：
在比较交换的时候，就是计算机中最经典的交换策略，用临时变量temp保存值，但是面试官问过我，ES6有没有简单的方法实现？ 有的，如下：
arr2 = [1,2,3,4];[arr2[0],arr2[1]] = [arr2[1],arr2[0]]  //ES6解构赋值console.log(arr2)  // [2, 1, 3, 4]复制代码所以，刚才的冒牌排序可以优化如下：
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;}复制代码选择排序选择排序是从数组的开头开始，将第一个元素和其他元素作比较，检查完所有的元素后，最小的放在第一个位置，接下来再开始从第二个元素开始，重复以上一直到最后。


有了刚才的铺垫，我觉得不用再演示了，很简单嘛： 外层循环从0开始到length-1， 然后内层比较，最小的放开头，走你：
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) {                [arr,arr[j]] = [arr[j],arr];            }        }    }    return arr}复制代码简单说两句：
  • 外层循环的i表示第几轮，arr就表示当前轮次最靠前(小)的位置；
  • 内层从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;}复制代码分析： 注意这里两次循环中，i和j的含义：
  • i是外循环，依次把后面的数插入前面的有序序列中，默认arr[0]为有序的，i就从1开始
  • j进来后，依次与前面队列的数进行比较，因为前面的序列是有序的，因此只需要循环比较、交换即可
  • 注意这里的break，因为前面是都是有序的序列，所以如果当前要插入的值arr[j]大于或等于arr[j-1]，则无需继续比较，直接下一次循环就可以了。
时间复杂度乍一看，好像插入排序速度还不慢，但是要知道： 当序列正好逆序的时候，每次插入都要一次次交换，这个速度和冒泡排序是一样的，时间复杂度O(n²)； 当然运气好，前面是有序的，那时间复杂度就只有O(n)了，直接插入即可。
排序算法
平均时间复杂度
最坏时间复杂度
空间复杂度
是否稳定

冒泡排序
O(n²)
O(n²)
O(1)
是

选择排序
O(n²)
O(n²)
O(1)
不是

直接插入排序
O(n²)
O(n²)
O(1)
是
好了，这张表如何快速记忆呢？ 方法就是一开始写的基本排序算法 。 一开始就说到，基本思想就是两层循环嵌套，第一遍找元素O(n),第二遍找位置O(n)，所以这几种方法，时间复杂度就可以这么简便记忆啦!
高级排序算法如果所有排序都像上面的基本方法一样，那么对于大量数据的处理，将是灾难性的，老哥，只是让你排个序，你都用了O(n²)。 好吧，所以接下来这些高级排序算法，在大数据上，可以大大的减少复杂度。
快速排序快速排序可以说是对于前端最最最最重要的排序算法，没有之一了，面试官问到排序算法，快排的概率能有80%以上(我瞎统计的...信不信由你)。
所以快排是什么呢？
快排是处理大数据最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直至所有数据都是有序的。
简单说： 找到一个数作为参考，比这个数字大的放在数字左边，比它小的放在右边； 然后分别再对左边和右变的序列做相同的操作:
  • 选择一个基准元素，将列表分割成两个子序列；
  • 对列表重新排序，将所有小于基准值的元素放在基准值前面，所有大于基准值的元素放在基准值的后面；
  • 分别对较小元素的子序列和较大元素的子序列重复步骤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 < current) {            left.push(arr)  //放在左边        } else {            right.push(arr) //放在右边        }    }    return quickSort(left).concat(current,quickSort(right)); //递归}复制代码希尔排序希尔排序是插入排序的改良算法，但是核心理念与插入算法又不同，它会先比较距离较远的元素，而非相邻的元素。文字太枯燥，还是看下面的动图吧：


在实现之前，先看下刚才插入排序怎么写的：
function insertSort(arr) {    for(let i = 1; i < arr.length - 1; 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 {                continue;            }        }    }    return arr;}复制代码现在，不同之处是在上面的基础上，让步长按照3、2、1来进行比较，相当于是三层循环和嵌套啦。
insertSort(arr,[3,2,1]);function shellSort(arr,gap) {    console.log(arr)//为了方便观察过程，使用时去除    for(let i = 0; i<gap.length; i++) {  //最外层循环，一次取不同的步长，步长需要预先给出        let n = gap; //步长为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，就会发现是完全一样的了。
运行一下看看
var arr = [3, 2, 45, 6, 55, 23, 5, 4, 8, 9, 19, 0];var gap = [3,2,1];console.log(shellSort(arr,gap))复制代码结果如下:
(12) [3, 2, 45, 6, 55, 23, 5, 4, 8, 9, 19, 0] //初始值当前序列为[3,2,23,6,55,45,5,4,8,9,19,0]  交换了45和23当前序列为[3,2,23,5,55,45,6,4,8,9,19,0]  交换了6和5当前序列为[3,2,23,5,4,45,6,55,8,9,19,0]  交换了55和4当前序列为[3,2,23,5,4,8,6,55,45,9,19,0]  交换了45和8当前序列为[3,2,8,5,4,23,6,55,45,9,19,0]  交换了23和8当前序列为[3,2,8,5,4,23,6,19,45,9,55,0]  交换了55和19当前序列为[3,2,8,5,4,23,6,19,0,9,55,45]  交换了45和0当前序列为[3,2,8,5,4,0,6,19,23,9,55,45]  交换了23和0当前序列为[3,2,0,5,4,8,6,19,23,9,55,45]  交换了8和0当前序列为[0,2,3,5,4,8,6,19,23,9,55,45]  交换了3和0当前序列为[0,2,3,5,4,8,6,9,23,19,55,45]  交换了19和9当前序列为[0,2,3,4,5,8,6,9,23,19,55,45]  交换了5和4当前序列为[0,2,3,4,5,6,8,9,23,19,55,45]  交换了8和6当前序列为[0,2,3,4,5,6,8,9,19,23,55,45]  交换了23和19当前序列为[0,2,3,4,5,6,8,9,19,23,45,55]  交换了55和45复制代码时间复杂度总结wait？ 不是还有很多排序算法的吗？怎么不继续了？ 是的，其实排序是很深奥的问题，如果研究透各个方法的实现、性能等等，内容恐怕多到爆炸了...而且这个也主要是为前端常见算法 问题的总结，个人觉得到这里就差不多了
排序算法
平均时间复杂度
最坏时间复杂度
空间复杂度
是否稳定

冒泡排序
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的比较，我们对一个<ul>列表进行渲染，当数据改变后需要比较变化时，不稳定排序或操作将会使本身不需要变化的东西变化，导致重新渲染，带来性能的损耗。
辅助记忆
  • 时间复杂度记忆
    • 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)(一遍找元素O(n)，一遍找位置O(n)）
    • 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)(一遍找元素O(n)，一遍找位置O(logn))
  • 稳定性记忆-“快希选堆”（快牺牲稳定性）

递归递归，其实就是自己调用自己。
很多时候我们自己觉得麻烦或者感觉 "想象不过来"，主要是自己和自己较真，因为交给递归，它自己会帮你完成需要做的。
递归步骤：
  • 寻找出口，递归一定有一个出口，锁定出口，保证不会死循环
  • 递归条件，符合递归条件，自己调用自己。
talk is cheap，show me code！
斐波那契数列，每个语言讲递归都会从这个开始，但是既然搞前端，就搞点不一样的吧，从对象的深度克隆(deep clone)说起
Deep Clone ：实现对一个对象(object)的深度克隆
//所谓深度克隆，就是当对象的某个属性值为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]) //递归            }            target[key] = origin[key];        }    }    return target;}复制代码这个可以说是前端笔试/面试中经常经常遇到的问题了，思路是很清晰的：
  • 出口： 遍历对象结束后return
  • 递归条件： 遇到引用值Array 或 Object
剩下的事情，交给JS自己处理就好了，我们不用考虑内部的层层嵌套，想太多
实战例题接下来，列举一些自己在最近笔试、面试中遇到的，需要使用递归实现的问题
Q1：Array数组的flat方法实现(2018网易雷火&伏羲前端秋招笔试)Array的方法flat很多浏览器还未能实现，请写一个flat方法，实现扁平化嵌套数组，如：
Arrayvar arr1 = [1, 2, [3, 4]];arr1.flat(); // [1, 2, 3, 4]复制代码这个问题的实现思路和Deep Clone非常相似，这里实现如下：
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;   //递归出口}复制代码好了，可以测试一下：
arr = [[2],[[2,3],[2]],3,4]arr.flat()// [2, 2, 3, 2, 3, 4]复制代码神秘力量的新解法
在评论区的一位小伙伴，提出了更好的办法，很简洁、方便，只用一句话就可以实现需求哦(不过你这样去解答一道网易的“编程题”,不觉得让人家有点难堪嘛~哈哈)
arr.prototype.flat = function() {    this.toString().split(',').map(item=> +item )}复制代码好了，惊叹完之后，大概说下实现吧：
  • toString方法，连接数组并返回一个字符串 '2,2,3,2,3,4'
  • split方法分割字符串，变成数组['2','2','3','2','3','4']
  • map方法，将string映射成为number类型2,2,3,2,3,4
Q2 实现简易版的co，自动执行generator这个问题，详细的解释可以在我之前的文章(从Co剖析和解释generator的异步原理)去看一下，如果对ES6的iterator和generator不太了解的，可以跳过这个问题。
比如实现如下的功能:
const co = require('co');co(function *() {    const url = 'http://jasonplacerholder.typecoder.com/posts/1';    const response = yield fetch(url);    const post = yield response.json();    const title = post.title;    console.log('Title: ',title);})复制代码剖析：
  • 第一步找出口，执行器返回的iterator如果状态为done，代表结束，可以出去
  • 递归条件： 取到下一个iterator，进行递归，自我调用
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)    }}复制代码哇...
没想到今天去整理排序 花了这么久...嗯..然而这篇文章已经够长了
接下来我会把之前笔试遇到的题目和一些常用的算法问题，一一记录，前端很多算法都是和数组、字符串处理息息相关的，所以对正则表达式、数组常用方法的掌握也很重要，简单总结下知识点：
  • 正则表达式
    • 字符串相关方法
    • str.split()
    • str.replace()
    • str.match()
    • reg.test()
    • reg.exec()
  • 数组方法
    • Array.map()  映射，有返回值，不改变数组本身
    • Array.forEach() 遍历，无返回值
    • Array.filter() 过滤，返回true时返回,false时不返回
    • Array.splice/slice/join等
    • for...of 遍历,iterator相关知识点


【转载】
链接：https://juejin.im/post/5b72f0caf265da282809f3b5



作者: 梦缠绕的时候    时间: 2018-8-21 16:26




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2