算法与数据结构

使用JavaScript来实现从常用的算法和数据结构

排序算法：

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序

数组：

• 数组

栈：

• 栈

队列:

• 队列
• 优先队列

链表：

• 单向链表
• 双向链表
• 双向循环链表

堆：

• 最大堆
• 最大索引堆
• 最小堆

树：

• 二叉树I
• 二叉树II

并查集:

一种树形结构，下面代码逐步优化.

• 并查集I
• 并查集II
• 并查集III
• 并查集IV
• 并查集V

线段树:

一种树形结构，用于获取区间内数值操作的结果

• 线段树I
• 线段树II

字典树:

一种树型结构，用于字符串匹配

• 字典树

AVL树：

一种平衡二叉树

• AVL树I
• AVL树II

红黑树

• 红黑树

图论：

• 图的实现
• 稠密图
• 稀疏图
• 联通分量
• 寻路算法
• 最短路径算法

最小生成树：

• 有权图边的定义
• 稠密图
• 稀疏图
• Prim算法
• Prim算法II
• Kruskal算法

经典算法：

• 二分查找
• 二分查找优化

字符串相关算法：

• Levenshtein Distance 莱文斯坦距离

补充

JavaScript测试算法性能

JavaScript用于测试算法性能的常用方法总结:
方法一：

console.time("time");
// 测试的算法
console.timeEnd("time");

方法二：

var start = Date.now();
// 测试的算法
var end = Date.now();
console.log(end-start);

JavaScript迭代器的写法

标准迭代器写法：每一次调用next方法，都会返回数据结构的当前成员的信息。具体来说，就是返回一个包含value和done两个属性的对象。其中，value属性是当前成员的值，done属性是一个布尔值，表示遍历是否结束。

var it = makeIterator(['a', 'b']);
it.next() // { value: "a", done: false }
it.next() // { value: "b", done: false }
it.next() // { value: undefined, done: true }

function makeIterator(array) {
  var nextIndex = 0;
  return {
    next: function() {
      return nextIndex < array.length ?
        {value: array[nextIndex++], done: false} :
        {value: undefined, done: true};
    }
  };
}

ES6的写法：默认的 Iterator 接口部署在数据结构的Symbol.iterator属性，或者说，一个数据结构只要具有Symbol.iterator属性，就可以认为是“可遍历的”（iterable）。

const obj = {
  [Symbol.iterator] : function () {
    return {
      next: function () {
        return {
          value: 1,
          done: true
        };
      }
    };
  }
};

使用generator：

let generator = function* () {
  yield 1;
  yield* [2,3,4];
  yield 5;
};

var iterator = generator();

iterator.next() // { value: 1, done: false }
iterator.next() // { value: 2, done: false }
iterator.next() // { value: 3, done: false }
iterator.next() // { value: 4, done: false }
iterator.next() // { value: 5, done: false }
iterator.next() // { value: undefined, done: true }