大厂面试：JavaScript各种源码解析

Javanx

发布于 2019-09-04 13:00:21

7160

发布于 2019-09-04 13:00:21

文章被收录于专栏：web秀

call函数实现

func 是要调用的函数，是由 context 调用，func 的指向 context，所以关注点在 context 指向

Function.prototype.call = function (context) {
  context = context || window
  const func = Symbol()
  context[func] = this
  const args = [...arguments].slice(1)
  const result = context[func](...args)
  delete context[func]
  return result
}

apply函数实现

该方法的语法和作用与 call() 方法类似，只有一个区别，就是 apply() 方法接受的是一个包含多个参数的数组，而 call() 方法接受的是一个参数列表

Function.prototype.apply = function (context) {
  context = context || window
  const func = Symbol()
  context[func] = this
  // 不同点
  const args = [...arguments[1]]
  const result = context[func](...args)
  delete context[func]
  return result
}

bind函数实现

注意：返回的是函数

Function.prototype.bind = function (context) {
  const self = this
  const args = [...arguments].slice(1)
  return function () {
    return self.apply(context, args.concat(...arguments))
  }
}

Object.assign实现

Object.assign() 方法用于将所有可枚举属性的值从一个或多个源对象复制到目标对象。它将返回目标对象。

Object.assign = function (target) {
  for (let index = 1; index < arguments.length; index++) {
    let nextObj = arguments[index]
    if (nextObj != null) {
      for (let nextKey in nextObj) {
        // 忽略掉那些从原型链上继承到的属性
        if (nextObj.hasOwnProperty(nextKey)) {
          target[nextKey] = nextObj[nextKey]
        }
      }
    }
  }
  return target
}

Object.create实现

Object.create()方法创建一个新对象，使用现有的对象来提供新创建的对象的proto。

Object.create = function (proto) {
  function F () {}
  F.prototype = proto
  return new F()
}

new操作符实现

new 运算符创建一个用户定义的对象类型的实例或具有构造函数的内置对象的实例。new 关键字会进行如下的操作：

创建一个空的简单JavaScript对象（即{}）；链接该对象（即设置该对象的构造函数）到另一个对象；将步骤1新创建的对象作为this的上下文；如果该函数没有返回对象，则返回this。

function newFunc (func) {
  return function () {
    // 创建了一个新对象，并且新对象原型指向func构造函数的原型对象
    // 不太懂可以看上面的Object.create基本实现
    const obj = Object.create(func.prototype)
    // 将构造函数的this指向obj，这样obj就可以访问到构造函数中的属性和方法
    func.call(obj, ...arguments)
    // 返回
    return obj
  }
}

// 示例
function Person (name, age) {
  this.name = name
  this.age = age
}
const obj = newFunc(Person)('小白', 18)
// >>> person {name: "小白", age: 18}

instanceof操作符实现

instanceof运算符用于测试构造函数的prototype属性是否出现在对象的原型链中的任何位置

function instanceOf (lift, right) {
  let lp = lift.__proto__
  let rp = right.prototype
  while (true) {
    if (lp === null) return false
    if (lp === rp) return true
    lp = lp.__proto__
  }
}

// 示例
function Person (name, age) {
  this.name = name
  this.age = age
}
function Student (name, age, school){
  Person.call(this, name, age)
  this.school = school
}
Student.prototype = Object.create(Person.prototype)
Student.prototype.constructor = Student
let student = new Student('小白', 18, '掘金')
instanceOf(student, Person)
// >>> true

继承方式

原型链继承

缺点：不能给父类构造函数传递参数，所有新实例都会共享父类实例的属性

// 父类构造函数
function Person (name, age) {
  this.name = name
  this.age = age
}
// 子类构造函数
function Student (school){
  this.school = school
}
Student.prototype = new Person()

借用构造函数继承

优点：可以解决给父类构造函数传递参数的问题，不存在共享问题。

缺点：父类原型的属性无法共享，父类的方法没有被共享。

// 父类构造函数
function Person (name, age) {
  this.name = name
  this.age = age
}
// 子类构造函数
function Student (name, age, school){
  Person.call(this, name, age)
  this.school = school
}

组合继承

优点：可以继承父类原型上的属性，可以传参，可复用。

缺点：调用了两次父类构造函数。

// 父类构造函数
function Person (name, age) {
  this.name = name
  this.age = age
}
// 子类构造函数
function Student (name, age, school){
  Person.call(this, name, age)
  this.school = school
}
Student.prototype = new Person()
Student.prototype.constructor = Student

原型式继承

缺点：原型引用属性会被所有实例共享

// 父类构造函数
function Person (name, age) {
  this.name = name
  this.age = age
}
let person = new Person('小白'， 18)
// 原型式继承的子类
let student = Object.create(person)

寄生式继承

给原型式继承穿了个马甲而已

// 父类构造函数
function Person (name, age) {
  this.name = name
  this.age = age
}
function createStudent (person) {
    let student = Object.create(person)
    return student
}
let person = new Person('小白'， 18)
let student = createStudent(person)

寄生组合式继承

最理想的继承方式

// 父类构造函数
function Person (name, age) {
  this.name = name
  this.age = age
}
// 子类构造函数
function Student (name, age, school){
  Person.call(this, name, age)
  this.school = school
}
Student.prototype = Object.create(Person.prototype)
Student.prototype.constructor = Student

ES6继承

// 父类构造函数
class Person {
  constructor (name, age) {
    this.name = name
    this.age = age
  }
}
// 子类构造函数
class Student extends Person {
  constructor (name, age, school) {
    super(name, age)
    this.school = school
  }
}

数据类型判断

使用原生js中的 Object.prototype.toString.call()检测

class Check {
  constructor () {
    const toString = Object.prototype.toString
    ;['String', 'Number', 'Boolean', 'Array',
      'Object', 'Function', 'Date', 'Symbol', 
      'RegExp', 'Undefined', 'Null', 'Error',
      'Map', 'Set'
    ].forEach(name => {
      this[`is${name}`] = function (val) {
        return toString.call(val) === `[object ${name}]`
      }
    })
  }
}

let instance = null

// 单文件实现的代理单例
// 不懂的可以使用闭包替代
class ProxyCheck {
  constructor () {
    return instance || (instance = new Check())
  }
}

export default ProxyCheck

