阿里淘系一面——牛客网@°良木丶

排序算法

1.说下自己了解的排序算法，并说明实现原理和时间复杂度（最好最坏最平均情况）

冒泡排序

比较所有相邻的两项，如果第一个比第二个大，则交换他们

最好O(n) 最坏O(n^2) 平均O(n^2) 稳定

function bubbleSort(array) {
  const length = array.length
  for (let i = 0; i < length; i++) {
    // 使用 length - 1 - i 是为了减去外层循环已经排序过的趟数，优化次数
    for (let j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        let temp = array[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return array
}

选择排序

找到数据中的最小值并将其放在第一位，接着找到第二小的值并将其放在第二位，以此类推

最好O(n^2) 最坏O(n^2) 平均O(n^2) 不稳定

function selectionSort(array) {
  const length = array.length
  for (let i = 0; i < length - 1; i++) {
    let minIndex = i // 假设第i项为最小值
    for (let j = i + 1; j < length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j
      }
    }
    if (i !== minIndex) {
      let temp = array[i]
      array[i] = array[minIndex]
      array[minIndex] = temp
    }
  }
  return array
}

插入排序

假设第一项已经排序了，接着和第二项进行比较，取出第二项的索引和值，判断第二项应该待在原位还是插到第一项之前？这样，头两项就已经正确排序，接着已经排序好的再和第三项比较（它应该插入到第一、第二、还是原位置？），以此类推

最好O(n) 最坏O(n^2) 平均O(n^2) 稳定

function insertionSort(array) {
  const length = array.length
  // 假设索引0已经排序
  for (let i = 1; i < length; i++) {
    let j = i
    let temp = array[i]
    while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1] // 将前一项后
      j--
    }
    array[j] = temp // 次数 j 为前一项索引，被插入到前面
  }
  return array
}

快速排序

分而治之

1.选择基准值，一般是将开头、中间、末尾三个数先进行排序，中间值作为基准值
2.将数组分为两个子数组：小于基准值得元素组成的子数组和大于基准值得元素组成的子数组
3.对这两个子数组进行快速排序（递归）

最好O(nlog^n) 最坏O(n^2) 平均O(nlog^n) 不稳定

数据结构

1.链表和数组的区别？各自的查找时间复杂度

数组在内存中是连续存放的，链表不是顺序存储的

数组查找快O(1)，增删慢O(n)
链表查找慢O(n)，增删块O(1)

2.树的存储（内存中）

双亲表示法，不是很清楚

3.二叉排序树的查找，不用递归

不是很清楚，待学习

4.二叉树变平衡二叉树

不是很清楚，待学习

前端相关

1.模拟JQuery选择器，传一串字符串获取对应dom元素

封装一个构造函数，传入dom节点id，声明一个属性值来保存获取到的dom元素，接着在其原型上定义相关方法执行相关操作，特定条件下返回this，用来执行链式操作

具体实现如下：

function Elem(id) {
  this.elem = document.getElementById(id)

  Elem.prototype.html = function (val) {
    const elem = this.elem
    if (val) {
      elem.innerHTML = val
      return this // 用于执行链式操作
    } else {
      return elem.innerHTML
    }
  }
  Elem.prototype.on = function (type, fn) {
    const elem = this.elem
    elem.addEventListener(type, fn)
    return this // 用于执行链式操作
  }
}

2.闭包及应用场景，使用闭包会造成什么后果？

当一个函数访问了其外部作用域的变量，就说这个函数是闭包

应用场景：

延长局部变量生命周期
封装私有变量

后果：因为闭包引用着另外一个函数的变量，这就会导致另外一个函数就算不再使用了也无法触发JavaScript的垃圾收集机制（标记清除）从而被销毁，所以当闭包使用过多，会占用较多的内存，导致内存泄漏！！！

3.跨域及解决方案？

浏览器同源政策限制，不允许ajax访问其他域接口

解决方案：

前端jsonp
后端CROS跨域资源请求，设置http header

详情参考我的这篇关于跨域的博客

4.盒模型、

标准盒模型（content + border + padding + margin）width 只包括 content
怪异盒模型（width（content + border + padding） + margin）width不包括外边距

5.从输入url到页面加载发生了什么？

简要说明就是：

判断是否需要跳转（301：永久性重定向）
从浏览器读取缓存（减少请求时间）
DNS解析（域名解析）
TCP连接（三次握手）
HTTP请求发出
服务器端处理请求，HTTP响应返回
浏览器拿到响应数据，解析响应内容，把解析结构展示给用户

6.实现数组indexOf，并说明时间复杂度

function idnexOf(arr, item) {
  if (!Array.isArray(arr) && !!!item) {
    return false
  }
  let resultindex = 0
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === item) {
      resultindex = i
      break
    } else {
      resultindex = -1
    }
  }
  return resultindex
}

时间复杂度：最好O(1) 最坏O(n) 平均O(n)

阿里淘系一面——牛客网@&#176;良木丶