《数据结构与算法之美》

开篇词 | 从今天起，跨过“数据结构与算法”这个坎

那些所谓的新技术，核心和本质的东西其实就是当初学的那些知识。

基础知识就像是一座大楼的地基，它决定了我们的技术高度。而想要快速做出点事情，前提条件一定是基础能力过硬，“内功”要到位。

人生路上，我们会遇到很多的坎。跨过去，你就可以成长，跨不过去就是困难和停滞。而在后面很长的一段时间里，你都需要为这个困难买单。对于我们技术人来说，更是这样。既然数据结构和算法这个坎，我们总归是要跨过去的，为什么不是现在呢？

01 | 为什么要学习数据结构和算法？

作为业务开发，我们会用到各种框架、中间件和底层系统，比如Spring、RPC框架、消息中间件、Redis等等。在这些基础框架中，一般都柔和了很多基础数据结构和算法的设计思想。

掌握数据结构和算法，不管对于阅读框架源码，还是理解其背后的设计思想，都是非常有用的。

掌握了数据结构与算法，你看待问题的深度，解决问题的角度就会完全不一样。

02 | 如何抓住重点，系统高效地学习数据结构与算法？

从广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

数据结构是为算法服务的，算法要作用在特定的数据结构之上。因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。

数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构就是没用的。

数据结构与算法的知识点：

查看图片

10个数据结构： 数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie数；
10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

03 ｜ 复杂度分析（上）：如何分析统计算法的执行效率和资源消耗？

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行的更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。

事后统计法的局限性：

• 测试结果非常依赖测试环境
• 测试结果受数据规模的影响很大

大O复杂度表示法

估算下这段代码的执行时间：

function foo(n) {
  let sum = 0;
  let i = 1;
  for (; i <= n; i++) {
    sum += i;
  }
  // return sum
}

我们可以假设每段代码的执行时间都是一样的，为unit_time。在这个假设的基础之上，这段代码的总执行时间是多少？

• 第2、3行分别需要1个unit_time时间，公式为：2 * unit_time。
• 第4、5行都运行了n遍，所以第四行是n * unit_time，第五行也是n * unit_time。简化下公式为：（n + n) * unit_time，再简化下公式为：2n * unit_time。
• 所有代码的执行时间T(n)与每行代码的执行次数成正比
• 最后总的执行时间T(n)为：2n * unit_time + 2 * unit_time，简化下公式为：(2n + 2) * unit_time = T(n)

再来看下这段代码的执行时间：

function bar(n) {
  let sum = 0;
  let i = 0;
  let j = 0;
  for (; i <= n; i++) {
    j = 1;
    for (; j <= n; j++) {
      sum += i * j
      // sum = sum + i * j
    }
  }
}

我们依旧假设每个语句的执行时间是unit_time。那么这段代码的总执行时间T(n)是？

• 第2、3、4行分别需要1个unit_time时间。公式为：3 * unti_time
• 第5、6行分别需要n个unit_time时间。公式为：2n * unit_time
• 第7、8行分别需要n个unit_time时间，但是需要执行n遍。公式为：(2n * unit_time) * n
• 最后的执行是间：T(n) = 3 * unit_time + 2n * unit_time + 2n * unit_time * n
• 公式简化为：(2n + 3) * unit_time + (2n * n) * unit_time
• 公式再简化为：(2n + 3 + 2n²) * unit_time

尽管我们不知道unit_time的具体值，但是通过这两段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，所有代码的执行时间T(n)与每行代码的执行次数成正比。

我么可以把这个规律总结为一个公式：T(n) = O(f(n)) 这段公式的大概意思为：

• T(n)表示一段代码执行的总时间
• n表示数据规模的大小
• f(n)每行代码执行的次数总和，因为这是一个公式，所以用f(n)来表示。
• O表示代码的执行时间T(n)与f(n)表达式成正比。

所以第一个例子中的Tn = O(2n + 2)。第二个例子中的T(n) = O(2n + 3 + 2n²)。

以上就是大O时间复杂度表示法。

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随着数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n2)。

时间复杂度分析

只关注循环次数最多的一段代码
以下代码为例：

function foo(n) {
  let sum = 0;
  let i = 1;
  for (; i <= n; i++) {
    sum += i;
  }
}

• 第2、3行代码都是常量级的执行时间，与n的大小无关，所以对于复杂度并没有影响。
• 循环次数最多的是4、5行代码，这两行代码被执行了n次，所以总的时间复杂度就是O(n)

加法法则：总复杂度等于量级最大的那段代码的复杂度。
这段代码，试着分析一下时间复杂度

function cal(n) {
  let sum_1 = 0;
  let p = 1;
  for (; p < 100; ++p) {
    sum_1 = sum_1 + p;
  }

  let sum_2 = 0;
  let q = 1;
  for (; q < n; ++q) {
    sum_2 = sum_2 + q;
  }

  let sum_3 = 0;
  let i = 1;
  let j = 1;
  for (; i <= n; ++i) {
    j = 1; 
    for (; j <= n; ++j) {
      sum_3 = sum_3 +  i * j;
    }
  }

  return sum_1 + sum_2 + sum_3;
}

这段代码分为3部分，分别是sum_1、sum_2、sum_3。我们分析每一部分的时间复杂度，然后把它们放到一块，再取一个量级最大的作为整段代码的复杂度。