// 示例
// 下面输出的结果为 >>> true
const check = new ProxyCheck()
check.isArray([1])
check.isBoolean(true)
check.isDate(new Date())
check.isError(new Error())
check.isFunction(() => {})
check.isMap(new Map())
check.isNull(null)
check.isNumber(1)
check.isObject({})
check.isRegExp(/a/)
check.isSet(new Set())
check.isString('a')
check.isSymbol(Symbol('a'))
check.isUndefined(void 0)

发布订阅

let events = {}
let instance = null

function returnActives (eventName) {
  let actives = events[eventName]
  if (Array.isArray(actives)) {
    return actives
  }
  return events[eventName] = []
}

class Event {
  // 订阅
  on (eventName, callback) {
    returnActives(eventName).push(callback)
  }
  // 发布
  emit (eventName, param) {
    returnActives(eventName).forEach(callback => {
      callback(param)
    })
  }
  // 取消订阅
  off (eventName, callback) {
    let actives = returnActives(eventName)
    if (typeof (callback) === 'function') {
      for (let i = 0; i < actives.length; i++) {
        if (actives[i] === callback) {
          actives.splice(i, 1)
          break
        }
      }
    } else if (callback === true) {
      events[eventName] = []
    }
  }
  // 只订阅一次
  once (eventName, callback) {
    function callbackWrap (params) {
      callback(params)
      app.off(eventName, callbackWrap)
    }
    app.on(eventName, callbackWrap)
  }
} 

class ProxyEvents {
  constructor () {
    return instance || (instance = new Event())
  }
}

export default ProxyEvents

缓存

Map版本

class CacheCell {
  constructor (data, timeout) {
    // 缓存的数据
    this.data = data
    // ���置超时时间，单位秒
    this.timeout = timeout
    // 对象创建时候的时间
    this.createTime = Date.now()
  }
}

let cacheMap =  new Map()
let instance = null
let timeoutDefault = 1200

function isTimeout (name) {
  const data = cacheMap.get(name)
  if (!data) return true
  if (data.timeout === 0) return false
  const currentTime = Date.now()
  const overTime = (currentTime - data.createTime) / 1000
  if (overTime > data.timeout) {
    cacheMap.delete(name)
    return true
  }
  return false
}

class Cache {
  // 将数据存储在缓存中指定的 name 中
  // timeout设置为0表示永久缓存
  set (name, data, timeout = timeoutDefault) {
    const cachecell = new CacheCell(data, timeout)
    return cacheMap.set(name, cachecell)
  }
  // 从缓存中获取指定 name 对应的内容
  get (name) {
    return isTimeout(name) ? null : cacheMap.get(name).data
  }
  // 从缓存中移除指定 name
  delete (name) {
    return cacheMap.delete(name)
  }
  // 返回一个布尔值，表示 name 是否在缓存之中
  has (name) {
    return !isTimeout(name)
  }
  // 清空数据缓存
  clear () {
    return cacheMap.clear()
  }
  // 设置缓存默认时间
  setTimeoutDefault (num) {
    if (timeoutDefault === 1200) {
      return timeoutDefault = num
    }
    throw Error('缓存器只能设置一次默认过期时间')
  }
}

class ProxyCache {
  constructor () {
    return instance || (instance = new Cache())
  }
}

export default ProxyCache

LocalStorage版本

class LocalStorageCacheCell {
  constructor (data, timeout) {
    // 缓存的数据
    this.data = data
    // 设置超时时间，单位秒
    this.timeout = timeout
    // 对象创建时候的时间
    this.createTime = Date.now()
  }
}

let instance = null
let timeoutDefault = 1200

function isTimeout (name) {
  const data = JSON.parse(localStorage.getItem(name))
  if (!data) return true
  if (data.timeout === 0) return false
  const currentTime = Date.now()
  const overTime = (currentTime - data.createTime) / 1000
  if (overTime > data.timeout) {
    localStorage.removeItem(name)
    return true
  }
  return false
}

class LocalStorageCache {
  // 将数据存储在本地缓存中指定的 name 中
  // timeout设置为0表示永久缓存
  set (name, data, timeout = timeoutDefault) {
    const cachecell = new LocalStorageCacheCell(data, timeout)
    return localStorage.setItem(name, JSON.stringify(cachecell))
  }
  // 从本地缓存中获取指定 name 对应的内容
  get (name) {
    return isTimeout(name) ? null : JSON.parse(localStorage.getItem(name)).data
  }
  // 从本地缓存中移除指定 name
  delete (name) {
    return localStorage.removeItem(name)
  }
  // 返回一个布尔值，表示 name 是否在本地缓存之中
  has (name) {
    return !isTimeout(name)
  }
  // 清空本地数据缓存
  clear () {
    return localStorage.clear()
  }
  // 设置缓存默认时间
  setTimeoutDefault (num) {
    if (timeoutDefault === 1200) {
      return timeoutDefault = num
    }
    throw Error('缓存器只能设置一次默认过期时间')
  }
}

class ProxyLocalStorageCache {
  constructor () {
    return instance || (instance = new LocalStorageCache())
  }
}

export default ProxyLocalStorageCache

AOP

面向切面编程：动态地将代码切入到类的指定方法、指定位置上的编程思想就是面向切面的编程。

Function.prototype.before = function (beforeFn) {
  const _self = this
  return function () {
    beforeFn.apply(this, arguments)
    return _self.apply(this, arguments)
  }
}

Function.prototype.after = function (afterFn) {
  const _self = this
  return function () {
    const ret = _self.apply(this, arguments)
    afterFn.apply(this, arguments)
    return ret
  }
}

// 示例
function test () {
  console.log(test)
}
test = test.before(function(){
  console.log('before')
}).after(function(){
  console.log('after')
})
test()
// >>> before
// >>> test
// >>> after

防抖

指触发事件后在 n 秒内函数只能执行一次，如果在 n 秒内又触发了事件，则会重新计算函数执行时间。

// immediate = true >>> 事件触发时立即执行，然后一定时间后才能再次执行
// immediate = false >>> 规定一定时间后只执行一次
function debounce (func, wait, immediate = true) {
  let timeout
  function debounced () {
    if (timeout) clearTimeout(timeout)
    let callNow = !timeout && immediate
    timeout = setTimeout(() => {
      timeout = null
      if (!immediate) {
        func.apply(this, arguments)
      }
    }, wait)
    if (callNow) func.apply(this, arguments)
  }
  debounced.cancel = function () {
    clearTimeout(timeout)
    timer = null
  }
  return debounced
}

节流

