前端需要知道的数据结构与算法(持续更新中...)

Jensen 发布于2019-08-23 15:17 / 3015人阅读

摘要：通常需要在实际的计算机运行才知道具体的执行时间。算法的执行时间往往和算法代码中语句执行的数量有关。空间复杂度运行一段程序的内存占用，空间复杂度通常指的是算法程序在计算机只想中只想所需要的存储空间。

基本数据结构 JS 数据类型

基本类型（栈 stack）： Number String Boolean Null Undefined 和 Symbol（es6 新增）
引用类型（堆 heap）：Object Array Function Data

数据结构

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成

算法 算法特征

有穷性、确定性、可行性、输入、输出

算法设计衡量

正确性、可读性、健壮性, 时间复杂度, 空间复杂度

时间复杂度

运行一段程序的计算工作量，时间复杂度即通常所说的算法执行所需要耗费的时间，时间越短，算法越好。但是，一个算法的执行时间往往无法精确估计。通常需要在实际的计算机运行才知道具体的执行时间。但是，也可以大致进行估计，得到算法的时间复杂度。算法的执行时间往往和算法代码中语句执行的数量有关。

空间复杂度

运行一段程序的内存占用，空间复杂度通常指的是算法程序在计算机只想中只想所需要的存储空间。

eg:

O(1):常数运算

O(n):1 层循环

O(n^2):2 层循环

O(n^n):n 层循环

O(log2n):int i = 1, n = 100;while(i < n){ i = i * 2;}

算法分类

快速排序算法

深度优先算法

广度优先算法

堆排序算法

归并排序算法

冒泡排序

原理：每次把最大或者最小的浮到最顶层

let arr = [33, 1, 46, 23, 35, 12, 30, 4, 16, 2]
function bubbleSort(array) {
  for (var i = 0; i < array.length; i++) {
    for (var j = 0; j < array.length - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        var temp = array[j]
        array[j] = array[j + 1]
        array[j + 1] = temp
      }
    }
  }
  return array
}

插入排序

原理：从数组的第二个和第一个比较，如果小于第一个则插入到第一个元素之前，否则不变
第三个一次和第二个第一个比,如果小于第二个且大于第一个则插入第二个元素之前

let arr = [33, 1, 46, 23, 35, 12, 30, 4, 16, 2]
function insertionSort(arr) {
  var len = arr.length
  var preIndex, current
  for (var i = 1; i < len; i++) {
    preIndex = i - 1
    current = arr[i]
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
  return arr
}

选择排序

原理：从数组的第一个开始，向后比较，找到最小的和第一个交换

let arr = [33, 1, 46, 23, 35, 12, 30, 4, 16, 2]
function selectionSort(arr) {
  var len = arr.length
  var minIndex, temp
  for (var i = 0; i < len; i++) {
    minIndex = i
    for (var j = i + 1; j < len; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j
      }
    }
    temp = arr[i]
    arr[i] = arr[minIndex]
    arr[minIndex] = temp
  }
  return arr
}

算法复杂度

排序方法	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性	复杂性
冒泡排序	O(n^2)	O(n)	O(1)	稳定	简单
插入排序	O(n^2)	O(n)	O(1)	稳定	简单
选择排序	O(n^2)	O(n^2)	O(1)	不稳定	简单

参考

前端你应该了解的数据结构与算法

如何理解时间复杂度和空间复杂度 3. 时间复杂度和空间复杂度

云服务器 GPU云服务器描述的数据结构与算法前端需要的技术前端需要掌握的技术前端开发需要掌握的技术

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101815.html

平时积累的前端资源，持续更新中。。。

本文收集学习过程中使用到的资源。持续更新中…… 项目地址 https://github.com/abc-club/f... 目录 vue react react-native Weex typescript Taro nodejs 常用库 css js es6 移动端微信公众号小程序 webpack GraphQL 性能与监控高质文章趋势动效数据结构与算法 js core 代码规范...

acrazing 2019-08-26 10:40 评论0 收藏0
前端面试题收集，持续更新中

摘要：对于所访问的每个元素，函数应该将该元素传递给所提供的回调函数。 HTML 在线阅读Github地址题目列表 HTML HTML和XHTML的区别 Html的语义化 Doctype的文档类型 cookie、sessionSttorage、localStory区别 HTML全局属性(global attribute)有哪些？常见的浏览器内核有哪些？介绍一下你对浏览器内核的理解？...

kgbook 2019-08-22 16:49 评论0 收藏0
前端面试题收集，持续更新中

摘要：对于所访问的每个元素，函数应该将该元素传递给所提供的回调函数。 HTML 在线阅读Github地址题目列表 HTML HTML和XHTML的区别 Html的语义化 Doctype的文档类型 cookie、sessionSttorage、localStory区别 HTML全局属性(global attribute)有哪些？常见的浏览器内核有哪些？介绍一下你对浏览器内核的理解？...

2json 2019-08-29 15:12 评论0 收藏0
前端面试题收集，持续更新中

摘要：对于所访问的每个元素，函数应该将该元素传递给所提供的回调函数。 HTML 在线阅读Github地址题目列表 HTML HTML和XHTML的区别 Html的语义化 Doctype的文档类型 cookie、sessionSttorage、localStory区别 HTML全局属性(global attribute)有哪些？常见的浏览器内核有哪些？介绍一下你对浏览器内核的理解？...

adam1q84 2019-08-02 10:17 评论0 收藏0
校招社招必备核心前端面试问题与详细解答

摘要：本文总结了前端老司机经常问题的一些问题并结合个人总结给出了比较详尽的答案。网易阿里腾讯校招社招必备知识点。此外还有网络线程，定时器任务线程，文件系统处理线程等等。线程核心是引擎。主线程和工作线程之间的通知机制叫做事件循环。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文总结了前端老司机经常问题的一些问题并结合个...

jonh_felix 2019-08-23 18:40 评论0 收藏0