常量的执行时间虽然会对代码的执行时间有很大的影响，但是回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，我们都可忽略掉。因为它本身对趋势的增长并没有影响。

• 第一段代码是循环了100次，跟n无关，它是一个常量。最终表示为200 * unit_time
• 第二段代码是循环了n次，它是一个变量。所以表示为：2n * unit_time，用大O表示法则为O(n)
• 第三段代码是外层循环了n次，内层循环了n次的n遍。最终表示为：2n² * unit_time，用大O表示法则为O(n)
• 综合这三段代码的时间复杂度，我们取其中最大的量级。所以整段代码的时间复杂度为：O(n²)

也就是说，总的时间复杂度等于量级最大的那段代码的时间复杂度。那么将这个规律抽象成公式就是：

如果T1(n) = O(f1(n))，T2(n) = O(f2(n));那么T(n) = T1(n) + T2(n) = max(O(f1(n)), O(f2(n))) = O(max(f1(n), f2(n)));

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
乘法法则公式：

• 如果T1(n) = O(f(n)), T2(n) = O(g(n))；
• 那么T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))

假设：T1(n) = O(n)，T2(n) = O(n²)，那么 T1(n) * T2(n) = O(n²)。落实到具体代码上，可以把乘法法则看成是嵌套循环。如下列子：

function cal(n) {
  let ret = 0;
  let i = 1;
  for (; i <= n; i++) {
    ret = ret * f(i);
  }
}

function f(n) {
  let sum = 0;
  let i = 1;
  for (; i<= n; i++) {
    sum += i;
  }
  return sum;
}

• 假设f只是一个普通的操作，那么第4 ~ 6行的时间复杂度就是T1(n) = O(n)。
• 但f不是一个普通操作，f函数里面有一个for循环，所以它的时间复杂度是T2(n) = O(n)
• 那么整个cal函数的时间复杂度就是T1(n) * T2(n) = O(n*n) = O(n²)。

几种常见时间复杂度实例分析

复杂度量级可以粗略地分为两类

• 多项式量级
• 非多项式量级
• 非多多项式量级只有两个：O(2n) 和 O(n!)。

我们把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。
当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

1. O(1)
O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。例如一下代码的时间复杂度就是O(1)。

const i = 8;
const j = 6;
const sum = i + j;

只要代码的执行时间不随着n的增大而增长，这样代码的时间复杂度我们都记作O(1)。或者说：一般情况下，只要算法中不存在循环语句、递归语句、即使有成千上万行代码，其时间复杂度也是O(1)。

O(logn)、O(nlog)n
如下代码：

let i = 1;
while (i <= n) {
  i *= 2; 
}

• 从代码中可以看出，变量i的值是从1开始，每循环一次乘以2
• 当大于n时循环结束
• 实际上，变量i的取值就是一个等比数列，大致可以表示为2^x = n
• 通过2^x = n求解x，那么可以表示为 x=log2n
• 所以这段代码的时间复杂度就是O(log2n)

实际上，不管是以2为底，以3为底，还是以10为底我们都可以把所有对数阶的时间复杂度都记为O(logn)。

为什么呢？
我们知道，对数之间是可以互相转换的，log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

如果你理解了我前面讲的 O(logn)，那 O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则吗？如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

O(m+n)、O(m*n)
代码复杂度由两个数据规模决定，如下代码：

function cal(m, n) {
  let sum_1 = 0;
  let i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  let sum_2 = 0;
  let j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。
针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。

空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

以代码为例：

function print(n) {
  let i = 0;
  let a = new Array(n);
  for (;i<n;i++) {
    a[i] = i * i;
  }
}

• 从代码中看，第二行申请了一个存储变量i的空间。但它是常量阶的，跟数据规模n没有关系，可以忽略
• 第三行申请了一个大小为n的数组空间，除此之外，剩下的代码都没有占用更多的空间。
• 整段代码的空间复杂度就是O(n)

我们常见的空间复杂度就是O(1)、O(n)、O(n²)，像O(logn)、O(nlogn)这样的对数阶复杂度平时都用不到。

04 | 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度

4个复杂度分析概念：

• 最好情况时间复杂度（best case time complexity）
• 最坏情况时间复杂度（worst case time complexity）
• 平均情况时间复杂度（average case time complexity）
• 均摊时间复杂度（amortized time complexity）

最好、最坏情况时间复杂度

试着分析下这段代码的复杂度

// n表示数组array的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) pos = i;
  }
  return pos;
}

• 这段代码的负载读是O(n)，其中，n代表数组长度。
  

我们来优化下这段代码

// n表示数组array的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

那么优化完之后的代码时间复杂度还是O(n)吗？用O(n)无法解决。

• 因为变量x可能出现在数组的任意位置。
• 如果数组中的第一个元素正好是x变量，时间复杂度就是O(1)。
• 如果数组中不存在x变量，那么就需要将数组遍历一遍，时间复杂度就是O(n)
• 所以，在不同的情况下，这段代码的时间复杂度是不一样的。

为了代码表示在不同情况下的不同时间复杂度，这里引入三个概念：

最好时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。

最坏时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度。

平均情况时间复杂度

平均情况时间复杂度

我们都知道，最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的复杂度，我们需要引入另一个概念：平均情况时间复杂度，后面我简称为平均时间复杂度。

平均时间复杂度又该怎么分析呢？我还是借助刚才查找变量 x 的例子来给你解释。