指连续触发事件但是在 n 秒中只执行一次函数。

// immediate = true >>> 事件触发时立即执行，触发完毕还能执行一次
// immediate = false >>> 规定时间内一定执行一次，触发完毕还能执行一次
function throttle(func, wait, immediate = true) {
  let timeout
  if (immediate) {
    let prev = 0
    return function () {
      let now = Date.now()
      clearTimeout(timeout)
      if (now - prev > wait) {
        func.apply(this, arguments)
        prev = now
      } else {
        timeout = setTimeout(() => {
          timeout = null
          func.apply(this, arguments)
        }, wait)
      }
    }
  }
  return function () {
    if (!timeout) {
      timeout = setTimeout(() => {
        timeout = null
        func.apply(this, arguments)
      }, wait)
    }
  }
}

数组扁平化

指将一个多维数组变为一维数组

function flatten (array) {
  return array.reduce((preValue, curValue) => {
    return preValue.concat(Array.isArray(curValue) ? flatten(curValue) : curValue)
  }, [])
}

// 示例
const array = [1, [2, [3, [4, [5, [6, [7]]]]]]]
flatten(array)
// >>> [1, 2, 3, 4, 5, 6, 7]

数组去重

const array1 = [1, 1, 2, 3, 3]
const array2 = [...new Set(array1)]
// array2 >>> [1, 2, 3]

数组合并

const array1 = [1, 2, 3]
const array2 = [4, 5, 6]
const array3 = [...array1, ...array2]
// array3 >>> [1, 2, 3, 4, 5, 6]

数据结构

栈

(1)、什么是栈

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。

(2)、栈有什么作用

栈是非常底层的东西，在编程语言的编译器和内存中保存变量、方法调用。

(3)、栈结构概念

入栈、出栈、栈顶、栈底。

class Stack {
  constructor () {
    // 私有属性
    this._items = []
  }
  // 栈顶添加元素
  push (el) {
    this._items.push(el)
  }
  // 栈顶移除元素
  pop () {
    return this._items.pop()
  }
  // 检查栈顶
  peek () {
    return this._items[this._items.length - 1]
  }
  // 检查栈是否为空
  isEmpty () {
    return this._items.length === 0
  }
  // 清除栈
  clear () {
    this._items = []
  }
  // 查看栈的大小
  size () {
    return this._items.length
  }
}

方法名说明 push 栈顶添加元素 pop 栈顶移除元素 peek 检查栈顶 isEmpty 检查栈是否为空 clear 清除栈 size 查看栈的大小

队列

（1）、什么是队列

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的端是队尾，允许删除的端是队头。队列是一个先进先出的线性表。

（2）、队列结构概念

入队、出队、队列头、队列尾。

class Queue {
  constructor () {
    // 私有属性
    this._items = []
  }
  // 入队
  enqueue (el) {
    this._items.push(el)
  }
  // 出队
  dequeue () {
    return this._items.shift()
  }
  // 查看队列头
  front () {
    return this._items[0]
  }
  // 检查队列是否为空
  isEmpty () {
    return this._items.length === 0
  }
  // 查看队列的大小
  size () {
    return this._items.length
  }
  // 清除队列
  clear () {
    this._items = []
  }
}

方法名说明 enqueue 入队 dequeue 出队 front 查看队列头 isEmpty 检查队列是否为空 size 查看队列的大小 clear 清除队列

链表

（1）、什么是链表

链表是一种物理存储单元上非连续、非顺序的存储结构。

（2）、为什么要学习链表

链表和数组作为算法中两个基本数据结构，在程序设计过程中经常使用。尽管两种结构都可以用来存储一系列的数据，但又各有各的特点。

数组的优势，在于可以方便的遍历查找需要的数据。在查询数组指定位置的操作中，只需要进行一次操作即可，时间复杂度为O(1)。但是，这种时间上的便利性，是因为数组在内存中占用了连续的空间，在进行类似的查找或者遍历时，本质是指针在内存中的定向偏移。然而，当需要对数组成员进行添加和删除的操作时，数组内完成这类的操作时间复杂度则变成了O(n)。

链表的特性，使其在某些操作上比数组更加高效。例如当进行插入和删除操作时，链表的操作的时间复杂度仅为O(1)。另外，因为链表在内存不是连续存储的，所以可以充分利用内存中的碎片空间。除此之外，链表还是很多算法的基础，最常见的哈希表就是基于链表来实现的。

基于以上原因，可以看到，链表在程序设计过程中是非常重要的。

1、单向链表

class LinkedList {
  // 构造函数
  constructor () {
    // 私有属性链表头
    this._head = null
    // 私有属性链表尾
    this._last = null
    // 私有属性代表链表的长度
    this._length = 0
    // 内部辅助类
    LinkedList.Node = class {
      constructor (el, next) {
        // 当前节点的元素
        this.el = el
        // 下一个节点链接
        this.next = next
      }
    }
  }
  // 私有方法根据索引获取节点
  _nodeIndex (index) {
    let node = this._head
    for (let i = 0; i < index; i++) {
      node = node.next
    }
    return node
  }
  // 链表尾添加元素
  append (el) {
    if (!this._head) {
      // 当链表头为空时，向链表头添加节点，同时向链表尾添加节点
      this._head = new LinkedList.Node(el, null)
      this._last = this._head
    } else {
      let node = new LinkedList.Node(el, null)
      // 向链表尾添加节点
      this._last.next = node
      // 重设链表尾
      this._last = node
    }
    // 记录列表长度
    this._length++
    return true
  }
  // 在链表中插入元素
  insert (index, el) {
    if (index < 0 || index > this._length) return false
    // 当index === 0表示向链表头插入元素
    if (index === 0) {
      // 当链表头为空时，向链表头添加节点，同时向链表尾添加节点
      if (!this._head) {
        this._head = new LinkedList.Node(el, null)
        this._last = this._head
      } else {
        this._head = new LinkedList.Node(el, this._head)
      }
    } else {
      // 获取当前需要插入的前一个节点
      let previous = this._nodeIndex(index - 1)
      let node = new LinkedList.Node(el, previous.next)
      previous.next = node
      // 判断是否插入链表尾
      if (index === this._length) {
        // 重设链表尾
        this._last = node
      }
    }
    // 记录列表长度
    this._length++
    return true
  }
  // 删除指定位置的元素
  removeAt (index) {
    if (index < 0 || index > this._length - 1) return false
    let current = null
    // 当index === 0表示删除链表头元素
    if (index === 0) {
      // 缓存链表头
      current = this._head
      // 改变链表头
      this._head = current.next
    } else {
      // 获取当前需要删除的前一个节点
      let previous = this._nodeIndex(index - 1)
      // 获取当前需要删除的节点
      current = previous.next
      // 删除元素
      previous.next = current.next
      // 判断是否删除链表尾
      if (index === this._length - 1) {
        // 重设链表尾
        this._last = previous
      }
    }
    // 记录列表长度
    this._length--
    return current.el
  }
  // 获取指定元素的索引位置
  indexOf (el) {
    // 索引
    let index = 0
    // 缓存链表头
    let current = this._head
    while (current) {
      // 判断给定的元素是否等于当前元素节点的元素
      // 如果时引用类型的还需要自定义判断引用类型是否相等
      if (el === current.el) {
        // 如果相等就返回索引
        return index
      }
      current = current.next
      index++
    }
    return -1
  }
  // 根据索引获取元素
  get (index) {
    if (index < -1 && index >= this._length) throw Error('越界异常')
    return this._nodeIndex(index).el
  }
  // 根据索引修改元素
  set (index, el) {
    if (index < -1 && index >= this._length) throw Error('越界异常')
    return this._nodeIndex(index).el = el
  }
  // 获取链表头
  getHead () {
    return this._head
  }
  // 获取链表尾
  getLast () {
    return this._last
  }
  // 删除指定的元素
  remove (el) {
    return this.removeAt(this.indexOf(el))
  }
  // 检查链表是否为空
  isEmpty () {
    return this._length === 0
  }
  // 获取链表的大小
  size () {
    return this._length
  }
  // 清空链表
  clear () {
    this._head = null
    this._length = null
    this._length = 0
  }
}

