前言

• https://github.com/trekhleb/javascript-algorithms/blob/master/README.zh-CN.md JavaScript 算法与数据结构

工具类

// 比较器

export default class Comparator {
  /**
   * Constructor.
   * @param {function(a: *, b: *)} [compareFunction] - It may be custom compare function that, let's
   * say may compare custom objects together.
   */
  constructor(compareFunction) {
    this.compare = compareFunction || Comparator.defaultCompareFunction;
  }

  /**
   * Default comparison function. It just assumes that "a" and "b" are strings or numbers.
   * @param {(string|number)} a
   * @param {(string|number)} b
   * @returns {number}
   */
  static defaultCompareFunction(a, b) {
    if (a === b) {
      return 0;
    }

    return a < b ? -1 : 1;
  }

  /**
   * Checks if two variables are equal.
   * @param {*} a
   * @param {*} b
   * @return {boolean}
   */
  equal(a, b) {
    return this.compare(a, b) === 0;
  }

  /**
   * Checks if variable "a" is less than "b".
   * @param {*} a
   * @param {*} b
   * @return {boolean}
   */
  lessThan(a, b) {
    return this.compare(a, b) < 0;
  }

  /**
   * Checks if variable "a" is greater than "b".
   * @param {*} a
   * @param {*} b
   * @return {boolean}
   */
  greaterThan(a, b) {
    return this.compare(a, b) > 0;
  }

  /**
   * Checks if variable "a" is less than or equal to "b".
   * @param {*} a
   * @param {*} b
   * @return {boolean}
   */
  lessThanOrEqual(a, b) {
    return this.lessThan(a, b) || this.equal(a, b);
  }

  /**
   * Checks if variable "a" is greater than or equal to "b".
   * @param {*} a
   * @param {*} b
   * @return {boolean}
   */
  greaterThanOrEqual(a, b) {
    return this.greaterThan(a, b) || this.equal(a, b);
  }

  /**
   * Reverses the comparison order.
   */
  reverse() {
    const compareOriginal = this.compare;
    this.compare = (a, b) => compareOriginal(b, a);
  }
}

相关信息

大O符号

大O符号中指定的算法的增长顺序。

以下是一些最常用的 大O标记法 列表以及它们与不同大小输入数据的性能比较。

大O标记法	计算10个元素	计算100个元素	计算1000个元素
O(1)	1	1	1
O(log N)	3	6	9
O(N)	10	100	1000
O(N log N)	30	600	9000
O(N^2)	100	10000	1000000
O(2^N)	1024	1.26e+29	1.07e+301
O(N!)	3628800	9.3e+157	4.02e+2567

数据结构操作的复杂性

数据结构	连接	查找	插入	删除	备注
数组	1	n	n	n
栈	n	n	1	1
队列	n	n	1	1
链表	n	n	1	1
哈希表	-	n	n	n	在完全哈希函数情况下，复杂度是 O(1）
二分查找树	n	n	n	n	在平衡树情况下，复杂度是 O(log(n))
B 树	log(n)	log(n)	log(n)	log(n)
红黑树	log(n)	log(n)	log(n)	log(n)
AVL 树	log(n)	log(n)	log(n)	log(n)
布隆过滤器	-	1	1	-	存在一定概率的判断错误（误判成存在）

数组排序算法的复杂性

名称	最优	平均	最坏	内存	稳定	备注
冒泡排序	n	n^2	n^2	1	Yes
插入排序	n	n^2	n^2	1	Yes
选择排序	n^2	n^2	n^2	1	No
堆排序	n log(n)	n log(n)	n log(n)	1	No
归并排序	n log(n)	n log(n)	n log(n)	n	Yes
快速排序	n log(n)	n log(n)	n^2	log(n)	No	在 in-place 版本下，内存复杂度通常是 O(log(n))
希尔排序	n log(n)	取决于差距序列	n (log(n))^2	1	No
计数排序	n + r	n + r	n + r	n + r	Yes	r - 数组里最大的数
基数排序	n * k	n * k	n * k	n + k	Yes	k - 最长 key 的升序