要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：

我们知道，时间复杂度的大 O 标记法中，可以省略掉系数、低阶、常量，所以，咱们把刚刚这个公式简化之后，得到的平均时间复杂度就是 O(n)。

这个结论虽然是正确的，但是计算过程稍微有点儿问题。究竟是什么问题呢？我们刚讲的这 n+1 种情况，出现的概率并不是一样的。我带你具体分析一下。（这里要稍微用到一点儿概率论的知识，不过非常简单，你不用担心。）

我们知道，要查找的变量 x，要么在数组里，要么就不在数组里。这两种情况对应的概率统计起来很麻烦，为了方便你理解，我们假设在数组中与不在数组中的概率都为 1/2。另外，要查找的数据出现在 0～n-1 这 n 个位置的概率也是一样的，为 1/n。所以，根据概率乘法法则，要查找的数据出现在 0～n-1 中任意位置的概率就是 1/(2n)。

因此，前面的推导过程中存在的最大问题就是，没有将各种情况发生的概率考虑进去。如果我们把每种情况发生的概率也考虑进去，那平均时间复杂度的计算过程就变成了这样：
这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

引入概率之后，前面那段代码的加权平均值为 (3n+1)/4。用大 O 表示法来表示，去掉系数和常量，这段代码的加权平均时间复杂度仍然是 O(n)。

你可能会说，平均时间复杂度分析好复杂啊，还要涉及概率论的知识。实际上，在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。像我们上一节课举的那些例子那样，很多时候，我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。

均摊时间复杂度

每一次O(n)的插入操作，都会跟着n-1次O(1)的插入操作，所以把耗时多的那次操作均摊到接下来 n - 1次耗时的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1)。

均摊时间复杂度就是一种特殊的平均时间复杂度。

05 | 数组：为什么很多编程语言中数组都是从0开始编号？

如何实现随机访问

数组的定义：

• 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

线性表（Linear List）：
线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。除了数组，链表、队列、栈等也是线性表结构。

查看图片

非线性表：
在非线性表中，数据之间并不是简单的前后关系。比如，二叉树、堆、图等。

查看图片

数组的线性表特性加上连续的内存空间和相同类型的数据确保了数组的“随机访问特性”。弊端是让数组的另一些操作变得非常低效，比如数组中的删除、插入一个数据，为保证连续性，就需要做大量的数据搬移工作。

计算机随机访问数组中的某个元素时，会通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_adddress = base_address + i + data_type_size

其中data_type_size表示数组中每个元素的大小

数组适合查找，但时间复杂度并不为O(1)。即便是排序号的数组，使用二分查找，时间复杂度也是O(logn)。数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。

低效的“插入”和“删除”

插入操作

• 如果只插入到数组末尾，那么时间复杂度是O(1)
• 如果插入到数组开头，那么时间复杂度是O(n)
• 在每个位置上插入的概率是一样的，那么平均情况时间复杂度为(1 + 2 + ...n) / n = O(n)
• 如果数组中的数据是无序的，只是一个存储数据的集合。在这种情况下，为了避免大规模的迁移数据，通常会在插入的位置把改位置的元素移动到最后一位，然后再插入。这时候时间复杂度为O(1)。

删除操作

• 如果只删除数组末尾的数据，那么时间复杂度是O(1)
• 如果删除数组开头的疏忽，那么时间复杂度为O(n)，平均情况时间复杂度也为O(n)

如果在不追求数组中数据连续性的情况下，可以将多次的删除操作标记出来，等到数组没有更多的存储空间时，再触发一次真正的删除操作，这时就大大减少了删除操作导致的数据搬移。 例如，数组中存储了8个元素：a、b、c、d、e、f、g、h。现在依次删除a、b、c三个元素。 为避免多次搬移数据，先记录已删除的数据。当数组没有更多存储空间时，再触发一次真正的删除操作。

警惕数组的访问越界问题

先看一段C语言代码：

int main(int argc, char* argv[]){
  int i = 0;
  int arr[3] = {0};
  for(; i<=3; i++){
    arr[i] = 0;
    printf("hello world\n");
  }
  return 0;
}

这段代码会无限循环打印Hello world。

因为数组大小为3，a[0]、a[1]、a[2]。for循环的结束条件写成了i<= 3，所以，当i = 3 时，数组a[3]访问越界。正确的方式是for循环结束条件写成 i < 3。

在C语言中，只要不是访问受限的内存，所有的内存空间都可以自由访问。根据前面讲的数组寻址公式，a[3]会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量i的内存地址。那么a[3] = 0，其实就是变量i = 0，所以会导致代码无限循环。

并非所有的编程语言都像C这样，像JavaScript本身并不存在数组访问越界的问题，因为JavaScript中的数组通常而言是不会定义它的大小，而是动态扩容的。

二维数组内存寻址

对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：

address = base_address + ( i * n + j) * type_size

06 | 链表（上）：如何实现LRU缓存淘汰算法？

常见的三种缓存策略：

• 先进先出策略FIFO（Fist In，Fist Out）
• 最少使用策略LFU（Least Frequently Used）
• 最近最少使用策略（Least Recently Used）

五花八门的链表结构

底层的存储结构
数组需要一块连续的内存空间来存储，对内存的要求比较高。如果申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可以用空间大于100MB，仍然会申请失败。

链表并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。所以，如果我们申请的是100MB大小的链表，根本不会有问题。

