个人感觉 【数据结构与算法图解】这本书讲的比较简单，有计算机基础的不推荐看

尽量减少重复劳动力

系统学习推荐小伙伴直接去 awesome-coding-js (opens new window)

这里是我个人学习的的一些小结

【数据结构与算法图解】 结合 awesome-coding-js 总结的

个人感觉 【数据结构与算法图解】这本书讲的比较简单，有计算机基础的不推荐看

1、一些概念

• 时间复杂度 理论：操作的速度，并不按时间计算，而是按步数 计算
• 读取：一步，查找：最多N步，插入：最多N+1（N次移动，1次插入），删除：最多N

2、查找

• 线性查找： 一个个查，比对
• 二分查找： 每次有序数组长度乘以 2，二分查找所需的最多步数只会加 1。

3、大 O 记法

一般指： 最坏的情况

• O(1) 不管需要多少步，步数不变就是O(1)
• O(N) 根据数据量变化而变化
• O(log N) 对数时间，比如二分查找，数据量翻倍时，步数+1

JavaScript简单记（不准）：根据for循环的数量来记，2个for就是O(n2)

4、冒泡排序

概念

循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。

这样一次循环之后最后一个数就是本数组最大的数。

下一次循环继续上面的操作，不循环已经排序好的数。

优化：当一次循环没有发生冒泡，说明已经排序完成，停止循环

解法

function bubbleSort(array) {
      for (let j = 0; j < array.length; j++) {
        let complete = true;
        for (let i = 0; i < array.length - 1 - j; i++) {
          // 比较相邻数
          if (array[i] > array[i + 1]) {
            [array[i], array[i + 1]] = [array[i + 1], array[i]];
            complete = false;
          }
        }
        // 没有冒泡结束循环
        if (complete) {
          break;
        }
      }
      return array;
    }

复杂度

时间复杂度：O(n2)

空间复杂度:O(1)

5、选择排序

每次循环选取一个最小的数字放到前面的有序序列中。

解法

 function selectionSort(array) {
      for (let i = 0; i < array.length - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < array.length; j++) {
          if (array[j] < array[minIndex]) {
            minIndex = j;
          }
        }
        [array[minIndex], array[i]] = [array[i], array[minIndex]];
      }
    }

复杂度

时间复杂度：O(n2)

空间复杂度:O(1)

大O记法忽略常数

选择排序的步数大概只有冒泡排序的一半，即选择排序比冒泡排序 快一倍。

但是严格来说选择排序应为 O(N2 / 2)，最终得写成 O(N2 )。

类似地，O(2N)要写成 O(N)； O(N / 2)也写成 O(N)；就算是比 O(N)慢 100 倍的 O(100N)，也要写成 O(N)。

6、插入排序

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。

插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

function insertSort(array) {
      for (let i = 1; i < array.length; i++) {
        let target = i;
        for (let j = i - 1; j >= 0; j--) {
          if (array[target] < array[j]) {
            [array[target], array[j]] = [array[j], array[target]]
            target = j;
          } else {
            break;
          }
        }
      }
      return array;
    }

复杂度

时间复杂度：O(n2)

空间复杂度:O(1)

7、快速排序

快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

先从右往左找一个小于 基准值 的数，再从左往右找一个大于 基准值 的数，然后交换他们。

这个图解很清楚：算法 3：最常用的排序——快速排序 (opens new window)

实现步骤：

• 选择一个基准元素target（一般选择第一个数）
• 将比target小的元素移动到数组左边，比target大的元素移动到数组右边
• 分别对target左侧和右侧的元素进行快速排序

简单版本

function quickSort(array) {
      if (array.length < 2) {
        return array;
      }
      const target = array[0];
      const left = [];
      const right = [];
      for (let i = 1; i < array.length; i++) {
        if (array[i] < target) {
          left.push(array[i]);
        } else {
          right.push(array[i]);
        }
      }
      return quickSort(left).concat([target], quickSort(right));
    }

8、数据结构

• 链表（带有存储下一个结点地址的）插入和删除效率比数组高很多

9、空间复杂度

空间复杂度：当所处理的数据有 N 个元素时，该算法还需额外消耗多少元素大小的内存空间

O(1)： 记住，时间 复杂度的O(1)意味着一个算法无论处理多少数据，其速度恒定。相似地，空间复杂度的 O(1)则 意味着一个算法无论处理多少数据，其消耗的内存恒定。