2、单向循环链表

class LinkedList {
  constructor () {
    this._head = null
    this._last = null
    this._length = 0;
    LinkedList.Node = class {
      constructor (el, next) {
        this.el = el
        this.next = next
      }
    }
  }
  _nodeIndex (index) {
    let node = this._head
    for (let i = 0; i < index; i++) {
      node = node.next
    }
    return node
  }
  append (el) {
    if (!this._head) {
      this._head = new LinkedList.Node(el, null)
      // ========= 不同点 =========
      // 链表尾指向链表头
      this._head.next = this._head
      this._last = this._head
    } else {
      // ========= 不同点 =========
      // 初始化给定链表头
      let node = new LinkedList.Node(el, this._head)
      this._last.next = node
      this._last = node
    }
    this._length++
    return true
  }
  insert (index, el) {
    if (index < 0 || index > this._length) return false
    if (index === 0) {
      if (!this._head) {
        this._head = new LinkedList.Node(el, null)
        // ========= 不同点 =========
        // 链表尾指向链表头
        this._head.next = this._head
        this._last = this._head
      } else {
        this._head = new LinkedList.Node(el, this._head)
        // ========= 不同点 =========
        // 链表尾指向新的链表头
        this._last.next = this._head
      }
    } else {
      let previous = this._nodeIndex(index - 1)
      let node = new LinkedList.Node(el, previous.next)
      previous.next = node
      if (index === this._length) {
        this._last = node
      }
    }
    this._length++
    return true
  }
  removeAt (index) {
    if (index < 0 || index > this._length - 1) return false
    let current = null
    if (index === 0) {
      current = this._head
      this._head = current.next
      // ========= 不同点 =========
      // 链表尾指向新的链表头
      this._last.next = this._head
    } else {
      let previous = this._nodeIndex(index - 1)
      current = previous.next
      previous.next = current.next
      if (index === this._length - 1) {
        this._last = previous
        // ========= 不同点 =========
        // 新的链表尾指向链表头
        this._last.next = this._head
      }
    }
    this._length--
    return current.el
  }
  indexOf (el) {
    let index = 0
    let current = this._head
    while (current) {
      if (el === current.el) {
        return index
      }
      current = current.next
      index++
    }
    return -1
  }
  get (index) {
    if (index < -1 && index >= this._length) throw Error('越界异常')
    return this._nodeIndex(index).el
  }
  set (index, el) {
    if (index < -1 && index >= this._length) throw Error('越界异常')
    return this._nodeIndex(index).el = el
  }
  getHead () {
    return this._head
  }
  getLast () {
    return this._last
  }
  remove (el) {
    return this.removeAt(this.indexOf(el))
  }
  isEmpty () {
    return this._length === 0
  }
  size () {
    return this._length
  }
  clear () {
    this._head = null
    this._length = null
    this._length = 0
  }
}

3、双向链表