常见的三种链表结构

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

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块成为链表的结点。为了将所有节点串联起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。我们把这个记录下个结点的指针叫做后继指针。

我们习惯把第一个结点叫做头结点，把最后一个结点叫做尾结点。头结点用来记录链表的基地址。有了它，我们就可以遍历整条链表。而尾结点指向一个空地址NULL，表示这是链表上的最后一个结点。

针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是O(1)。

如果想要随机访问第K个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

你可以把链表想象成一个队伍，队伍中的每个人都只知道自己后面的人是谁，所以当我们希望知道排在第 k 位的人是谁的时候，我们就需要从第一个人开始，一个一个地往下数。所以，链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。

循环链表是一种特殊的单链表。它跟单链表唯一的区别就在尾结点。循环链表的尾结点指针是指向链表的头结点。

循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题 (opens new window)。

双向链表
单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

删除操作
在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：

• 删除结点中“值等于某个给定值”的结点；
• 删除给定指针指向的结点。

尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。

所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了！

对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

空间换时间的设计思想

当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。

对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。

双向循环列表

链表 VS 数组性能大比拼

数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别，它们插入、删除、随机访问操作的时间复杂度正好相反。

如何基于链表实现LRU缓存淘汰算法？

我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。

2. 如果此数据没有在缓存链表中，又可以分为两种情况：

• 如果此时缓存未满，则将此结点直接插入到链表的头部；
• 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

因为不管缓存有没有满，我们都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度为 O(n)。

实际上，我们可以继续优化这个实现思路，比如引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。

07 | 链表（下）：如何轻松写出正确的链表代码？

技巧一：理解指针或引用的含义

有些语言有“指针”的概念，比如C语言；有些语言没有指针，取而代之的是“引用”，比如Java、Python。不管是“指针”还是“引用”，实际上，它们的意思都是一样的，都是存储所指对象的内存地址。

指针的概念

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

理解链表

p->next=q。这个代码是说，p节点中的next指针存储了q结点的内存地址。
p->next=p->next->next。这行代码表示，p结点的next指针存储了p节点的下下一个结点的内存地址。

技巧二：警惕指针丢失和内存泄露

如图所示，我们希望在结点 a 和相邻的结点 b 之间插入结点 x，假设当前指针 p 指向结点 a。如果我们将代码实现变成下面这个样子，就会发生指针丢失和内存泄露。

p->next = x;  // 将p的next指针指向x结点；
x->next = p->next;  // 将x的结点的next指针指向b结点；

p-next指针在完成第一步操作之后，已经不再指向结点b，而是指向结点x。第2行代码相当于将x赋值给x-next，自己指向自己。因此，整个链表也就段按成了两半，从结点b往后的所有结点都无法访问到了。

对于有些语言来说，比如 C 语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。所以，我们插入结点时，一定要注意操作的顺序，要先将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。

同理，删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。

技巧三：利用哨兵简化实现难度

如果向一个空链表中插入第一个结点，需要这样处理

if (head == null) {
  head = new_node;
}

如果删除链表中最后一个结点，需要写成这样子

if (head->next == null) {
   head = null;
}

我们可以看出，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且也容易因为考虑不全而出错。

如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。 利用哨兵简化编程难度的技巧，在很多代码实现中都有用到，比如插入排序，归并排序，动态规划等。

哨兵机制的代码举例：
代码一：

// 在数组a中，查找key，返回key所在的位置
// 其中，n表示数组a的长度
int find(char* a, int n, char key) {
  // 边界条件处理，如果a为空，或者n<=0，说明数组中没有数据，就不用while循环比较了
  if(a == null || n <= 0) {
    return -1;
  }
  
  int i = 0;
  // 这里有两个比较操作：i<n和a[i]==key.
  while (i < n) {
    if (a[i] == key) {
      return i;
    }
    ++i;
  }
  
  return -1;
}

代码二：

// 在数组a中，查找key，返回key所在的位置
// 其中，n表示数组a的长度
// 我举2个例子，你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 7
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 6
int find(char* a, int n, char key) {
  if(a == null || n <= 0) {
    return -1;
  }
  
  // 这里因为要将a[n-1]的值替换成key，所以要特殊处理这个值
  if (a[n-1] == key) {
    return n-1;
  }
  
  // 把a[n-1]的值临时保存在变量tmp中，以便之后恢复。tmp=6。
  // 之所以这样做的目的是：希望find()代码不要改变a数组中的内容
  char tmp = a[n-1];
  // 把key的值放到a[n-1]中，此时a = {4, 2, 3, 5, 9, 7}
  a[n-1] = key;
  
  int i = 0;
  // while 循环比起代码一，少了i<n这个比较操作
  while (a[i] != key) {
    ++i;
  }
  
  // 恢复a[n-1]原来的值,此时a= {4, 2, 3, 5, 9, 6}
  a[n-1] = tmp;
  
  if (i == n-1) {
    // 如果i == n-1说明，在0...n-2之间都没有key，所以返回-1
    return -1;
  } else {
    // 否则，返回i，就是等于key值的元素的下标
    return i;
  }
}

对比两段代码，在字符串 a 很长的时候，比如几万、几十万，你觉得哪段代码运行得更快点呢？答案是代码二，因为两段代码中执行次数最多就是 while 循环那一部分。第二段代码中，我们通过一个哨兵 a[n-1] = key，成功省掉了一个比较语句i<n，不要小看这一条语句，当累积执行万次、几十万次时，累积的时间就很明显了。

