前端面试题解密:经典算法之冒泡算法(ES6版)及优化

胡哥有话说 等级 392 0 0

前言

随着前端的飞速发展,前端业务开发给前端工程师提出了更高的要求,因而算法题也越来越高频次的出现在前端面试中。有很多的小伙伴找胡哥苦诉,在前端实际开发中(除了涉及游戏开发方面),算法使用有很多吗?大厂的面试是故意要自我标榜下吗?其实不然,考核算法还是相当有必要的,来来来,让胡哥给你拯救世界的理由,哦,不,是考核算法的理由。

为啥要考算法?

  1. 算法是通用技能,包含了诸多逻辑和相关的技术点,优秀的算法方案会体现出优秀的逻辑思维和和解决问题的能力。
  2. 扎实的算法有助于我们在解决复杂问题时获得更优的解决方案。

算法的实现基于不同的语言有不同的形式,对于JavaScript来说,算法的实现也有很多种不同的方式,本文基于JS最新的ES6语法来实现,各位小伙伴在领略算法魅力的同时也能掌握到ES6的语法。

一、冒泡算法

冒泡算法,闻名而知其意,使用类似于水中气泡自下而上逐渐变大的原理(这个原理要是有不清楚的童鞋,可咨询物理老师压强问题,看看老师会不会把你打出shi来...)来对数组进行排序。

排序规则

  1. 每次循环,比较当前位置项与下一个位置项的大小,如果当前项 > 后一项,则交换两者的位置。每次循环比较都能选择出一个最大值,放在末尾,剩余待筛选的比较项就减少一项。
  2. 如果数组存在n项,那么需要循环执行筛选的次数为n次

二、冒泡算法代码实现

function bubbleSort ([...arr]) {
  for (let i = 0; i < arr.length; i++) {    
    // 第j和j+1项比较,故j的最大值为 = 最大长度 - 1 - 减去已经执行筛选的轮数i
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换数组元素的位置
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
      }
    }
  }
  return arr
}

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

// 输出排序结果
let sortArr = bubbleSort(arr)
console.log(sortArr) // [1, 2, 3, 4]
// 输出原数组
console.log(arr) // [4, 3, 2, 1]

ES6语法结构

  1. 函数定义时形参:[...arr]
     解构赋值和扩展运算符,为不影响原数组,使用该方式接收原数组元素
  2. [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]表达式
     利用数组的解构赋值,交换两个位置的值
     [a, b] = [b, a]
     这样就不必借助于第三个变量来交换值

三、冒泡算法优化

使用上面的方式来实现冒泡算法排序时,时间平均复杂度为O(n^2),那最坏的情况是什么呢?传入的数组完全是逆序的,即[4, 3, 2, 1]。但是如果传入的数组[1, 2, 3, 4]是完全正序的呢?如果还按该方式,那在执行时是性能浪费的,那该如何优化呢?

优化方案

如果数组是完全顺序的,那就说明在执行一次循环比较时,没有数组元素被交换位置,所以我们来设置一个标志flag,初始化为true,如果存在交换则赋值为false。在一次循环后,如果标志为true,则表示为无交换,已经是完全顺序了,则可以break停止外层循环了。下面我们来看下代码实现。

function bubbleSort ([...arr]) {
  for (let i = 0; i < arr.length; i++) {
    // 设置标记,标记当前轮筛选时是否有交换位置元素,默认为true,如果有交换设置为false
    let flag = true

    // 第j和j+1项比较,故j的最大值为 最大长度 - 1 - 减去已经执行筛选的轮数i
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换数组元素的位置
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]

        // 有交换位置,设置标记为false
        flag = false
      }
    }

    // 如果当前轮比较时没有交换位置,说明已经排序完成了
    if (flag) {
      break
    }
  }
  return arr
}

let arr = [1, 2, 3, 4]
// 输出排序结果
let sortArr = bubbleSort(arr)
console.log(sortArr) // [1, 2, 3, 4]
// 输出原数组
console.log(arr) // [1, 2, 3, 4]

此时在完成排序时,只执行了一次循环,此刻的时间复杂度为O(n)

后记

以上就是胡哥今天给大家分享的内容,喜欢的小伙伴记得点赞收藏呦,关注胡哥有话说,学习前端不迷路,欢迎多多留言交流...

胡哥有话说,专注于大前端技术领域,分享前端系统架构,框架实现原理,最新最高效的技术实践!

收藏
评论区

相关推荐