class LinkedList {
  // 构造函数
  constructor () {
    // 私有属性链表头
    this._head = null
    // 私有属性链表尾
    this._last = null
    // 私有属性代表链表的长度
    this._length = 0;
    // 内部辅助类
    LinkedList.Node = class {
      constructor (previous, el, next) {
        // 上一个节点链接
        this.previous = previous
        // 当前节点的元素
        this.el = el
        // 下一个节点链接
        this.next = next
      }
    }
  }
  // 私有方法根据索引获取节点
  _nodeIndex (index) {
    let node = this._head
    for (let i = 0; i < index; i++) {
      node = node.next
    }
    return node
  }
  // 链表尾添加元素
  append (el) {
    if (!this._head) {
      // 当链表头为空时，向链表头添加节点，同时向链表尾添加节点
      this._head = new LinkedList.Node(null, el, null)
      this._last = this._head
    } else {
      let node = new LinkedList.Node(this._last, el, null)
      // 向链表尾添加节点
      this._last.next = node
      // 重设链表尾
      this._last = node
    }
    // 记录列表长度
    this._length++
    return true
  }
  // 在链表中插入元素
  insert (index, el) {
    if (index < 0 || index > this._length) return false
    // 当index === 0表示向链表头插入元素
    if (index === 0) {
      // 当链表头为空时，向链表头添加节点，同时向链表尾添加节点
      if (!this._head) {
        this._head = new LinkedList.Node(null, el, null)
        this._last = this._head
      } else {
        let node = this._head
        this._head = new LinkedList.Node(null, el, node)
        node.previous = this._head
      }
    } else {
      // 获取当前需要插入的前一个节点
      let previous = this._nodeIndex(index - 1)
      let node = new LinkedList.Node(previous, el, previous.next)
      previous.next = node
      // 判断是否插入链表尾
      if (previous.next) {
        // 重设链表尾
        this._last = node
      }
    }
    // 记录列表长度
    this._length++
    return true
  }
  // 删除指定位置的元素
  removeAt (index) {
    if (index < 0 || index > this._length - 1) return false
    let current = null
    // 当index === 0表示删除链表头元素
    if (index === 0) {
      // 缓存链表头
      current = this._head
      // 改变链表头
      this._head = current.next
      this._head.previous = null
    } else {
      // 获取当前需要删除的前一个节点
      let previous = this._nodeIndex(index - 1)
      // 获取当前需要删除的节点
      current = previous.next
      // 删除元素
      previous.next = current.next
      // 判断是否删除链表尾
      if (index === this._length - 1) {
        // 重设链表尾
        this._last = previous
      } else {
        current.next.previous = previous
      }
    }
    // 记录列表长度
    this._length--
    return current.el
  }
  // 获取指定元素的索引位置
  indexOf (el) {
    // 索引
    let index = 0
    // 缓存链表头
    let current = this._head
    while (current) {
      // 判断给定的元素是否等于当前元素节点的元素
      // 如果时引用类型的还需要自定义判断引用类型是否相等
      if (el === current.el) {
        // 如果相等就返回索引
        return index
      }
      current = current.next
      index++
    }
    return -1
  }
  // 根据索引获取元素
  get (index) {
    if (index < -1 && index >= this._length) throw Error('越界异常')
    return this._nodeIndex(index).el
  }
  // 根据索引修改元素
  set (index, el) {
    if (index < -1 && index >= this._length) throw Error('越界异常')
    return this._nodeIndex(index).el = el
  }
  // 获取链表头
  getHead () {
    return this._head
  }
  // 获取链表尾
  getLast () {
    return this._last
  }
  // 删除指定的元素
  remove (el) {
    return this.removeAt(this.indexOf(el))
  }
  // 检查链表是否为空
  isEmpty () {
    return this._length === 0
  }
  // 获取链表的大小
  size () {
    return this._length
  }
  // 清空链表
  clear () {
    this._head = null
    this._length = null
    this._length = 0
  }
}

4、双向循环链表

class LinkedList {
  constructor () {
    this._head = null
    this._last = null
    this._length = 0;
    LinkedList.Node = class {
      constructor (previous, el, next) {
        this.previous = previous
        this.el = el
        this.next = next
      }
    }
  }
  _nodeIndex (index) {
    let node = this._head
    for (let i = 0; i < index; i++) {
      node = node.next
    }
    return node
  }
  append (el) {
    if (!this._head) {
      this._head = new LinkedList.Node(null, el, null)
      // ========= 不同点 =========
      // 链表头的下一个和上一个指向指向自己
      this._head.next = this._head
      this._head.previous = this._head
      this._last = this._head
    } else {
      // ========= 不同点 =========
      // 创建节点给定上一个和下一个的指向
      let node = new LinkedList.Node(this._last, el, this._head)
      this._last.next = node
      this._last = node
      // 改变链表头的上一个指向
      this._head.previous = this._last
    }
    this._length++
    return true
  }
  insert (index, el) {
    if (index < 0 || index > this._length) return false
    if (index === 0) {
      if (!this._head) {
        this._head = new LinkedList.Node(null, el, null)
        // ========= 不同点 =========
        // 链表头的下一个和上一个指向指向自己
        this._head.next = this._head
        this._head.previous = this._head
        this._last = this._head
      } else {
        let node = this._head
        // ========= 不同点 =========
        // 需要改变链表尾的下一个指向
        this._head = new LinkedList.Node(this._last, el, node)
        node.previous = this._head
        this._last.next = this._head
      }
    } else {
      let previous = this._nodeIndex(index - 1)
      let node = new LinkedList.Node(previous, el, previous.next)
      // ========= 不同点 =========
      // 需要改变插入后的上一个指向
      previous.next.previous = node
      previous.next = node
      if (index === this._length) {
        this._last = node
      }
    }
    this._length++
    return true
  }
  removeAt (index) {
    if (index < 0 || index > this._length - 1) return false
    let current = null
    if (index === 0) {
      current = this._head
      this._head = current.next
      // ========= 不同点 =========
      this._head.previous = this._last
      this._last.next = this._head
    } else {
      let previous = this._nodeIndex(index - 1)
      current = previous.next
      previous.next = current.next
      // ========= 不同点 =========
      current.next.previous = previous
      if (index === this._length - 1) {
        this._last = previous
      }
    }
    this._length--
    return current.el
  }
  indexOf (el) {
    let index = 0
    let current = this._head
    while (current) {
      if (el === current.el) {
        return index
      }
      current = current.next
      index++
    }
    return -1
  }
  get (index) {
    if (index < -1 && index >= this._length) throw Error('越界异常')
    return this._nodeIndex(index).el
  }
  set (index, el) {
    if (index < -1 && index >= this._length) throw Error('越界异常')
    return this._nodeIndex(index).el = el
  }
  getHead () {
    return this._head
  }
  getLast () {
    return this._last
  }
  remove (el) {
    return this.removeAt(this.indexOf(el))
  }
  isEmpty () {
    return this._length === 0
  }
  size () {
    return this._length
  }
  clear () {
    this._head = null
    this._last = null
    this._length = 0
  }
}

方法名说明 append 链表尾添加元素 insert 在链表中插入元素 removeAt 删除指定位置的元素 indexOf 获取指定元素的索引位置 get 根据索引获取元素 set 根据索引修改元素 getHead 获取链表头 getLast 获取链表尾 remove 删除指定的元素 isEmpty 检查链表是否为空 size 获取链表的大小 clear 清空链表

集合

（1）、什么是集合

集合，简称集，是数学中一个基本概念。

（2）、集合的特性：

确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。

互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画，可以使用多重集，其中的元素允许出现多次。

无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。集合上可以定义序关系，定义了序关系后，元素之间就可以按照序关系排序。但就集合本身的特性而言，元素之间没有必然的序。