当然，这只是为了举例说明哨兵的作用，你写代码的时候千万不要写第二段那样的代码，因为可读性太差了。大部分情况下，我们并不需要如此追求极致的性能。

技巧四：重点留意边界条件处理

检查链表代码是否正确的边界条件有这样几个：

• 如果链表为空时，代码是否能正常工作？
• 如果链表只包含一个结点时，代码是否能正常工作？
• 如果链表只包含两个结点时，代码是否能正常工作？
• 代码逻辑在处理头结点和尾结点的时候偶，是否能正常工作？

边界条件不止我列举的那些。针对不同的场景，可能还有特定的边界条件，这个需要你自己去思考，不过套路都是一样的。

实际上，不光光是写链表代码，你在写任何代码时，也千万不要只是实现业务正常情况下的功能就好了，一定要多想想，你的代码在运行的时候，可能会遇到哪些边界情况或者异常情况。遇到了应该如何应对，这样写出来的代码才够健壮！

技巧五：举例画图，辅助思考

举例法和画图法

比如往单链表中插入一个数据这样一个操作，我一般都是把各种情况都举一个例子，画出插入前和插入后的链表变化，如图所示：

看图写代码，是不是就简单多啦？而且，当我们写完代码之后，也可以举几个例子，画在纸上，照着代码走一遍，很容易就能发现代码中的 Bug。

技巧六：多写多练，没有捷径

5个常见的链表操作

• 单链表反转
• 链表中环的检测
• 两个有序的链表合并
• 删除链表倒数第n个结点
• 求链表的中间结点

把这几个操作都能写熟练，不熟就多写几遍

08 | 栈：如何实现浏览器的前进和后退功能？

如何理解“栈”？

栈概念

后进者先出，先进者后出，这就是典型的“栈”结构
从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

事实上，从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。

如何实现一个“栈”？

实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

基于数组的顺序栈

// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           //栈的大小

  // 初始化数组，申请一个大小为n的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了，直接返回false，入栈失败。
    if (count == n) return false;
    // 将item放到下标为count的位置，并且count加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素，并且栈中元素个数count减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

• 栈的空间复杂度为O(1)
• 栈的时间复杂度为O(1)

支持动态扩容的顺序栈

动态扩容的栈的示意图

• 出栈的时间复杂度始终不变，为O(1)
• 入栈，当栈申请的内存足够时，时间复杂度为O(1)
• 入栈，当栈需要扩容时，时间复杂度为O(n)

对于入栈操作来说，最好情况时间复杂度是O(1)，最坏情况时间复杂度是O(n)。那么入栈的平均时间复杂度是多少？

为了方便分析，需要事先做一些假设和分析：

• 栈空间不够时，我们重新申请一个是原来大小两倍的数组；
• 为了简化分析，假设只有入栈操作没有出栈操作；
• 定义不涉及内存搬移的入栈操作为simple-push操作，时间复杂度为O(1)

如果当前栈大小为 K，并且已满，当再有新的数据要入栈时，就需要重新申请 2 倍大小的内存，并且做 K 个数据的搬移操作，然后再入栈。但是，接下来的 K-1 次入栈操作，我们都不需要再重新申请内存和搬移数据，所以这 K-1 次入栈操作都只需要一个 simple-push 操作就可以完成。为了让你更加直观地理解这个过程，请看下面这张图。

这 K 次入栈操作，总共涉及了 K 个数据的搬移，以及 K 次 simple-push 操作。将 K 个数据搬移均摊到 K 次入栈操作，那每个入栈操作只需要一个数据搬移和一个 simple-push 操作。以此类推，入栈操作的均摊时间复杂度就为 O(1)。

通过这个例子的实战分析，也印证了前面讲到的，均摊时间复杂度一般都等于最好情况时间复杂度。因为在大部分情况下，入栈操作的时间复杂度 O 都是 O(1)，只有在个别时刻才会退化为 O(n)，所以把耗时多的入栈操作的时间均摊到其他入栈操作上，平均情况下的耗时就接近 O(1)。

栈在函数调用中的应用

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。为了更好地理解，看下这段代码的执行过程。

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}

int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

上述代码中对应的函数栈里出栈、入栈的操作，如图所示

栈在表达式求值中的应用

编译器如何利用栈来实现表达式求值

比如一个简单的四则运算：34+13*9+44-12/3

编译器通过两个栈来实现，其中一个保存操作数的栈，另一个是保存运算符的栈。从左向右遍历表达式，当遇到数字，就压入操作数栈；当遇到运算符，就与运算符栈顶元素进行比较。

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

我们将3+5*8-6这个表达式的计算过程画成一张图

栈在括号匹配中的应用

假设表达式中只包含三种括号：()、[]、{}，并且它们可以任意嵌套。

我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。

浏览器前进、后退功能的实现

我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。

比如你顺序查看了 a，b，c 三个页面，我们就依次把 a，b，c 压入栈，这个时候，两个栈的数据就是这个样子：

当你通过浏览器的后退按钮，从页面 c 后退到页面 a 之后，我们就依次把 c 和 b 从栈 X 中弹出，并且依次放入到栈 Y。这个时候，两个栈的数据就是这个样子：

