一、算法复杂度

O(log n) 对数时间，这样的算法包括二分法；
O(n) 线性时间，包括简单查找；
O(n*log n) , 包括快排；
O(n^2), 选择排序;
O(n!) 非常慢的算法；

理解：
谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加
算法的运行时间用大O表示法表示
O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。
大O表示法省略诸如1/2这样的常数

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。
递归条件：指的是函数调用自己
基线条件：指的是函数不再调用自己，从而避免形成无限循环
常量：算法所需的固定时间量
快速查找的常量比合并查找小，因此如果它们的运行时间都为O(n log n)，快速查找的速度将更快。

快排算法不稳定：
最快时：O(n) O(log n) = O(n log n)，层数为O(log n)（也是调用栈的高度，用中间元素做基准时），每层需要的时间为O(n)
最慢时：O(n) O(n) = O(n^2 )， 层数为O(n)（用第一个元素做基准，排列有序数组时）， 每层需要的时间为O(n)。

  1. // 快排
  2. function quickSort (arr) {
  3.     if(arr.length<= 1) {
  4.         return arr
  5.     }
  6.     const item = arr[0];
  7.     const left = [], right = [];
  8.     for(var i= 1; i< arr.length; i++) {
  9.         if(arr[i] < item){
  10.             left.push(arr[i])
  11.         }else{
  12.             right.push(arr[i])
  13.         }
  14.     }
  15.     return quickSort(left).concat(item).concat(quickSort(right))
  16. }
  18. // var res = quickSort([5, 4, 9, 13, 16, 7, 49]);
  19. // console.log('res', res);
  21. // 原地快排
  22. function quickSort1 (arr) {
  23.     if(arr.length<= 1) {
  24.         return arr
  25.     }
  27.     let flag = arr[0];
  28.     let i = 1;
  29.     let j = arr.length-1;
  31.     while(i<j) {
  32.         //顺序很重要，要先从右往左找
  33.         while(arr[j] >= flag && i<j) {
  34.             j--;
  35.         }
  36.         while(arr[i] <= flag && i<j) {
  37.             i++;
  38.         }
  39.         const temp = arr[i];
  40.         arr[i] = arr[j];
  41.         arr[j]=temp;
  42.     }
  43.     arr[0]=arr[j];
  44.     arr[j]=flag;
  45.     return quickSort(arr.slice(0,i)).concat([flag]).concat(quickSort(arr.slice(i+1)));
  46. }
  48. var res2 = quickSort1([5, 4, 9, 13, 16, 7, 49]);
  49. console.log('res2', res2);

数组擅长随机访问
链表的删除和插入复杂度低

散列表
散列函数：将输入映射到数字，

hash表
优点：查找、新增、删除元素容易，js对象就是用hash表实现的。
缺点：存储空间大， 碰撞后需扩容，雪崩效应（之前的hash全部失效）

队列是一种先进先出的数据结构
栈是一种后进先出的数据结构

解决最短路径问题的算法被称为广度优先搜索，用于在非加权图中查找最短路径
总权重最小的路径的算法叫做狄克斯特拉算法 ，狄克斯特拉算法只适用于有向无环图，用于在加权图中查找最短路径，仅当权重为正时狄克斯特拉算法才管用

推荐书籍：
啊哈算法
算法图解
算法 第四版