// 注意: 集合里键和值一样
class MySet {
  constructor () {
    // 私有属性
    this._items = {}
  }
  // 检查元素是否存在
  has (value) {
    return this._items.hasOwnProperty(value)
  }
  // 添加元素
  add (value) {
    // 当元素不存在进行添加，否则返回false
    if (!this.has(value)) {
      this._items[value] = value
      return value
    }
    return false
  }
  // 删除元素
  delete (value) {
    if (this.has(value)) {
      // 删除对象属性
      delete this._items[value]
      return true
    }
    return false
  }
  // 清空集合
  clear () {
    this._items = {}
  }
  // 获取集合的大小
  size () {
    return Object.keys(this._items).length
  }
  // 获取所有的值
  values () {
    return Object.values(this._items)
  }
  // ================= 集合之间的操作 ====================
  // 并集
  union (otherSet) {
    let res = new MySet()
    this.values().forEach(el => {
      res.add(el)
    })
    otherSet.values().forEach(el => {
      res.add(el)
    })
    return res
  }
  // 交集
  intersection (otherSet) {
    let res = new MySet()
    this.values.forEach(el => {
      if (otherSet.has(el)) {
        res.add(el)
      }
    })
    return res
  }
  // 补集
  subtract (otherSet) {
    let res = new MySet()
    this.values().forEach(el => {
      if (!otherSet.has(el)) {
        res.add(el)
      }
    })
  }
  // 交集的补集
  exclusiveOr (otherSet) {
    let res = new MySet()
    this.subtract(otherSet).values().forEach(el => {
      res.add(el)
    })
    otherSet.subtract(this).values().forEach(el => {
      res.add(el)
    })
    return res
  }
  // ================= 集合之间的操作 ====================
}

方法名说明 has 检查元素是否存在 add 添加元素 delete 删除元素 clear 清空集合 size 获取集合的大小 values 获取所有的值 union 并集 intersection 交集 subtract 补集 exclusiveOr 交集的补集

字典

（1）、什么是字典

字典是一种以键-值对形式存储数据的数据结构

class Dictionary {
  constructor () {
    // 私有属性
    this._items = {}
  }
  // 检查键是否存在
  has (key) {
    // return key in this._items
    return this._items.hasOwnProperty(key)
  }
  // 添加键值对
  set (key, value) {
    this._items[key] = value
  }
  // 通过键删除
  delete (key) {
    // 判断键存不存在
    if (this.has(key)) {
      delete this._items[key]
      return true
    }
    return false
  }
  // 通过键获取数据
  get (key) {
    // 判断键存不存在
    if (this.has(key)) {
      return this._items[key]
    }
    return undefined
  }
  // 获取所有的键
  keys () {
    return Object.keys(this._items)
  }
  // 清空字典
  clear () {
    this._items = {}
  }
}

方法名说明 has 检查键是否存在 set 添加键值对 delete 通过键删除 get 通过键获取数据 keys 获取所有的键 clear 清空字典下面来道算法题（两数之和）（题型引自LeetCode）给定一个整数数组nums和一个目标值target，请你在该数组中找出和目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

暴力法：

function twoSum (nums, target) {
  let arr = []
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        arr = [i, j]
      }
    } 
  }
  return arr
}

字典实现：

function twoSum (nums, target) {
    let dictionary = new Dictionary()
    for (let i = 0; i < nums.length; i++) {
       let val = target - nums[i]
       if (dictionary.has(val)) return [dictionary.get(val), i]
       dictionary.set(nums[i], i)
    }
}

使用Map实现：

function twoSum (nums, target) {
    let map = new Map()
    for (let i = 0; i < nums.length; i++) {
       let val = target - nums[i]
       if (map.has(val)) return [map.get(val), i]
       map.set(nums[i], i)
    }
}

哈希表

（1）、什么时哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

（2）、为什么需要哈希表

数组的特点是：寻址容易，插入和删除困难。

链表的特点是：寻址困难，插入和删除容易。

哈希表就是综合两者的特性，寻址容易，插入删除也容易的数据结构。

1、基本哈希表

缺点：散列冲突，不同的key经过散列函数的计算得到了相同的散列地址。

class HashTable {
  // 构造函数
  constructor () {
    // 私有属性
    this._items = []
  }
  // 私有方法
  // 散列函数
  // 散列值重复性太高了
  _loseloseHashCode (key) {
    let hash = 0
    for (let i = 0; i < key.length; i++) {
      hash += key[i].charCodeAt()
    }
    return hash % 37
  }
  // 私有方法
  // 散列函数
  // 比上面的更好
  _djb2HashCode (key) {
    let hash = 5381
    for (let i = 0; i < key.length; i++) {
      hash = hash * 33 + key[i].charCodeAt
    }
    return hash % 1013
  }
  // 添加
  put (key, value) {
    // 获取散列值
    // const position = this._djb2HashCode(key)
    const position = this._loseloseHashCode(key)
    this._items[position] = value
  }
  // 获取
  get (key) {
    // const position = this._djb2HashCode(key)
    const position = this._loseloseHashCode(key)
    return this._items[position]
  }
  // 删除
  remove (key) {
    // const position = this._djb2HashCode(key)
    const position = this._loseloseHashCode(key)
    this._items[position] = undefined
  }
  // 清空哈希表
  clear () {
    this._items = []
  }
}

2、分离链接法

散列表的每个单元是一个链表

将散列到同一个值的所有元素保留到一个链表中

优点：解决散列冲突

缺点：性能打折

class HashTable {
  // 构造函数
  constructor () {
    // 私有属性
    this._items = []
    // 内部辅助类
    HashTable.Node = class {
      constructor (key, value) {
        this.key = key
        this.value = value
      }
    }
  }
  _loseloseHashCode (key) {
    let hash = 0
    for (let i = 0; i < key.length; i++) {
      hash += key[i].charCodeAt()
    }
    return hash % 37
  }
  _djb2HashCode (key) {
    let hash = 5381
    for (let i = 0; i < key.length; i++) {
      hash = hash * 33 + key[i].charCodeAt
    }
    return hash % 1013
  }
  put (key, value) {
    const position = this._loseloseHashCode(key)
    // 插入的时候先判断当前位置是否为空，如果为空就创建链表再添加数据
    if (this._items[position]) {
      this._items[position].append(new HashTable.Node(key, value))
    } else {
      // 使用链表
      // 注意这里不能使用循环链表
      // 不懂的可以看上面的链表实现
      let l = new LinkedList()
      this._items[position] = l
      l.append(new HashTable.Node(key, value))
    }
  }
  get (key) {
    const position = this._loseloseHashCode(key)
    if (this._items[position]) {
      let current = this._items[position].getHead()
      // 上面提到不能使用循环链表，是因为这里判断会造成死循环
      while (current) {
        if (current.el.key === key) {
          return current.el.value
        }
        current = current.next
      }
    } else {
      return undefined
    }
  }
  remove (key) {
    const position = this._loseloseHashCode(key)
    if (this._items[position]) {
      let current = this._items[position].getHead()
      while (current) {
        if (current.el.key === key) {
          let res = this._items[position].remove(current.el)
          if (this._items[position].isEmpty()) {
            this._items[position] = undefined
          }
          return res
        }
        current = current.next
      }
    } else {
      return false
    }
  }
  clear () {
    this._items = []
  }
}