这个时候你又想看页面 b，于是你又点击前进按钮回到 b 页面，我们就把 b 再从栈 Y 中出栈，放入栈 X 中。此时两个栈的数据是这个样子：

这个时候，你通过页面 b 又跳转到新的页面 d 了，页面 c 就无法再通过前进、后退按钮重复查看了，所以需要清空栈 Y。此时两个栈的数据这个样子：

09 | 队列：队列在线程池等有限资源池中的应用

如何理解队列？

先进者先出，这就是典型的“队列”。

栈只有两个基本操作：入栈push()和出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队enqueue()，放一个数据到队列尾部：出队dequeue()，从队列头部取一个元素。

所以，队列跟栈一样，也是一种操作受限的线性表数据结构。

作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列Disruptor、Linux环形缓存，都用到了循环并发队列；

顺序队列和链式队列

队列的实现方式

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

基于数组实现的队列

// 用数组实现的队列
public class ArrayQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 如果tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}

对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

结合下面这张图来理解。当 a、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 的位置。

当我们调用两次出队操作之后，队列中 head 指针指向下标为 2 的位置，tail 指针仍然指向下标为 4 的位置。

根据图片的示意，随着不停地进行入队、出队操作，head和tail斗殴会持续往后移动。当tail移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。

解决这个问题需要用到数据搬移！。但是每次进行出队操作都相当于删除数组下标为0的数据，需要搬移整个队列中的数据，这样出队操作的时间复杂度就会从原来的O(1)变为O(n)。

实际上，可以不用在每次出队时都搬移数据。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。

下面是具体的代码：

// 入队操作，将item放入队尾
public boolean enqueue(String item) {
  // tail == n表示队列末尾没有空间了
  if (tail == n) {
    // tail ==n && head==0，表示整个队列都占满了
    if (head == 0) return false;
    // 数据搬移
    for (int i = head; i < tail; ++i) {
      items[i-head] = items[i];
    }
    // 搬移完之后重新更新head和tail
    tail -= head;
    head = 0;
  }
  
  items[tail] = item;
  ++tail;
  return true;
}

从代码中，我们可以将head到tail之间的数据，整体搬移到数组中 0 到tail-head的位置。

这种情况下，出队的时间复杂度为O(1)。入队的时间复杂度最好情况下是O(1)，最坏情况下是O(n)，平均时间复杂度是O(1)。

基于链表的队列实现方法

基于链表的实现，我们同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。如图所示，入队时，tail->next= new_node, tail = tail->next；出队时，head = head->next。

循环队列

循环队列可以解决用数据来实现队列存在的数据搬移操作。即：循环队列可以避免数据搬移。

看图，感受下循环队列：

图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：

通过这样的方法，我们成功避免了数据搬移操作。

要想写出没有 bug 的循环队列的实现代码，最关键的是，确定好队空和队满的判定条件。

循环队列中，判断队列为空的判断条件仍然是 head == tail。但是队列满的判断条件就稍微有点复杂。先看一张队列满的图：

就像图中画的队满的情况，tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。多画几张队满的图，你就会发现，当队满时，(tail+1)%n=head。

当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。

代码示意：

public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

阻塞队列和并发队列

阻塞队列和并发队列这种特殊特性的队列应用会比较广泛。

阻塞队列其实就是在队列基础上增加了阻塞操作。

在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

上述的定义就是一个“生产者 - 消费者模型”！是的，我们可以使用阻塞队列，轻松实现一个“生产者 - 消费者模型”！

这种基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。

而且不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应对一个“生产者”。

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

10 | 递归：如何利用三行代码找到“最终推荐人”？

如何理解递归？

去的过程叫“递”，回来的过程叫归。基本上，所有递归问题都可以用递归公式来表示。

比如，想在电影院中寻找自己在哪一排，可以写成这样的公式：

f(n) = f(n-1)+1
其中，f(1)=1

f(n)表示你想知道自己在哪一排，f(n-1)表示前面一排所在的排数，f(1)=1表示第一排的人知道自己在第一排。有了这个公式，可以很轻松写出递归代码：

int f(int n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}

递归需要满足的三个条件

只要同时满足这三个条件，就可以用递归来解决。

1. 一个问题的解可以分解为几个子问题的解

• 子问题就是数据规模更小的问题。

2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3. 存在递归终止条件

如何编写递归代码

写递归代码最关键的是写出递归公式，找到终止条件。

加入这里有n个台阶，每次你可以跨1个台阶或者2个台阶，请问走这个n个台阶有多少种走法？如果有7个台阶，你可以2，2，2，1走上去，也可以1，2，1，1，2走上去。总之走法有很多，那如何用编程求得总共有多少种走法呢？

可以根据第一步的走法把所有走法分为两类，第一类是第一步走了1个台阶，另一类是第一步走了2个台阶。所以n个台阶的走法就等于先走1阶后，n-1个台阶的走法加上先走2阶后，n-2个台阶的走法。用公式表示就是：

f(n) = f(n-1)+f(n-2)

递归终止条件是f(1)=1，f(2)=2。

把递归终止条件和刚刚得到的公式放在一起是这样的：

f(1)=1;
f(2)=2;
f(n)=f(n-1)+f(n-2);

有了公式后，转化成代码：

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递归公式，然后在推敲终止条件，最后将递归公式和终止条件翻译成代码。