一、手写源码之 Promise
版本一,构造函数 javascript function MyPromise(fn () {}) { // const this {} this.state 'pending' this.value undefined const resolve (value) { if (this.state
ES6之set
const snew Set(); 2,3,4,2,3,4,5,6,2,3,3.forEach(xs.add(x)) console.log(s); for(let i of s){ console.log(i) } console.log(s.add(9)); //add(value),添加某个值,返回Set结构本身 console.log(s.d
快速掌握es6+新特性及es6核心语法盘点
首先先祝各位国庆快乐,好好去体验生活的快乐,也祝祖国生日快乐,越变越强大,越来越繁荣。 接下来我会总结一些工作中常用也比较核心的es6的语法知识,后面又要慢慢开始
JavaScript基础加ES6语法
JavaScript 一、什么是JavaScript 当下最流行的脚本语言,在世界上的所有浏览器中都有js的身影,是一门脚本语言,可以用于我们与web站点和web应用程序的交互,还可以用于后台服务器的编写,例如node.js 二、语法特点 基于对象和事件驱动的松散型,解释型语言 单线程异步 三、JavaScript作用 页面的交
前端面试题解密:经典算法之冒泡算法(ES6版)及优化
前言 随着前端的飞速发展,前端业务开发给前端工程师提出了更高的要求,因而算法题也越来越高频次的出现在前端面试中。有很多的小伙伴找胡哥苦诉,在前端实际开发中(除了涉及游戏开发方面),算法使用有很多吗?大厂的面试是故意要自我标榜下吗?其实不然,考核算法还是相当有必要的,来来来,让胡哥给你拯救世界的理由,哦,不,是考核算法的理由。 为啥要考算法? 1. 算法是
ES6环境搭建及react-router学习
一、起因 ES6新纳入了很多振奋人心的新特性,真的很让人忍不住去尝试一下。不过,由于现在大部分的浏览器对ES6的支持程度都不是很好。所以如果想要放心地使用一些新特性,还需要用一些工具,将ES6或者ES7的代码转为ES5的代码。今天,就配置了一下环境
js 理解模块化
经常在面试或者其他文章看到关于模块化的问题,之前也只是寥寥看了几次,对于 CommonJS,AMD,ES6也说不出个所以然,于是今天抽空好好看了 红宝书第4版关于模块化的介绍,这里记录一下。 理解模块模式 初衷在开发中肯定有设计大量三方库或者业务逻辑代码,较好的方式是将其分割为多个小模块,最后以一定的方式连接起来
JavaScript 是什么?
前言 引用《JavaScript 高级程序设计第四版》中说的话 ——“从简单的输入验证脚本到强大的编程语言,JavaScript 的崛起没有任何人预测到。它很简单,学会用只要几分钟;它又很复杂,掌握它要很多年。要真正学好用好 JavaScript,理解其本质、历史及局限性是非常重要的”。 面试官:JavaScript 是什么? 我:
Node.js 如何处理 ES6 模块
Node.js 如何处理 ES6 模块作者: 日期: 学习 JavaScript 语言,你会发现它有两种格式的模块。一种是 ES6 模块,简称 ESM;另一种是 Node.js 专用的 CommonJS 模块,简称 CJS。这两种模块不兼容。很多人使用 Node.js,只会用require()加载模块,遇到 ES6
ES 家族新特性,闪亮登场!
前言前端学习永无止境,学习吧骚年 本文集合了 ES6 至 ES11 常用到的特性,包括还在规划的 ES12,只列举大概使用,详细介绍的话内容量将十分巨大.。PS:使用新特性需要使用最新版的 bable 就行转义 新特性ES6(2015) 1\. 类(class) class Man    constructor(name)      this.n
JavaScript 和 Node.js 中事件循环
1.JavaScript中事件循环可以参考《JavaScript忍者秘籍第二版》第十三章,讲解的很好。JavaScript中事件循环,主要就在理解宏任务和微任务这两种异步任务。宏任务(macrotask): setTimeOut 、 setInterval 、 setImmediate 、 I/O 、 各种callback、 UI渲染 、messageCh
你所知道的JS变量作用域
变量的作用域,指的是变量在脚本代码中的可读、可写的有效范围,也就是脚本代码中可以使用这个变量的区域。在ES6之前,变量的作用域主要分为全局作用域、局部作用域(也称函数作用域)两种;在ES6及其之后,变量的作用域主要分为全局作用域、局部作用域、块级作用域这3种。相应作用域变量分别称为全局变量、局部变量、块级变量。全局变量声明在所有函数之外;局部变量是在函数体内
了解什么是 TypeScript
内容纲要 了解什么是 TypeScript TypeScript 基本语法 TypeScript 介绍 TypeScript 是什么TypeScript 是 JavaScript 的强类型版本。然后在编译期去掉类型和特有语法,生成纯粹的 JavaScript代码。由于最终在浏览器中运行的仍然是 JavaScript,所以 TypeScript 并
ES11来了,不进来看看嘛
前言ES2020 (ES11)是 ECMAScript 对应 2020 年的版本。这个版本不像 ES6 (ES2015)那样包含大量新特性。但也添加了许多有趣且有用的特性。本文以简单的代码示例来介绍 ES2020新特性。这样,你可以很快理解这些新功能,而不需要多么复杂的解释,好了,废话不多说我们进入正文🔛 私有变量类的主要作用之一是将我们的代码包含在可重用的
一分钟入门 Babel(下一代 JavaScript 语法的编译器)
简单来说把 JavaScript 中 es2015/2016/2017/2046 的新语法转化为 es5,让低端运行环境(如浏览器和 node )能够认识并执行。严格来说,babel 也可以转化为更低的规范。但以目前情况来说,es5 规范已经足以覆盖绝大部分浏览器,因此常规来说转到 es5 是一个安全且流行的做法。ES6转ES5(第一种) 初始化项目npm