3、线性探查法

线性探测是计算机程序解决散列表冲突时所采取的一种策略。

优点：解决散列冲突

缺点：性能打折

class HashTable {
  // 构造函数
  constructor () {
    // 私有属性
    this._items = []
    // 内部辅助类
    HashTable.Node = class {
      constructor (key, value) {
        this.key = key
        this.value = value
      }
    }
  }
  _loseloseHashCode (key) {
    let hash = 0
    for (let i = 0; i < key.length; i++) {
      hash += key[i].charCodeAt()
    }
    return hash % 37
  }
  _djb2HashCode (key) {
    let hash = 5381
    for (let i = 0; i < key.length; i++) {
      hash = hash * 33 + key[i].charCodeAt
    }
    return hash % 1013
  }
  put (key, value) {
    let position = this._loseloseHashCode(key)
    // 插入的时候先判断当前位置是否为空，如果不为空就接着往后直到找到空位置
    if (!this._items[position]) {
      this._items[position] = new HashTable.Node(key, value)
    } else {
      while (this._items[++position]) {
        this._items[position] = new HashTable.Node(key, value)
      }
    }
  }
  get (key) {
    const position = this._loseloseHashCode(key)
    // 查找时先判断是否为空，如果不为空就判断key是否相等，不相等就往下找
    for (let i = position; this._items[position]; i++) {
      if (this._items[i].key === key) {
        return this._items[i].value
      }
    }
    return undefined
  }
  remove (key) {
    const position = this._loseloseHashCode(key)
    for (let i = position; this._items[position]; i++) {
      if (this._items[position].key === key) {
        let res = this._items[i].value
        this._items[i] = undefined
        return res
      }
    }
    return undefined
  }
  clear () {
    this._items = []
  }
}

方法名说明 put 添加 get 获取 remove 删除 clear 清空哈希表

树

树形结构是一层次的嵌套结构。一个树形结构的外层和内层有相似的结构，所以这种结构多可以递归的表示。经典数据结构中的各种树状图是一种典型的树形结构：一颗树可以简单的表示为根，左子树，右子树。左子树和右子树又有自己的子树。

class Tree {
  constructor () {
    // 私有变量根
    this._root = null
    // 内部辅助类
    Tree.Node = class {
      constructor (el) {
        this.el = el
        this.left = null
        this.rigth = null
      }
    }
  }
  // 私有方法
  _insertNode (node, newNode) {
    // left方向
    if (newNode.el < node.el) {
      if (!node.left) {
        node.left = newNode
      } else {
     this._insertNode(node.left, newNode)
      }
    }
    // rigth方向
    if (newNode.el > node.el) {
      if (!node.rigth) {
        node.rigth = newNode
      } else {
        this._insertNode(node.rigth, newNode)
      }
    }
  }
  // 私有方法
  _searchNode (node, el) {
    if (node) return false
    if (node.el = el) return true
    if (node.el > el) this._searchNode(node.rigth, el)
    if (node.el < el) this._searchNode(node.left, el)
  }
  // 私有方法
  _removeNode (node, el) {
    if (!node) return null
    if (node.el > el) {
      node.left = this._removeNode(node.left, el)
      return node
    }
    if (node.el < el) {
      node.rigth = this._removeNode(node.rigth, el)
      return node
    }
    if (node.el === el) {
      if (!node.left && !node.rigth) {
        return null
      }
      if (node.left && !node.rigth) {
        return node.left
      }
      if (!node.left && node.rigth) {
        return node.rigth
      }
      if (node.left && node.rigth) {
        let minNode = this._minNode(node.rigth)
        node.el = minNode.el
        node.rigth = this._removeNode(node.rigth, minNode.el)
        return node
      }
    }
  }
  // 私有方法
  // 深度优先遍历可进一步按照根节点与其左右子节点的访问先后顺序划分为前序遍历、中序遍历和后序遍历。
  // 根节点放在左节点的左边，称为前序遍历；
  // 根节点放在左节点和右节点的中间，称为中序遍历；
  // 根节点放在右节点的右边，称为后序遍历。
  _traverseNode (node, callback) {
    // 终止条件
    if (!node) return
    // 前序遍历
    // callback(node.el)
    this._traverseNode(node.left, callback) 
    // 中序遍历
    // callback(node.el)
    this._traverseNode(node.rigth, callback)
    // 后序遍历
    callback(node.el)
  }
  // 私有方法
  // 栈与深度优先遍历
  // 只是实现了前序遍历
  // 中序遍历、后序遍历，读者可以自行编写，递归本身就和栈相关
  _traverseNodeStack (callback) {
    // 初始化栈并将根节点压栈
    let stack = new Stack()
    stack.push(this._root)
    // 循环遍历直到栈为空
    while (!stack.isEmpty()) {
      // 出栈，并对其域进行访问
      let node = stack.pop()
      callback(node.el)
      // 判断rigth节点是否为空，如果不为空，入栈处理
      if (node.rigth) stack.push(node.rigth)
      // 判断left节点是否为空，如果不为空，入栈处理
      if (node.left) stack.push(node.left)
    }
  }
  // 私有方法
  // 队列与广度优先遍历
  // 从根节点开始，一层一层的访问。实现的核心是通过队列的入队和出队操作
  _traverseNodeQueue (callback) {
    // 初始化队列并将根节点入队
    let queue = new Queue()
    queue.enqueue(this._root)
    // 循环遍历队列直到队列为空
    while (!queue.isEmpty()) {
      // 出队，并对其域进行访问
      let node = queue.dequeue()
      callback(node.el)
      // 判断left节点是否为空，如果不为空，入队处理
      if (node.left) queue.enqueue(node.left)
      // 判断rigth节点是否为空，如果不为空，入队处理
      if (node.rigth) queue.enqueue(node.rigth)
    }
  }
  // 私有方法
  _minNode (node) {
    if (!node) return null
    while (node && node.left) {
      node = node.left
    }
    return node
  }
  // 私有方法
  _max (node) {
    if (!node) return null
    while (node && node.rigth) {
      node = node.rigth
    }
    return node.el
  }
  // 插入节点
  insert (el) {
    if (!this._root) {
      this._root = new Tree.Node(el)
    } else {
      this._insertNode(this._root, new Tree.Node(el))
    }
  }
  // 搜索节点
  search (el) {
    return this._searchNode(this._root, el)
  }
  // 最小值
  min () {
    let node = this._minNode(this._root)
    if (node) {
      return node.el
    }
    return null
  }
  // 最大值
  max () {
    return this._max(this._root)
  }
  // 删除节点
  remove (el) {
    this._root = this._removeNode(this._root, el)
  }
  // 遍历节点
  traverse (callback) {
    // this._traverseNode(this._root, callback)
    // this._traverseNodeStack(callback)
    this._traverseNodeQueue(callback)
  }
  // 获取树
  getTree () {
    return this._root
  }
}