对于递归代码，这种试图想清楚整个递归过程的做法，实际上是进入了一个思维误区。很多时候，我们理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。那正确的思维方式应该是怎样的？

如果一个问题A可以分解为若干子问题B、C、D，你可以假设子问题B、C、D已经解决，再次基础上思考如何解决问题A。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单很多了。

因此，编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递归公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归代码要警惕堆栈溢出

堆栈溢出会造成系统性崩溃，后果会非常严重。

系统栈或虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

避免出现堆栈溢出可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度（比如1000）之后，就不再继续往下递归，直接返回报错。比如下面的伪代码片段，为了代码简洁，有些边界条件没有考虑，比如 x<=0。

// 全局变量，表示递归的深度。
int depth = 0;

int f(int n) {
  ++depth；
  if (depth > 1000) throw exception;
  
  if (n == 1) return 1;
  return f(n-1) + 1;
}

递归代码要警惕重复计算

刚才讲的询阶梯的递归代码例子，如果吧整个递归过程分解一下的话，是这样的：

从图中，可以直观地看到，想要计算f(5)，需要先计算f(4)和f(3)，而计算f(4)还需要计算f(3)，因此，f(3)就被计算了很多次，f(4)同理。这就是重复计算问题。

可以通过一个数据结构来避免重复计算，比如散列表来保存已经求过的f(k)。当递归到f(k)时，先看下是否已经求解过了。

按照这个思路来改下刚才的代码：

public int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  
  // hasSolvedList可以理解成一个Map，key是n，value是f(n)
  if (hasSolvedList.containsKey(n)) {
    return hasSolvedList.get(n);
  }
  
  int ret = f(n-1) + f(n-2);
  hasSolvedList.put(n, ret);
  return ret;
}

怎么将递归代码改写成非递归代码？

利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。

把电影院的递归代码可以改成这样：

int f(int n) {
  int ret = 1;
  for (int i = 2; i <= n; ++i) {
    ret = ret + 1;
  }
  return ret;
}

第二个询阶梯的递归代码可以改成这样：

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  
  int ret = 0;
  int pre = 2;
  int prepre = 1;
  for (int i = 3; i <= n; ++i) {
    ret = pre + prepre;
    prepre = pre;
    pre = ret;
  }
  return ret;
}

笼统的讲，可以将所有的递归代码都改成这种迭代循环的非递归写法。

只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。

11 | 排序（上）：为什么插入排序比冒泡排序更受欢迎

排序算法的执行效率

1. 最好情况、最坏情况、平均情况时间复杂度

为什么要区分这三种时间复杂度？第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完全 无序。有序度不同的数据，对于排序的执行时间肯定会有影响的，我们要知道排序算法在不同数据下的西性能表现。

2. 时间复杂度的系数、常数、低阶

时间复杂度反映的是数据规模 n 很大的时候一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。在实际开发中，排序的数据规模可能是10个、100个、1000个这样规模较小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

3. 比较次数和交换（或移动）次数

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

排序算法的内存消耗

针对排序算法的空间复杂度，引入了一个新的概念，原地排序（Sorted in place）。就是特指空间复杂度是O(1)的排序算法。

排序算法的稳定性

针对排序算法，还有一个重要的度量指标，稳定性。这个概念是说：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

举一个例子，有一组数据2、9、3、4、8、3。按照大小排序之后就是2、3、3、4、8、9。经过某种排序算法之后，如果两个3的前后顺序没有改变，那么就把这种排序算法叫做稳定的排序算法。如果前后顺序发生变化，就叫做不稳定的排序算法。

冒泡排序（Bubble Sort）

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

比如，我们对这一组数据4、5、6、3、2、1，从小到大进行排序。第一次冒泡是这样的：

可以看出，经过一次冒泡排序之后，6这个元素已经存储在正确的位置上。要想完成所有数据的排序，只需要进行6次这样的冒泡操作就行了。

刚才的冒泡排序还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。如下图元素排序，只需要4次冒泡操作就可以了。

冒泡排序算法的代码：

// 冒泡排序，a表示数组，n表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

• 冒泡的过程中只涉及相邻数据的交换，只需要常量级的数据空间，所以它的空间复杂度为O(1)，是一个原地排序算法。
• 冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，所以冒泡排序是稳定的排序算法。

插入排序（Insertion Sort）

一个有序的数组，往里面添加一个新的数据后，如何继续保持数据有序？我们只需要遍历数组，找到数据应该插入的位置将其插入即可。

这是一个动态排序的过程，即动态地往有序集合中添加数据，可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据，也可以借鉴上面的插入方法，来进行排序，于是就有了插入排序算法。

插入排序的思想

将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

如图所示，要排序的数据是4、5、6、1、3、2。

插入排序的算法

// 插入排序，a表示数组，n表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

• 插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，这是一个原地排序算法。
• 在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小 的元素，将其放到已排序区间的末尾。

• 选择排序的空间复杂度为O(1)，最好情况、最坏情况和平均情况时间复杂度都为O(n²)
• 选择排序是一种不稳定的排序算法。从图中可以看出，选择排序每次都要找剩余排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

为什么插入排序比冒泡排序更受欢迎？

从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个。

// 冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

// 插入排序中数据的移动操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

所以，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是O(n²)，但是如果我们希望把性能优化做到极致，那肯定首选插入排序。

12 | 排序（下）：如何用快排思想在O(n)内查找第K大元素？

归并排序（Merge Sort）的原理

