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

胡哥有话说 等级 680 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)

后记

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

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

收藏
评论区

相关推荐

Node.js 如何处理 ES6 模块
Node.js 如何处理 ES6 模块作者: 日期: 学习 JavaScript 语言,你会发现它有两种格式的模块。一种是 ES6 模块,简称 ESM;另一种是 Node.js 专用的 CommonJS 模块,简称 CJS。这两种模块不兼容。很多人使用 Node.js,只会用require()加载模块,遇到 ES6
9个常用ES6特性归纳(一般用这些就够了)
ECMAScript 6.0(以下简称 ES6)是 JavaScript 语言的下一代标准,已经在 2015 年 6 月正式发布了。它的目标,是使得 JavaScript 语言可以用来编写复杂的大型应用程序,成为企业级开发语言。ES6给我们带来很多令人意想不到的功能,在这里我们一起来学习一下9个超级实用的 ES6 特性。 **1、展开操作符** -----
ES6 参数默认值引起的中间作用域
ES6 参数默认值的问题,其实之前在另一篇文章中已经有涉及,之所以再谈起这个问题,是在阅读《ES6 标准入门》时产生的一个疑惑。阮老师的代码是: var x = 1;function foo(x, y = function() { x = 2; }) { var x = 3; y(); console.log(x);}foo();
ES6 常用语法
### 什么是ES6 ECMAScript 6 简称ES6, 在2015年6月正式发布~  ECMAScript 是JavaScript语言的国际标准。 我们本着二八原则,掌握好常用的,有用的~能让我们更快的上手~~~ ### 1  声明变量const  let  var ES6以前 var关键字来声明变量,无论声明在何处都存在变量提升这个事情~~会
ES6中对字符串处理的优点
\[toc\] ### 1、字符的Unicode表示法 ES6之前 Unicode 只能表示 \\u0000 -- \\uFFFF 之间的字符。 ES6可以表示超过这个 范围的unicode字符 如 //原来 ES6 之前 "\uD842\uDFB7" // "𠮷" "\u20BB7" // " 7"
ES6基础(二)
**一、ES6字符串扩展** **字符串模板**   在传统的JavaScript语言中,输出模板通常是这样写的。 ![](https://oscimg.oschina.net/oscnet/5ee956c855034c767c1c9f8015ff329030b.png) 上面这种写法繁琐不方便,于是ES6中引入了字符串模板解决这个问题。 ![](
ES6学习笔记(3)
参考书《ECMAScript 6入门》 http://es6.ruanyifeng.com/ **字符串的扩展** ES6之前只能识别\\u0000 - \\uFFFF 之间的字符,超过此范围,识别会出错;ES6弥补了这个错误 ES6扩展的新方法 codePointAt----"𠮷".CodePointAt(0)//返回超过\\u00
ES6新特性整理,你需要了解的ES6知识
ES6是新版本JavaScript语言的标准,上一次标准的制订还是2009年出台的ES5。目前ES6的标准化工作已经完成,14年12月份放出了正式版本。 目前主流的浏览器都支持运行ES6代码,如果你的不支持,还等什么呢,换浏览器啊~ 潮流虽然太快,但我们不停下学习的步伐,就不会被潮流丢下的,下面来领略下ES6中新特性,一堵新生代JS的风采。 箭头操作符 =
ES6知识点补充
前言 ECMAScript 6.0(简称ES6),作为下一代JavaScript的语言标准正式发布于2015 年 6 月,至今已经发布3年多了,但是因为蕴含的语法之广,完全消化需要一定的时间,这里我总结了部分ES6,以及ES6以后新语法的知识点,使用场景,希望对各位有所帮助 **本文讲着重是对ES6语法特性的补充,不会讲解一些API层面的语法,更多的是发
ECMAScript 6 新特性简介
简介 == ECMAScript 6.0(以下简称 ES6)是 JavaScript 语言的下一代标准,正式发布与2015年6月。它的目标,是使得JavaScript语言可以用来编写复杂的大型应用程序,成为企业级开发语言。 今天我们将会讲解一下ES6中引入的语法新特性。 ECMAScript和JavaScript的关系 ================
ECMAScript 6.0 简介
ECMAScript 6.0(以下简称 ES6)是 JavaScript 语言的下一代标准,已经在2015年6月正式发布了。它的目标,是使得 JavaScript 语言可以用来编写复杂的大型应用程序,成为企业级开发语言。 ECMAScript 和 JavaScript 的关系 --------------------------- 一个常见的问题是,EC
ECMAScript 6新特性简介
简介 == ECMAScript 6.0(以下简称 ES6)是 JavaScript 语言的下一代标准,正式发布与2015年6月。它的目标,是使得JavaScript语言可以用来编写复杂的大型应用程序,成为企业级开发语言。 今天我们将会讲解一下ES6中引入的语法新特性。 ECMAScript和JavaScript的关系 ================
ES6学习笔记(二十)Module 的加载实现
上一章介绍了模块的语法,本章介绍如何在浏览器和 Node 之中加载 ES6 模块,以及实际开发中经常遇到的一些问题(比如循环加载)。 1.浏览器加载 ======= 传统方法  ----- HTML 网页中,浏览器通过`<script>`标签加载 JavaScript 脚本。 <!-- 页面内嵌的脚本 --> <script type
JS中!function(){}()的理解
这种写法,是一种`立即执行函数`的写法,即IIFE等设计模式。这种函数在函数定义的地方就直接执行了。 理解IIFE设计模式的关键是要认识到,在ES6之前,JavaScript仅具有[函数作用域](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fen.wikipedia.org%2Fwiki
JavaScript易错知识点整理
前言 本文是我学习JavaScript过程中收集与整理的一些易错知识点,将分别从变量作用域,类型比较,this指向,函数参数,闭包问题及对象拷贝与赋值这6个方面进行由浅入深的介绍和讲解,其中也涉及了一些ES6的知识点。 JavaScript知识点 ------------- ### 1.变量作用域 `var a = 1; functio