// 示例：
let tree = new Tree()
tree.insert(11)
tree.insert(8)
tree.insert(6)
tree.insert(9)
tree.insert(12)
tree.insert(10)
tree.insert(13)
tree.traverse(console.log)
// 树结构如下：
            11
         8      12
       6   9       13
             10
// 递归前序 >>> 11 8 6 9 10 12 13
// 递归中序 >>> 6 8 9 10 11 12 13
// 递归后续 >>> 6 10 9 8 13 12 11
// 栈与深度优先遍历 >>> 11 8 6 9 10 12 13
// 队列与广度优先遍历 >>> 11 8 12 6 9 13 10

方法名说明 insert 插入节点 search 搜索节点 min 最小值 max 最大值 remove 删除节点 traverse 遍历节点 getTree 获取树

排序算法

冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

function bubbleSort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
      }
    }
  }
}

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

function quickSort (arr) {
  function quick (arr, start, end) {
    // 终止条件
    if (start >= end) return
    // 分界值
    let stard = arr[start]
    // 标记从分界值开始向左找比 stard 大的数的位置
    let low = start
    // 标记右侧 high 向左找比 stard 小的数的位置
    let high = end
    while (low < high) {
      // 从 high 开始向左，找到第一个比 stard 小或者等于 stard 的数，标记位置
      while (low < high && stard <= arr[high]) {
        high--
      }
      // 把找到的数放到左侧的空位 low 标记了这个空位
      arr[low] = arr[high]
      // 从分界值开始向左找，找到第一个比 stard 大或者等于 stard 的数，标记位置
      while (low < high && arr[low] <= stard) {
        low++
      }
      // 把找到的数放到左侧的空位 high 标记了这个空位
      arr[high] = arr[low]
    }
    arr[low] = stard
    // 对 stard 左侧所有数进行上述的排序
    quick(arr, start, low - 1)
    // 对 stard 右侧所有数进行上述的排序
    quick(arr, low + 1, end)
  }
  quick(arr, 0, arr.length - 1)
}

插入排序

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

function insertSort (arr) {
  for (let i = 1; i < arr.length; i++) {
    // 如果当前的值比前一个值小
    if (arr[i] < arr[i - 1]) {
      // 把当前的值缓存下来
      let temp = arr[i]
      let j = i -1
      // 遍历当前位置前面所有的值
      for (; j >= 0 && arr[j] > temp; j--) {
        // 把当前的值赋值给后一位
        arr[j + 1] = a[j]
      }
      // 把临时变量赋值给不满足条件的后一位
      arr[j + 1] = temp
    }
  }
}

希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

function shellSort (arr) {
  // 遍历步长
  for (let d = arr.length / 2 >>> 0; d > 0; d = d / 2 >>> 0) {
    // 遍历所有元素
    for (let i = d; i < arr.length; i++) {
      // 遍历本组所有的元素
      for (let j = i - d; j > 0; j -= d) {
        if (arr[j] > arr[j + d]) {
          [arr[j], arr[j + d]] = [arr[j + d], arr[j]]
        }
      }
    }
  }
}

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

function selecStort (arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i
    for (let j = i + 1; j < arr.length; j++) {
      minIndex = arr[j] < arr[minIndex] ? j : minIndex
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }
}

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

function mergeSort (arr, low = 0, high = arr.length - 1) {
  function merge (arr, low, middle, high) {
    // 用于储存归并后的数组
    let temp = []
    // 记录第一个数组中需要遍历的下标
    let l = low
    // 记录第二个数组中需要遍历的下标
    let m = middle + 1
    // 遍历两个数组取出最小的值，放入临时数组中
    while (l <= middle && m <= high) {
      if (arr[l] <= arr[m]) {
        temp.push(arr[l++])
      } else {
        temp.push(arr[m++])
      }
    }
    // 处理多余的数据
    while (l <= middle) {
      temp.push(arr[l++])
    }
    while (m <= high) {
      temp.push(arr[m++])
    }
    // 把临时数组的数据重新存入原数组中
    for (let i = 0; i < temp.length; i++) {
      arr[i + low] = temp[i]
    }
  }

  if(low < high) {
    let middle = (low + high) / 2 >>> 0 
    // 左子数组有序
    mergeSort(arr, low, middle)
    // 右子数组有序
    mergeSort(arr, middle + 1, high)
    merge(arr, low, middle, high)
  }
}

基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

function radixSort (arr) {
  let max = Number.MIN_SAFE_INTEGER
  // 缓存数组最大的数
  for (let i = 0; i <arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]
    }
  }
  // 计算最大的数是几位数
  let maxLength = (max + '').length
  // 创建数组临时存储数据
  let temp = new Array(10).fill(0)
  // 记录数量
  let counts = new Array(10)
  // 根据最大的数是几位数决定比较次数
  for (let i = 0, n = 1; i < maxLength; i++, n *= 10) {
    // 初始化二维数组
    temp = temp.map(() => {
      return []
    })
    counts.fill(0)
    for (let j = 0; j < arr.length; j++) {
      // 计算余数
      let y = (arr[j] / n >>> 0) % 10
      temp[y].push(arr[j])
      counts[y]++
    }
    let index = 0
    // 取出数据
    for (let j = 0; j < counts.length; j++) {
      if (counts[j] === 0) continue
      for (let k = 0; k < counts[j]; k++) {
        arr[index++] = temp[j][k]
      }
    }
  }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

面向对象编程

数据结构

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

面向对象编程

数据结构