归并排序的思想：先把数组从中间分成前后两部分，然后对前后两部分分别排序，在将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序使用的是分治思想。分治，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。分治算法一般是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧

归并排序的递推公式：

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解

p...r表示数组的开始下标和结束下标。merge_sort(p...q)和merge(q+1...r)，其中下标q等于p和r的中间位置。也就是(p+r)/2。

伪代码表示归并算法：

// 归并排序算法, A是数组，n表示数组大小
merge_sort(A, n) {
  merge_sort_c(A, 0, n-1)
}

// 递归调用函数
merge_sort_c(A, p, r) {
  // 递归终止条件
  if p >= r  then return

  // 取p到r之间的中间位置q
  q = (p+r) / 2
  // 分治递归
  merge_sort_c(A, p, q)
  merge_sort_c(A, q+1, r)
  // 将A[p...q]和A[q+1...r]合并为A[p...r]
  merge(A[p...r], A[p...q], A[q+1...r])
}

merge(A[p...r], A[p...q], A[q+1...r])这个函数的作用就是将已经有序的A[p...q]和A[q+1...r]合并成一个有序的数组，并且放入A[p...r]。

如图所示，申请一个临时数组tmp，大小与A[p...r]相同。用两个游标i和j，分别指向A[p...q]和A[q+1...r]的第一个元素。比较这两个元素A[i]和A[j]，如果A[i]<=A[j]，就把A[i]放入到临时数组tmp，并且i后移一位，否则将A[j]放入到tmp，j后移一位。重复上述逻辑直到结束，最后再把临时数组tmp中的数据拷贝到原数组A[p...r]中。

merge函数的伪代码如下：

merge(A[p...r], A[p...q], A[q+1...r]) {
  var i := p，j := q+1，k := 0 // 初始化变量i, j, k
  var tmp := new array[0...r-p] // 申请一个大小跟A[p...r]一样的临时数组
  while i<=q AND j<=r do {
    if A[i] <= A[j] {
      tmp[k++] = A[i++] // i++等于i:=i+1
    } else {
      tmp[k++] = A[j++]
    }
  }
  
  // 判断哪个子数组中有剩余的数据
  var start := i，end := q
  if j<=r then start := j, end:=r
  
  // 将剩余的数据拷贝到临时数组tmp
  while start <= end do {
    tmp[k++] = A[start++]
  }
  
  // 将tmp中的数组拷贝回A[p...r]
  for i:=0 to r-p do {
    A[p+i] = tmp[i]
  }
}

归并排序的性能分析

归并排序稳不稳定关键要看merge函数，在合并的过程中，如果A[p...q]和A[q+1...r]之间有相同的元素，那我们可以像伪代码中那样，先把A[p...q]中的元素放入tmp数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。

归并排序的时间复杂度是O(nlogn)。

归并排序不是原地排序算法，归并排序的空间复杂度是O(n)。

快速排序（Quicksort）的原理

快排利用的也是分治思想。快排的思想：如果要排序数组中下标从p 到r 之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。

遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。

用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，知道区间缩小为1，就说明所有的数据都有序了。

递推公式如下：

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

终止条件：
p >= r

递归的伪代码：

// 快速排序，A是数组，n表示数组的大小
quick_sort(A, n) {
  quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r为下标
quick_sort_c(A, p, r) {
  if p >= r then return
  
  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, r)
}

partition()分区函数实际上会随机选择一个元素作为pivot(一般情况下，可以选择p到r区间的最后一个元素)，然后对A[p...r]分区，函数返回pivot的下标。

在不考虑空间消耗的情况下，partition分区函数可以写得非常简单。申请两个临时数组X和Y，遍历A[p...r]，将小于pivot的元素都拷贝到临时数组X，将大于pivot的元素都拷贝到临时数组Y。最后再将数组X和数组Y中数据顺序拷贝到A[p...r]。

上述这种快排方式就不是原地算法了。如果希望快排是原地算法，那它的空间复杂度就得是O(1)。所以，需要在A[p...r]的原地完成分区操作。

伪代码如下：

partition(A, p, r) {
  pivot := A[r]
  i := p
  for j := p to r-1 do {
    if A[j] < pivot {
      swap A[i] with A[j]
      i := i+1
    }
  }
  swap A[i] with A[r]
  return i
}

代码的逻辑示意图：

归并排序和快排的区别在哪里？

可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

快速排序的性能分析

• 快排是一种原地、不稳定的排序算法。
• 快速排序的时间复杂度是O(nlogn)。

13 | 线性排序：如何根据年龄给100万用户数据排序？

三种事件复杂度是O(n)的排序算法：桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫做线性排序（Linear sort）。这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。

桶排序（Bucket Sort）

通排序，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个 桶里的数据按照顺序依次取出，组成的序列 就是有序的了。

桶排序的时间复杂度为什么是O(n)？

如果要排序的数据有n个，我们把它们均匀地划分到m个桶内，每个桶内就有k=n/m个元素。每个桶内部使用快速排序，时间复杂度为O(k * logk)。m个桶排序的时间复杂度就是O(m * k * logk)，因为k=n/m，所以整个桶排序的时间复杂度就是O(n * log(n/m))。当桶的个数m接近数据个数n时，log(n/m)就是一个非常小的常量，这个时候桶排序的时间复杂度接近O(n)。

使用桶排序需要满足这些条件：