数据结构与算法 ​

数据结构与算法是相辅相成的。

数据结构是为算法服务的，算法要作用在特定的数据结构之上。

学习数据结构与算法，有一个很重要的概念就是-复杂度分析。

数据结构与算法解决的是如何更快、更省地存储和处理数据。

因此，我们就需要一个考量效率和资源消耗的方法，就是复杂度分析方法。

数据结构与算法学习图示：

上图是 20 个最常用的、最基础的数据结构与算法。

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、树。

10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

复杂度分析 ​

数据结构与算法本身解决的是两个问题：

• 如何让代码运行得更快；
• 如何让代码更省空间。

对于算法来说，执行效率是一个非常重要的考量指标。如何衡量编写的算法代码的执行效率？

这就牵扯到 2 个概念：时间复杂度分析、空间复杂度分析。

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

为什么需要复杂度分析 ​

你可能会问如果把代码跑一遍，通过统计、监控，就可以得到算法执行的时间和占用的内存大小。

那么为什么还需要做复杂度分析？

首先这种评估算法执行效率的方法是对的，它也有一个名字叫 事后统计法。

这种统计方法有非常大的局限性。

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

我们需要一种不需要具体数据测试，就可以粗略估计算法的执行效率的方法。

这就是我们需要了解的时间、空间复杂度分析方法。

大 O 复杂度表示法 ​

所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比。

我们可以把这个规律总结成一个公式：

T(n) = O(f(n));

T(n) = O(f(n));

T(n) 表示代码执行的时间，n 表示数据规模的大小。

f(n) 表示每行代码执行的次数总和。

O 表示代码执行时间 T(n) 与 f(n) 表达式成正比。

大 O 时间复杂度实并不具体表示代码的真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势。

所以也被叫做渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

时间复杂度分析 ​

分析一段代码的时间复杂度有三个比较实用的方法：

1. 只关注循环执行次数最多的一段代码

我们在分析一个算法、一段代码的时间复杂度时，只需要关注循环执行次数最多的那段代码即可。

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

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

比如上面这段代码，因为存在一个 for 循环，其中的代码被执行了 n 次，所以时间复杂度为 O(n)。

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

function cal (n) {
  let sum1 = 0;
  for (let p = 1; p < 100; p++) {
    sum1 = sum1 + p;
  }
  
  let sum2 = 0;
  for (let q = 1; q < n; q++) {
    sum2 = sum2 + q;
  }
  
  let sum3 = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      sum3 = sum3 + i * j;
    }
  }
  
  return sum1 + sum2 + sum3;
}

function cal (n) {
  let sum1 = 0;
  for (let p = 1; p < 100; p++) {
    sum1 = sum1 + p;
  }
  
  let sum2 = 0;
  for (let q = 1; q < n; q++) {
    sum2 = sum2 + q;
  }
  
  let sum3 = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      sum3 = sum3 + i * j;
    }
  }
  
  return sum1 + sum2 + sum3;
}

这段代码可以分为 3 部分，分别求 sum1、sum2、sum3。

我们可以分别分析每一部分的时间复杂度，然后把它们放到一起，再取一个量级最大的作为整段代码的复杂度。

第一段代码是一个常量的执行时间，跟 n 的规模无关。

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

第二段代码和第三段代码的时间复杂度分别是 O(n) 和 O(n²)。

综合这三段代码的时间复杂度，我们取其中最大的量级，所以，这段代码的时间复杂度为 O(n²)。

也就是说，总的时间复杂度等于量级最大的那段代码的时间复杂度。

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

我们可以把乘法法则看作嵌套循环。

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

  return ret;
}

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

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

  return ret;
}

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

常见的时间复杂度实例分析 ​

我们把时间复杂度为非多项式量级的算法问题较多 NP（Non-DeterministicPolynomial，非确定多项式）问题。

当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。

所以，非多项式时间复杂度的算法是一种非常低效的算法。

O(1) ​

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

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

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

只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万的代码，时间复杂度也为 O(1)。

O(logn)、O(nlogn) ​

对数时间复杂度非常常见。

let i = 1;

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

let i = 1;

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

对于上面这个例子，只要我们能计算出这行代码被执行了多少次，就可以知道整段代码的时间复杂度。

变量 i 从 1 开始，每次循环都会乘以 2。当 i 大于 n 时，循环结束。

$2^0$ $2^1$ $2^2$ ... $2^k$ ... $2^x$ = n

我们可以通过 $2^x = n$ 求解 x，即 $x = log2^n$。所以时间复杂度为 $O(log2^n)$;

现在再看这段代码：

let i = 1;

while (i <= n) {
  i = i * 3;
}

let i = 1;

while (i <= n) {
  i = i * 3;
}

根据刚才的思路，很简单就可以看出，这段代码的时间复杂度为 $O(log3^n)$。

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

采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。

我们介绍过计算时间复杂度的乘法法则，如果一段代码的时间复杂度是 $O(logn)$，我们循环执行 n 遍，时间复杂度就是 $O(nlogn)$。

O(m + n)、O(m * n) ​

代码的复杂度由两个数据的规模决定。

function cal (m, n) {
  let sum1 = 0;
  for (let i = 1; i < m; i++) {
    sum1 = sum1 + i;
  }
  
  let sum2 = 0;
  for (let j = 1; j < n; j++) {
    sum2 = sum2 + j;
  }
  
  return sum1 + sum2;
}

function cal (m, n) {
  let sum1 = 0;
  for (let i = 1; i < m; i++) {
    sum1 = sum1 + i;
  }
  
  let sum2 = 0;
  for (let j = 1; j < n; j++) {
    sum2 = sum2 + j;
  }
  
  return sum1 + sum2;
}

由代码可以看出， 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))。

空间复杂度分析 ​

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。

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

还是看下面例子（这段代码有点 low，主要是方便解释）。

function print (n) {
  let i = 0;
  let a = [];
  
  for (i; i < n; i++) {
    a[i] = i * i;
  }
  
  for (i = n - 1; i >= 0; --i) {
    console.log(a[i]);
  }
}

function print (n) {
  let i = 0;
  let a = [];
  
  for (i; i < n; i++) {
    a[i] = i * i;
  }
  
  for (i = n - 1; i >= 0; --i) {
    console.log(a[i]);
  }
}

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

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

而且，空间复杂度比时间复杂度分析要简单很多。

总结 ​

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度不多，从低阶到高阶有：$O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)$。

复杂度分析并不难，关键在于多练。

技术拓展 ​

项目性能测试和代码的复杂度分析是否冲突？ ​

渐进式时间、空间复杂度分析和性能基准测试并不冲突，而是相辅相成的。一个低阶的时间复杂度程序极大的可能性会优于一个高阶的时间复杂度程序。所以在实际编程中，时刻关系理论时间，空间度模型是有助于产出效率高的程序的。

同时，因为渐进式时间，空间复杂度分析只是提供一个粗略的分析模型，因此也不会浪费太多时间。重点在于编程时，要具有这种复杂度分析的思维。

时间复杂度 ​

今天主要分析4个复杂度分析方面的知识点，最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity）。

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

先看下面的例子。

function find (arr, n, x) {
	let pos = -1;
  
  for (let i = 0; i < n; i++) {
    if (arr[i] == x) pos = i;
  }
  
  return pos;
}

function find (arr, n, x) {
	let pos = -1;
  
  for (let i = 0; i < n; i++) {
    if (arr[i] == x) pos = i;
  }
  
  return pos;
}

这段代码要实现的功能是，在一个无序数组中，查找变量 x 出现的位置，如果没有找到，就返回 -1。

按照之前讲的分析方法，这段代码的复杂度是 O(n)，其中，n 代表数组长度。

但其实我们在数组中查找一个数据，并不需要每次把整个数组都遍历一遍，如果找到元素就可以结束循环。

我们可以优化一下这段代码。

function find (arr, n, x) {
	let pos = -1;
  
  for (let i = 0; i < n; i++) {
    if (arr[i] == x) {
      pos = i;
      break;
    };
  }
  
  return pos;
}

function find (arr, n, x) {
	let pos = -1;
  
  for (let i = 0; i < n; i++) {
    if (arr[i] == x) {
      pos = i;
      break;
    };
  }
  
  return pos;
}

这时，就出现一个问题。在我们优化完之后，这段代码的时间复杂度还是 O(n) 吗？

案例中要查找的变量 x 可能出现在数组的任意位置。

如果数组第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n - 1 个数据，这时时间复杂度是 O(1)。

如果数据中不存在变量 x，那就需要把数组遍历一遍，时间复杂度就成了 O(n)。

所以，不同情况下，这段代码的时间复杂度是不同的。

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

• 最好情况时间复杂度
• 最坏情况时间复杂度
• 平均情况时间复杂度

顾名思义，最好情况时间复杂度就是，在理想的情况下，执行这段代码的时间复杂度。

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

平均情况时间复杂度 ​

最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。

我们需要引入另一个概念，平均情况时间复杂度。后面简称为平均时间复杂度。

我们继续以刚才的例子进行分析。

function find (arr, n, x) {
	let pos = -1;
  
  for (let i = 0; i < n; i++) {
    if (arr[i] == x) {
      pos = i;
      break;
    };
  }
  
  return pos;
}

function find (arr, n, x) {
	let pos = -1;
  
  for (let i = 0; i < n; i++) {
    if (arr[i] == x) {
      pos = i;
      break;
    };
  }
  
  return pos;
}

要查找的变量 x 在数组中的位置，有 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)。

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

均摊时间复杂度 ​

现在，你应该已经掌握算法复杂度分析的大部分内容。下面来讲一个更加高级的概念，均摊时间复杂度以及它对应的分析方法，摊还分析（平摊分析）。

均摊时间复杂度，听起来和平均时间复杂度有点类似。初学者经常把这两个概念弄混。大部分情况下，我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某种特殊情况下才会用到，而均摊时间复杂度应用的场景比它更加特殊、更加有限。

还是借助一个例子来理解。

const arr = new Array(10);
let count = 0;

function insert (val) {
  if (count == arr.length) {
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
      sum = sum + arr[i];
    }
    arr[0] = sum;
    count = 1;
  }
  
  arr[count] = val;
  count++;
}

const arr = new Array(10);
let count = 0;

function insert (val) {
  if (count == arr.length) {
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
      sum = sum + arr[i];
    }
    arr[0] = sum;
    count = 1;
  }
  
  arr[count] = val;
  count++;
}

这段代码实现了一个向数组中插入数据的功能。当数组满了之后，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后将将新的数据插入。如果数组存在空闲空间，则直接将数据插入数组。

那这段代码的时间复杂度是多少？我们可以用之前讲过的三种时间复杂度的分析方法来分析。

最理想的情况下，数组中有空闲空间，只需要将数据插入到数组下标为 count 的位置，所以最好情况时间复杂度为 O(1)。

最坏的情况下，数组中没有空闲空间，需要先做一次数组的遍历求和，然后再将数据插入，所以最坏情况时间复杂度为 O(n)。

平均复杂度为 O(1)。我们可以通过之前讲的概率论来分析。

假设数组的长度为 n，根据数据插入的位置不同，我们可以分为 n 种情况，每种情况的时间复杂度都为 O(1)。

除此之外，还有一种 ”额外“ 情况，就是在数组没有空闲空空间时插入一个数据，这个时候的时间复杂度为 O(n)。

而且，这 n + 1 中情况发生的概率一样，都是 1/(n + 1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：

至此为止，前面说的时间复杂度的计算，理解起来应该都没有问题。但是这个例子中的平均复杂度的计算其实并不需要这么复杂，不需要引入概率论的知识。我们先来对比一下这个 insert() 例子和之前的 find() 例子，你就会发现两者有很大差别。

首先，find() 函数在极端情况下，复杂度才为 O(1)。但 insert() 在大部分情况下，时间复杂度都为 O(1)。只有个别情况下，复杂度才比较高，为 O(n)。这是 insert()第一个区别于 find() 的地方。

我们再来看第二个不同的地方。对于 insert() 函数来说，O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。

所以，针对这样一种特殊场景的复杂度分析，我们并不需要像之前讲平均复杂度分析方法那样，找出所有的输入情况及相应的发生概率，然后再计算加权平均值。针对这种特殊的场景，我们引入了一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度我们起了一个名字，叫均摊时间复杂度。

我们还是继续看在数组中插入数据的这个例子。每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。你都理解了吗？

均摊时间复杂度和摊还分析应用场景比较特殊，所以我们并不会经常用到。为了方便你理解、记忆，我这里简单总结一下它们的应用场景。如果你遇到了，知道是怎么回事儿就行了。

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

尽管很多数据结构和算法书籍都花了很大力气来区分平均时间复杂度和均摊时间复杂度，但其实我个人认为，均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多精力去区分它们。你最应该掌握的是它的分析方法，摊还分析。至于分析出来的结果是叫平均还是叫均摊，这只是个说法，并不重要。

总结 ​

今天我们学习了几个复杂度分析相关的概念，分别有：最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度、均摊时间复杂度。之所以引入这几个复杂度概念，是因为，同一段代码，在不同输入的情况下，复杂度量级有可能是不一样的。

在引入这几个概念之后，我们可以更加全面地表示一段代码的执行效率。而且，这几个概念理解起来都不难。最好、最坏情况下的时间复杂度分析起来比较简单，但平均、均摊两个复杂度分析相对比较复杂。

一、数组 ​

说起数组，我想你肯定不会陌生，甚至还会自信的说，它很简单。

的确，在每一种编程语言中，都会有数组这种数据类型。不过，它不仅仅是一种编程语言的类型，还是一种最基础的数据结构。

尽管数组看起来非常基础、简单，但是绝大多人并没有理解这个基础结构的精髓。

在大部分编程语言中，数组都是从 0 开始编写的，但你是否下意识地想过，为什么数组要从 0 开始，而不是 1 开始？从 1 开始不是更符合人类的思维习惯？你可以带着这个问题学习接下来的内容。

如何实现随机访问 ​

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

ECMAScript 中定义的数组可以存储任意类型数据。

这里有几个关键词，理解这几个关键词，就可以彻底掌握数组的概念。

线性表（Linear List） ​

顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。

其实除了数组，链表、队列、栈等也是线性表结构。

与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为在非线性表中数据之间并不是简单的前后关系。

连续的内存空间和相同类型数据 ​

正因为这两个限制，它才有了随机访问的特性。但有利也有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保持连续性，就需要做大量的数据搬移的操作。

那么，数组是如何根据下标随机访问数组元素的？

我们拿一个长度为 10 的数组 const arr = new Array(10); 来举例。 当你创建数组时，计算机给数组分配了一块连续内存空间 1000～1039，其中，内存的首地址为 base_address = 1000。

我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问来访问内存中的数据。

当计算机需要随机访问数据中的某个元素是时，它会首先通过下面的寻址公式，计算出该元素的内存地址：

a[i]_address = base_address + i * data_type_size

a[i]_address = base_address + i * data_type_size

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

数组和链表的区别 ​

关于数据和链表区别，经常有人说 ”链表适合插入、删除、时间复杂度 O(1)“，数组适合查找，查找时间复杂度为 O(1)。

实际上这种表述是不准确的。数组的确适合查找操作，但是查找的时间复杂度并不为 O(1)。

即便是排好序的数组，用二分查找，时间复杂也是 $O(log^n)$ 。所以正确的表述应该是，数据支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

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

前面提到过，数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效。

现在就来详细说一下，究竟为什么会导致低效？有哪些改进方法？

插入操作 ​

假如数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。 这时，我们需要将 k～n 这部分的元素顺序地向后以移动一位。那插入的时间复杂度是多少？

如果是在数组的末尾插入元素，那就不需要移动数据，这时的时间复杂度是 O(1)。 如果在数组中的开头插入数据，那后面所有的数据都要移动，所以最坏时间复杂度是 O(n)。 因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 (1 + 2+ 3 + ... n) / n = O(n)。

如果数组中的元素是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 k 之后的数据。但是，如果数组中存在的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数据插入到第 k 个位置，为了避免大规模的数据搬移，我们还有一个简单的方法，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入到第 k 个位置。

为了更好理解，下面来举个例子。

const arr = new Array(10);

arr.push('a');
arr.push('b');
arr.push('c');
arr.push('d');
arr.push('e');

const arr = new Array(10);

arr.push('a');
arr.push('b');
arr.push('c');
arr.push('d');
arr.push('e');

我们需要将元素插入到第 3 个位置。这时只需要将 c 放入 a[5]，将 a[2] 赋值给 x 即可。

最后数组中元素如下：a, b, x, d, e, c。

利用这种处理技巧，在特定场景下，在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。这种处理思想在快排中也会用到。

删除操作 ​

跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续。

如果删除数组末尾的数据，最好情况时间复杂度为 O(1)。如果删除开头的数据，则最坏情况时间复杂度为 O(n)。平均情况时间复杂度也为 O(n)。

实际上，在某些特殊场景下，我们并不一定非要追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率也会得到提升。

继续来看例子。比如数组中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们需要依次删除 a，b，c 三个元素。

为了避免 d，e，f，g，h 这几个数据被搬移三次，我们可以先记录下已经删除的数据。每次的删除并不是真正地搬移数据，只是记录数据已经删除。当数组中没有更多空间存储数据时，我们再触发一次真正的删除操作，这样就可以大大减少删除操作导致的数据搬移。

如果你了解过 JVM，你会发现，这其实就是 JVM 标记清除垃圾回收算法的核心思想。

数据结构和算法的魅力就在于此，很多时候我们并不是要死记硬背某个数据结构或算法，而是学习它背后的思想和处理技巧，这些东西才是最有价值的。如果你足够细心，应该会发现不管是在软件开发还是架构设计中，总能找到某些算法和数据结构的影子。

数组的越界问题 ​

了解了数组的基本操作之后，可以说下数据访问越界的问题。

数组越界问题在ECMAScript 中定义的数组中体现并不明显。因为其存在静默失败的特性。

越界访问只会返回 undefiend，但是数组也存在存储范围，其范围是0 到 2^32 - 1。

let arr = [];

arr[Math.pow(2, 32) - 2] = 10;

arr.push(12);

console.log(arr); // Invalid array length

let arr = [];

arr[Math.pow(2, 32) - 2] = 10;

arr.push(12);

console.log(arr); // Invalid array length

但其实，在其他编程语言中，数组访问越界往往会产生严重的问题。比如下面这个 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;
}

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“，而是会无限打印 ”hello world“。

原因数组大小为 3，而上述代码因为书写错误，当 i = 3 时，数组 a[3] 访问越界。

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

数据越界在 C 语言中是一种未觉行为，并没有规定数组访问越界时编译器应该如何处理。 因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移量计算得到的内存地址是可用的，那么程序就可能不会报任何错误。

这种情况下，一般都会出现莫名其妙的逻辑错误，就像上面的例子，调试的难度很大。而且，很多计算器病毒也正是利用到了代码中数组越界可以访问非法地址的漏洞，来攻击系统，所以写代码的时候一定要警惕数组越界。

不过并非所有的语言都像 C 一样，把数组越界检查的工作丢给程序员来做，向 java 本身存在越界检查，js 则会静默失败处理。

int[] a = new int[3];
a[3] = 10;

int[] a = new int[3];
a[3] = 10;

运行上述 java 代码，会抛出 java.lang.ArrayIndexOutOfBoundsException。

容器能否替代数组？ ​

针对数组类型，很多语言都提供了容器类。比如 Java 中的 ArrayList 、C++ STL 中的 vector。

这里拿 Java 语言来举例。如果你是 java 工程师，几乎天天用 ArrayList ，对它应该非常熟悉。那它与数组相比，到底存在哪些优势？

ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是支持动态扩容。

数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时，就需要重新分配一个更大的空间，将原来的数据复制过去，然后将新的数据插入。

如果使用 ArrayList，我们就完全不需要关心底层的扩容逻辑，ArrayList 已经帮我们实现好了。每次存储空间不够的时候，它都会将空间自动扩容为 1.5 倍左右。不过，扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。

比如我们要从数据库中取出 10000 条数据放入 ArrayList。我们看下面这段代码，相比不指定大小，事先指定数据大小可以省掉很多内存申请和数据搬移操作。

ArrayList<User> users = new ArrayList(10000);

for (int i = 0; i < 10000; ++i) {
  users.add(xxx);
}

ArrayList<User> users = new ArrayList(10000);

for (int i = 0; i < 10000; ++i) {
  users.add(xxx);
}

作为 java 这种高级语言来说，是不是数组就没有价值了？相信你也知道答案，当然不是，任何数据结构都有其存在的意义。

• Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能损耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组；
• 如果数据大小事先已知，并且对数据的操作非常简单，不适用 ArrayList 提供的大部分方法，也可以直接使用数组；
• 当表示多维数组时，用数组表示会比较直观。比如 Object [][] array; 。使用容器则需要这样定义 ArrayList<ArrayList<object>>；

简单做下总结，对于业务开发来说，直接使用容器就足够了，省时省力。虽然会损耗一定的性能，完全不影响系统整体的性能。但如果是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

总结 ​

今天主要学习了数组。数组是最基础、最简单的数据结构了。数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况复杂度为 O(n)。

在平时的业务中，我们可以直接使用编程语言提供的容器类，但是如果特别底层的开发，直接使用数组比较合适。

技术拓展 ​

为什么大多数编程语言，数组要从 0 开始编号，而不是从 1 开始？ ​

从数组的内存模型上来看，”下标“ 最确切的定义应该是 ”偏移（offset）“。前面也说过，如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就表示 k 个 type_size 的位置，所以计算 a[k] 的内存地址只需要这样写：

a[k]_address = base_address + k * type_size

a[k]_address = base_address + k * type_size

但是，如果数组从 1 开始计数，那我们计算数组元素 a[k] 的内存地址就会变为：

a[k]_address = base_address + (k - 1) * type_size

a[k]_address = base_address + (k - 1) * type_size

对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，又多了一次减法指令。

数组作为非常基础的数据结构，通过下标随机访问数组元素也是非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择从 0 开始编号，而不是从 1 开始。

不过，上面说的都算不上压倒性的证明，最主要的原因可能还是历史原因。

C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言，或者说，为了在一定程度上减少 C 语言程序员学习 Java 的成本，因此继续沿用了从 0 开始计数的习惯。实际上，很多语言中数组的下标并不是从 0 开始的，比如 MatLab。甚至还有一些语言支持负数下标，比如 Python。

V8 中的垃圾回收算法 ​

v8 引擎对于栈和堆中的垃圾回收有不同的处理措施。

对于栈来说，使用 ESP 的指针向下移动来销毁该函数保存在栈中的执行上下文。

对于堆来说，就需要使用 JavaScript 的垃圾回收器。

V8 中会把堆分为老生代和新生代两个区域，新生代存放的是生存时间短的对象，老生代存放的是生存时间比较长的对象。

新生区通常只支持 1～8M 的容量，老生区支持的容量大很多。

对于新生区和老生区分别使用两个不同的垃圾回收器：

• 副垃圾回收器，主要负责新生代的垃圾回收；
• 主垃圾回收器，主要负责老生代的垃圾回收；

副垃圾回收器，使用 Scavenge 算法进行处理。

主垃圾回收器，采用标记-清除（Mark-Sweep）的算法进行垃圾回收。还有另一种算法标记-整理（Mark-Compact）算法。

二维数组的内存寻址公式 ​

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

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

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

另外，对于数组访问越界造成无限循环，应该和编译器有关，对于不同的编译器，在内存分配时，会按照内存地址递增或者递减的方式进行分配。如果是内存地址递减的方式，就会造成无限循环。

二、链表 ​

学习链表之前，先来讨论一个经典的链表应用场景，那就是 LRU 缓存淘汰算法。

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有非常广泛的应用，比如常见的 CPU 缓存、数据缓存、浏览器缓存等等。

缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该保存，这时就需要缓存淘汰策略来决定。

常见的缓存淘汰策略有三种：

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

链表结构 ​

相对于数组，链表是一种稍微复杂的数据结构。

我们可以先从底层的存储结构来看。为了直观对比，先看下面这张图。

从上图可以看到，数组需要一块连续的内存空间来存储，对内存的要求比较高。链表并不需要一块连续的内存空间，它通过 “指针” 将一组零散的内存块串联起来使用。

如果我们申请一个 100MB 大小的数组，当内存中没有联系的、足够大的存储空间时，即便内存的剩余总可用空间大于 100 MB，仍然会申请失败。链表则不会这样，所以当我们申请的是 100 MB 大小的链表，不会考虑是否存在连续的空间，不会存在申请失败的问题。

链表的结构有很多，今天主要介绍三种常见的链表结构，它们分别是：单链表、双向链表、循环链表。

单链表 ​

上面刚刚讲到，链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的 “结点”。

为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。我们把这个记录下个结点地址的指针叫做后继指针 next。

在单链表中，有两个结点是比较特殊的，分别是第一个结点和最后一个结点。

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

和数组相同，链表也支持数据的查找、插入和删除操作。

在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度为 O(n)。 在链表中插入或者删除一个数据，我们并不需要为了保存内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的。

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

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

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

循环链表 ​

循环链表是一种特殊的单链表。循环链表也很简单，它跟单链表唯一的区别就在于尾结点。

单链表的尾结点指针指向空地址，空地址代表是最后的结点。 循环链表的尾结点指针指向链表的头节点，它像一个环一样首尾相连，所以叫做 ”循环“ 链表。

循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。 比如著名的 ”约瑟夫问题“ 。尽管用单链表可以实现，但是用循环链表实现的话，代码就会简洁很多。

双向链表 ​

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

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

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

双向循环链表 ​

上面已经说了循环链表和双向链表，如果把这两种链表整合在一起，就是双向循环链表。

双向链表为什么比单链表高效 ​

你可能会问，刚才说到单链表的插入、删除操作的时间复杂度已经是 O(1) 了，双向链表为什么比单链表更加高效？

先来看删除操作。

实际软件开发中，链表删除一个数据通常存在两种情况：

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

对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点一个一个一次遍历对比，直到找到值等于给定值的结点，然后将其删除。尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的时间复杂度为 O(n)。

对于第二种情况，我们已经找到要删除的结点，但是删除某个结点 q 需要知道其前驱结点，但是单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，还是需要从头结点开始遍历链表，直到找到 p.next = q，说明 p 是 q 的前驱结点。但是对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要想单链表那样遍历。所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要 O(1) 的时间复杂度就搞定了。

同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。

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

现在，你是不是也觉得双向链表比单链表更高效？这就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因。如果你熟悉 java 语言，肯定知道 LinkedHashMap 这个容器。如果你深入研究 LinkedHashMap 的实现原理，就会发现其中就用到了双向链表的这种数据结构。

空间换时间的设计思想 ​

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

继续说下开篇缓存的例子。缓存实际上就利用了空间换时间的设计思想。如果我们把数据存储到硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。但如果我们通过缓存技术，事先将数据加载到内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。

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

链表 VS 数据 ​

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

不过，数组和链表的对比，不能局限于时间复杂度。而且，在实际的软件开发过程中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。 链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

CPU 在内存中读取数据时，会把读取到的数据加载到 CPU 的缓存中。CPU 每次从内存中读取数据会读取一个数据块并保存到 CPU 缓存中，然后下次访问内存数据的时候会优先从 CPU 缓存开始查找，如果找不到才从内存中取。这样就实现了比内存访问速度更快的机制，也就是 CPU 缓存存在的意义。对于数组来说，存储空间是连续的，所以在加载某个下标时可以把后面的几个元素也加载到 CPU 缓存中，这样执行速度就会快于存储空间不连续的链表存储。

数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的内存空间分配给它，导致 ”内存不足（out of memory）“ 。如果声明的数组过小，则可能出现不够用的情况。这时，只能再申请一个最大的内存空间，把原数组拷贝进去，非常费时。 链表本身没有大小的限制，天然地支持动态扩容，这也是它与数组最大的区别。

你可能会反驳，Java 中的 ArrayLIst 容器，也可以支持动态扩容啊？

如果我们往支持动态扩容的数组中插入一个数据时，如果数组中没有空闲空间，就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非常耗时的。举个比较极端的例子，如果我们用 ArrayList 存储了 1GB 大小的数据，这个时候已经没有空闲空间，当我们再插入数据的时候，ArrayList 会申请一个 1.5 GB 大小的存储空间，并且把原来 1 GB 的数据拷贝到新申请的空间上。听起来是不是就很耗时？

除此之外，如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗也会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，有可能导致频繁的 GC（Garbage Collection，垃圾回收）。

所以，在我们实际的开发中，针对不同类型的项目，跟根据具体情况，权衡究竟是选择数组还是链表。

链表代码编写技巧 ​

理解指针或引用含义 ​

事实上，看懂链表的结构并不难，但是一旦把它和指针混在一起，就很难理解。所以要想写对链表代码，首先就要理解好指针。

实际上，对于指针的理解，只需要记住下面这句话就可以了：

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

我们可以结合链表代码的编写过程，慢慢分析。

在编写链表代码的时候，经常会有这样的代码：p.next = q。这行代码是说，p 结点的 next 指针存储了 q 结点的内存地址。

还有一个更复杂的，也是我们写链表代码经常遇到的：p.next = p.next.next 。这行代码表示，p 结点的 next 指针存储了 p 结点的下下一个结点的内存地址。

掌握了指针或引用的概念，你应该可以很轻松地看懂链表代码。

警惕指针丢失和内存泄漏 ​

不知道你是否存在这样的感觉，写链表代码的时候，指针指来指去，一会儿就不知道指到哪里了。 所以，我们在写链表代码的时候，一定注意不要弄丢了指针。

指针往往是怎么弄丢的？这里举一个例子。

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

p.next = x;
x.next = p.next;

p.next = x;
x.next = p.next;

初学者经常会在儿犯错。p.next 指针在完成第一步操作之后，已经不再指向结点 b，而是指向结点 x。第二行代码相当于将 x 赋值给 x.next，即自己指向自己。因此，整个链表就断为两半，从结点 b 往后的所有结点都无法访问到了。

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

x.next = p.next;
p.next = x;

x.next = p.next;
p.next = x;

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

利用哨兵简化实现难度 ​

首先，我们来回顾一下单链表的插入和删除操作。如果我们在结点 p 后面插入一个新的结点，只需要下面两行代码就可以搞定。

new_node.next = p.next;
p.next = new_node;

new_node.next = p.next;
p.next = new_node;

但是，当我们向一个空链表中插入第一个结点，刚刚的逻辑就不能用。我们需要进行下面的特殊处理，其中 head 表示链表的头结点。 所以，从这段代码可以看出，对于单链表的插入操作，第一个结点和其它节点的插入逻辑是不同的。

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

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

再看下单链表结点的删除操作。如果要删除结点 p 的后继结点，只需要一行代码就可以搞定。

p.next = p.next.next;

p.next = p.next.next;

但是，如果我们要删除链表中的最后一个节点，前面的删除代码就不能工作。跟插入结点类似，我们也需要对这种情况单独处理。

if (head.next === null) {
  head = null;
}

if (head.next === null) {
  head = null;
}

综上所述，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且也容易因为考虑不全儿出错。那么如何解决这个问题？

那就要引出哨兵这个概念。哨兵，解决的是国家之前的边界问题。在链表中也是如此，这里说的哨兵也是解决 ”边界问题“ 的，不直接参与业务逻辑。

如果我们引入哨兵结点，在任何时候，不管链表是否为空，head 指针都会一直指向这个哨兵结点。我们把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表叫做不带头链表。

带头链表可以参考下图。哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点和插入其它结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑。

实际上，这种利用哨兵简化编程难度的技巧，在很多代码中实现中都有用到，比如插入排序、归并排序、动态规划等。

为了便于理解，再举一个非常简单的例子。

const str = '12345',
      len = str.length;

console.log(find(str, len, 3));

const str = '12345',
      len = str.length;

console.log(find(str, len, 3));

function find (str, n, key) {
  if (str === null || n <= 0) {
    return -1;
  }

  let i = 0;

  while (i < n) {
    if (str[i] == key) {
      return i;
    }
    i++;
  }

  return -1;
}

function find (str, n, key) {
  if (str === null || n <= 0) {
    return -1;
  }

  let i = 0;

  while (i < n) {
    if (str[i] == key) {
      return i;
    }
    i++;
  }

  return -1;
}

function find (str, n, key) {
  if (str === null || n <= 0) {
    return -1;
  }

  if (str[n - 1] == key) {
    return n - 1;
  }

  const temp = str[n - 1];

  str[n - 1] = key;

  let i = 0;

  while (str[i] != key) {
    i++;
  }

  str[n - 1] = temp;

  if (i == n - 1) {
    return -1;
  } else {
    return i;
  }
}

function find (str, n, key) {
  if (str === null || n <= 0) {
    return -1;
  }

  if (str[n - 1] == key) {
    return n - 1;
  }

  const temp = str[n - 1];

  str[n - 1] = key;

  let i = 0;

  while (str[i] != key) {
    i++;
  }

  str[n - 1] = temp;

  if (i == n - 1) {
    return -1;
  } else {
    return i;
  }
}

对比两段代码，在字符串 str 很长的时候，比如几万、几十万，你觉得哪段代码运行得更快？

答案是代码二，因为两段代码中执行次数最后就是 while 循环那一部分。第二段代码中，我们通过一个哨兵 a[n - 1] = key，成功省掉了一个比较语句 i < n，不要小看这一条语句，当累积执行万次、十几万次时，积累的时间就很明显了。

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

留意边界条件处理 ​

软件开发过程中，代码在一些边界或者异常情况下，最容易产生 Bug。链表代码也不例外。要实现没有 Bug 的链表代码，一定要在编写的过程中以及编写完成之后，检查边界条件是否考虑全面，以及代码在边界条件下是否能正常运行。

经常用来检查链表代码是否正确的边界条件如下：

• 链表为空的情况
• 链表只包含一个结点的情况
• 链表只包含两个结点的情况
• 代码逻辑处理头节点和尾结点的情况

当你写完链表代码之后，除了看下你写的代码在正常情况下能否工作，还要看在上面列举的几个边界条件下能否正确工作。 如果这些边界条件下都没有问题，那基本上可以认为没有问题。

当然，边界条件不止我列举的那些。针对不同的场景，还有特定的边界条件，这个需要你自己去思考。

实际上，不光是写链表代码，在写任何代码时，一定要多想想，可能会遇到哪些边界情况或者异常情况，这样写出来的代码才够健壮、

举例画图，辅助思考 ​

对于稍微复杂的链表操作，比如单链表反转，指针一会儿指这，一会儿指那，一会儿就被绕晕了。 所以这个时候就可以考虑使用举例法和画图法。

你可以找一个具体的例子，把它画在纸上，释放一些脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。 比如向单链表中插入一个数据，可以把各种情况都举一个例子，画出链表插入前和插入后的链表变化。

多写多练，没有捷径 ​

如果你已经理解并掌握前面所讲的方法，但是手写链表代码还是会出各种各样的错误，也不要着急。 把常见的链表操作都自己多写几遍，出问题就一点一点调试，熟能生巧。

常见的链表操作 ​

206：单链表反转 ​

141：链表中环的检测 ​

21：两个有序的链表合并 ​

19：删除链表倒数第 n 个结点 ​

876：求链表的中间节点 ​

总结 ​

写链表代码是最考验逻辑思维能力的。因为，链表代码到处都是指针的操作、边界条件的处理，稍有不慎就容易产生 Bug。 链表代码写的好坏，可以看出一个人写代码是否够细心，考虑问题是否全面，思维是否缜密。所以这也是很多面试官喜欢让人手写链表代码的原因。

技术拓展 ​

JS 实现单链表 ​

function Node (val) {
  this.val = val;
  this.next = null;
}

function LinkedList () {
  this.head = new Node('head');
}

LinkedList.prototype.find = function (val) {
  let currNode = this.head;
  
  while (currNode.val != val) {
    currNode = currNode.next;
  }

  return currNode;
}

LinkedList.prototype.insert = function (newVal, val) {
  const newNode = new Node(newVal);
  const current = this.find(val);
  newNode.next = current.next;
  current.next = newNode;
}

LinkedList.prototype.print = function () {
  let currNode = this.head;

  while (currNode.next != null) {
    console.log(currNode.next.val);
    currNode = currNode.next;
  }
}

LinkedList.prototype.findPrevious = function (val) {
  let currNode = this.head;

  while (currNode.next != null && currNode.next.val != val) {
    currNode = currNode.next;
  }

  return currNode;
}


LinkedList.prototype.remove = function (val) {
  const prevNode = this.findPrevious(val);

  if (prevNode.next != null) {
    prevNode.next = prevNode.next.next;
  }
}

module.exports = {
  LinkedList
}

function Node (val) {
  this.val = val;
  this.next = null;
}

function LinkedList () {
  this.head = new Node('head');
}

LinkedList.prototype.find = function (val) {
  let currNode = this.head;
  
  while (currNode.val != val) {
    currNode = currNode.next;
  }

  return currNode;
}

LinkedList.prototype.insert = function (newVal, val) {
  const newNode = new Node(newVal);
  const current = this.find(val);
  newNode.next = current.next;
  current.next = newNode;
}

LinkedList.prototype.print = function () {
  let currNode = this.head;

  while (currNode.next != null) {
    console.log(currNode.next.val);
    currNode = currNode.next;
  }
}

LinkedList.prototype.findPrevious = function (val) {
  let currNode = this.head;

  while (currNode.next != null && currNode.next.val != val) {
    currNode = currNode.next;
  }

  return currNode;
}


LinkedList.prototype.remove = function (val) {
  const prevNode = this.findPrevious(val);

  if (prevNode.next != null) {
    prevNode.next = prevNode.next.next;
  }
}

module.exports = {
  LinkedList
}

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

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

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

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

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

这样，我们就可以用链表实现一个 LRU 缓存，是不是很简单？

下面，我们来分析一下缓存访问的时间复杂度是多少。

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

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

vue 的 keep-alive 内置组件查找缓存也使用了 LRU 缓存算法，是基于数组和对象实现的。

单链表实现的字符串，判断是不是回文串 ​

可以使用快慢指针法。快指针每步两格走，到达链表末端时，慢指针刚到到达中心。

慢指针到达中心前，将走过的节点反向，在中心点开辟一个新的指针向回走，慢指针继续继续向前，慢指针扫完整个链表时，就可以判断这是回文串，否则就提前退出。总的时间复杂度为 O(n)，空间复杂度是 O(1)。

function Node (val) {
  this.val = val;
  this.next = null;
}

function LinkedList (values) {
  if (values) {
    this.head = new Node(values.shift());
    
    currNode = this.head;

    values.forEach(val => {
      currNode.next = new Node(val);
      currNode = currNode.next;
    });
  }
}

function Node (val) {
  this.val = val;
  this.next = null;
}

function LinkedList (values) {
  if (values) {
    this.head = new Node(values.shift());
    
    currNode = this.head;

    values.forEach(val => {
      currNode.next = new Node(val);
      currNode = currNode.next;
    });
  }
}

const list = new LinkedList(['a', 'b', 'c', 'c', 'b', 'a']);

const head = list.head;

console.log(isPalindrome(head));

function isPalindrome (head) {
  let slow = head,
      fast = head,
      prev = null;

  while (fast != null && fast.next != null) {
    fast = fast.next.next;

    const next = slow.next;

    slow.next = prev;
    prev = slow;
    slow = next;
  }

  if (fast != null) {
    slow = slow.next;
  }

  while (slow != null) {
    if (slow.val != prev.val) {
      return false;
    }

    slow = slow.next;
    prev = prev.next;
  }

  return true;
}

const list = new LinkedList(['a', 'b', 'c', 'c', 'b', 'a']);

const head = list.head;

console.log(isPalindrome(head));

function isPalindrome (head) {
  let slow = head,
      fast = head,
      prev = null;

  while (fast != null && fast.next != null) {
    fast = fast.next.next;

    const next = slow.next;

    slow.next = prev;
    prev = slow;
    slow = next;
  }

  if (fast != null) {
    slow = slow.next;
  }

  while (slow != null) {
    if (slow.val != prev.val) {
      return false;
    }

    slow = slow.next;
    prev = prev.next;
  }

  return true;
}

哨兵是否还有其他应用场景 ​

。。。

三、栈 ​

浏览器的前进、后退功能，我想你肯定很熟悉。

当你依次访问完一串页面 a-b-c 之后，点击浏览器的回退按钮，就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a，点击前进按钮，就可以重新查看页面 b 和 c。但是，如果你会回退到页面 b 之后，点击了新的页面 d，那就无法再通过前进、后退功能查看页面 c 了。

假设你是 Chrome 浏览器的开发工程师，你会如何实现这个功能？其实这就需要用到我们今天要将的 ”栈“ 这种数据结构。

栈是什么 ​

关于 ”栈“，有个很贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放，取得时候，也是从上往下一个一个地依次取，不能从中间任意抽出。后进先出，先进后出，这就是典型的 ”栈“ 结构。

栈是一种 ”操作受限“ 的线性表，只允许在一端插入和删除数据。从功能上说，数组和链表确实可以替代栈，但是特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

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

如何实现一个栈 ​

栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。

实际上，栈既可以用数组实现，也可以用链表实现。用数组实现的栈，就做顺序栈，用链表实现的栈，就做链式栈。

这里实现一个基于数组的顺序栈。

class ArrayStack {
  items;
  count;
  n;

  constructor (n) {
    this.items = new Array(n);
    this.n = n;
    this.count = 0;
  }

  push (item) {
    if (this.count == this.n) return false;

    this.items[this.count] = item;
    this.count++;

    return true;
  }

  pop () {
    if (this.count == 0) return null;

    const tmp = this.items[this.count - 1];
    this.count--;

    return tmp;
  }
}

class ArrayStack {
  items;
  count;
  n;

  constructor (n) {
    this.items = new Array(n);
    this.n = n;
    this.count = 0;
  }

  push (item) {
    if (this.count == this.n) return false;

    this.items[this.count] = item;
    this.count++;

    return true;
  }

  pop () {
    if (this.count == 0) return null;

    const tmp = this.items[this.count - 1];
    this.count--;

    return tmp;
  }
}

了解了定义和基本操作，那它的操作时间和空间复杂度是多少？

不管是顺序栈还是链式栈，我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

注意，这里存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以，我们在说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。

支持动态扩容的顺序栈 ​

之前的基于数组实现的栈，是一个固定大小的栈，也就是说，在初始化栈时需要事先指定栈的大小。当栈满之后，就无法向栈里添加数据了。尽管链式栈的大小不受限，但也要存储 next 指针，内存消耗相对较多。是否能基于数组实现一个可以支持动态扩容的栈？

在之前的数组那一节，已经说过实现动态扩容的数组思路。当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据统统拷贝过去。这样就实现了一个支持动态扩容的数组。

所以，要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就可以。当栈满之后，就申请一个更大的数组，将原来的数据搬移到新数组中。

实际上，支持动态扩容的栈，在平时开发中并不常用到。说这块的目的，主要是希望练习一下前面讲的复杂度分析方法。 你不用死记硬背入栈、出栈的时间复杂度，你需要掌握的是分析方法。能够自己分析才算是真正掌握。

对于出栈操作来说，我们不会涉及内存的重新申请和数据搬移，所以出栈的时间复杂度仍然是 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)。

栈在函数调用中的应用 ​

前面讲的都偏理论一些，现在来看下，栈在软件工程中的实际应用。栈作为一个比较基础的数据结构，应用场景还是蛮多的。其中，一个比较经典的应用场景是函数调用栈。

我们知道，操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成 “栈” 这种结构，用来存储函数调用时的临时变量。 每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

栈在表达式取值中的应用 ​

栈的另一个常见的应用场景，编译器如何利用栈来实现表达式求值。

为了方便解释，我们可以将算数表达式简化为只包含加减乘除四则运算，比如 34 + 13 * 9 + 44 - 12/3 。对于这个四则运算，人脑可以很快求解出答案，但是对于计算机来说，理解这个表达式本身就是一个很难的事。如果换做你，让你实现这样一个表达式求值的功能，你会怎么做？

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

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

下面是 3 + 5 * 8 - 6 这个表达式的计算过程中的图，你可以结合图和思考上述过程。

这样用两个栈来解决的思路是不是非常巧妙？你有没有想到？

栈在括号匹配中的应用 ​

除了用栈来实现表达式求值，我们还可以借助栈来检查表达式中的括号是否匹配。

假设表达式中只包含三种括号，()、[]、{}，并且它们可以任意嵌套。如果给你一个包含三种符号的表达式字符串，应该如何检查它是否合法？

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

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

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

实现浏览器的前进、后退功能，用两个栈就可以非常完美解决。

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

图示中左边为栈 X，右边为栈 Y。

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

当你通过浏览器的回退按钮，从页面 c 后退到页面 a 之后，我们就依次把 c 和 b 从栈 X 中弹出，并且依次放入到栈 Y。

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

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

总结 ​

栈是一种操作受限的数据结构，只支持入栈和出栈操作。后进先出是它最大的特点。栈既可以通过数组实现，也可以通过链表实现。不管是基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。除此之外，还讲了一种支持动态扩容的顺序栈，你需要掌握它的均摊时间复杂度分析方法。

技术拓展 ​

为什么函数调用栈要有 ”栈“ 来保存临时变量 ​

其实，我们不一定要用栈保存临时变量，只不过如果这个函数调用符合后进先出的特性，用栈中这种数据结构实现，是顺理成章的选择。

从调用函数进入被调用函数，对于数据来说，变化的是作用域。只要能保证每进入一个新的函数，都是一个新的作用域就可以。要实现这个需求，用栈就非常方便。进入被调用函数的时候，分配一段栈空间给这个函数的变量，在函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。

JVM 内存管理中的 ”堆栈“ ​

。。。

四、队列 ​

我们知道，CPU 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。

当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源，这个时候线程池该如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现？

实际上，这些问题并不复杂，其底层的数据结构就是我们今天要学的内容，队列（queue）。

如何理解队列 ​

队列的概念很好理解。你可以将其想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进先出，就是典型的 ”队列“。

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

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

队列的概念很好理解，基本操作也很容易。作为一种非常基础的数据结构，队列的应用也很广泛，特别是一些具有某些额外特性的队列。 比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着很关键的作用。比如高性能队列 Disrupter、Linux 环形缓存，都用到了循环并发队列。还有 Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁。

顺序队列和链式队列 ​

队列跟栈一样，也是一种抽象的数据结构。它具有先进先出的特性，支持在队尾插入元素，在队头删除元素，那么该如何实现一个队列？

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

来看下基于数组的实现方法。

class ArrayQueue {
  items = null;
  n = 0;
  head = 0;
  tail = 0;

  constructor (capacity) {
    this.items = new Array(capacity);
    this.n = capacity;
  }

  enqueue (item) {
    if (this.tail === this.n) return false;

    this.items[this.tail] = item;
    this.tail++;

    return true;
  }

  dequeue () {
    if (this.head === this.tail) return null;

    const ret = this.items[this.head];
    this.head++;

    return ret;
  }
}

class ArrayQueue {
  items = null;
  n = 0;
  head = 0;
  tail = 0;

  constructor (capacity) {
    this.items = new Array(capacity);
    this.n = capacity;
  }

  enqueue (item) {
    if (this.tail === this.n) return false;

    this.items[this.tail] = item;
    this.tail++;

    return true;
  }

  dequeue () {
    if (this.head === this.tail) return null;

    const ret = this.items[this.head];
    this.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)。能不能针对这个现象优化下？

实际上，我们在出队时可以不同搬移数据。如果没有空闲空间，只需要在入队时，再集中触发一次数据的搬移操作。借助这个思想，出队函数 dequeue() 保持不变，我们可以改造一下 enqueue()，就可以轻松解决刚才的问题。

class ArrayQueue {
  items = null;
  n = 0;
  head = 0;
  tail = 0;

  constructor (capacity) {
    this.items = new Array(capacity);
    this.n = capacity;
  }

  enqueue (item) {
    if (this.tail === this.n) {
      if (this.head === 0) return false;

      for (let i = this.head; i < this.tail; i++) {
        this.items[ i - this.head] = this.items[i];
      }

      this.tail -= this.head;
      this.head = 0;
    };

    this.items[this.tail] = item;
    this.tail++;

    return true;
  }

  dequeue () {
    if (this.head === this.tail) return null;

    const ret = this.items[this.head];
    this.head++;

    return ret;
  }
}

class ArrayQueue {
  items = null;
  n = 0;
  head = 0;
  tail = 0;

  constructor (capacity) {
    this.items = new Array(capacity);
    this.n = capacity;
  }

  enqueue (item) {
    if (this.tail === this.n) {
      if (this.head === 0) return false;

      for (let i = this.head; i < this.tail; i++) {
        this.items[ i - this.head] = this.items[i];
      }

      this.tail -= this.head;
      this.head = 0;
    };

    this.items[this.tail] = item;
    this.tail++;

    return true;
  }

  dequeue () {
    if (this.head === this.tail) return null;

    const ret = this.items[this.head];
    this.head++;

    return ret;
  }
}

从代码中我们可以看到，当队列的 tail 指针移动到数组的最右边后，如果有新的数据入队，我们可以将 head 到 tail 之间的数据，整体搬移到数组 0 到 tail-head 的位置。

这种实现思路中，出队操作的时间复杂度仍然是 O(1)，但入队操作的时间复杂度还是 O(1)。接下来，看下基于链表的队列实现。

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

循环队列 ​

我们用数组实现队列时，在 tail = n 时，会有数据搬移操作，这样入队操作性能就会受到影响。你有没有办法能够避免数据搬移？

我们来看看循环队列的思路。循环队列，顾名思义，它长的像一个环。原本数组是有头有尾的，是一条直线。现在我们将其首尾相连，就成为一个环。

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

通过这样的方法，就可以避免数据搬移操作。看起来不难理解，但是循环队列的代码实现难度要比前面的非循环队列难很多。要想写出没有 bug 的循环队列的实现代码，最关键的是，确认好队空和队满的判定条件。

在用数组实现的非循环队列中，队满的判断条件是 tail === n，队空的判断条件是 head == tail。针对循环队列，如何判断队空和队满？

队列为空的判断条件仍然是 head === tail。但队列满的条件就有点复杂。下面有张队列满的图，你也可以看下，总结一下规律。

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

在一般情况下，我们可以看出来，当队列满时，tail + 1 = head。但是，有个特殊情况，当tail = n - 1，而 head = 0时，这时候，tail + 1 = n，而 head = 0，所以使用 (tail + 1) % n的值，通过对 n 取余，才能得到 head 的真实值。而且，tail + 1 最大的情况就是 n ，不会大于 n，这样，tail+1 除了最大情况，不然怎么余 n 都是 tail + 1 本身，也就是 head。所以，正确的队满判断公式就是：（tail + 1）% n = head。

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

class CircularQueue {
  items = null;
  n = 0;
  head = 0;
  tail = 0;

  constructor (capacity) {
    this.items = new Array(capacity);
    this.n = capacity;
  }

  enqueue (item) {
    if ((this.tail + 1) % this.n === this.head) return false;

    this.items[this.tail] = item;
    this.tail = (this.tail + 1) % this.n;

    return true;
  }

  dequeue () {
    if (this.head === this.tail) return null;

    const ret = this.items[this.head];
    this.head = (this.head + 1) % this.n;

    return ret;
  }
}

class CircularQueue {
  items = null;
  n = 0;
  head = 0;
  tail = 0;

  constructor (capacity) {
    this.items = new Array(capacity);
    this.n = capacity;
  }

  enqueue (item) {
    if ((this.tail + 1) % this.n === this.head) return false;

    this.items[this.tail] = item;
    this.tail = (this.tail + 1) % this.n;

    return true;
  }

  dequeue () {
    if (this.head === this.tail) return null;

    const ret = this.items[this.head];
    this.head = (this.head + 1) % this.n;

    return ret;
  }
}

循环队列和并发队列 ​

前面说的内容理论比较多，看起来很难与实际的项目开发扯上关系。确实，队列这种数据结构很基础，平时的业务开发也不大可能从零实现一个队列，甚至都不会直接用到。而有一些特殊特性的队列应用比较广泛，比如阻塞队列和并发队列。

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，当队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已满，那么插入数据就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

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

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

在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，那么如何实现一个线程安全的队列呢？

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

总结 ​

队列的最大特点就是先进先出，主要的两个操作是入队和出队。和栈一样，它既可以用数组来实现，也可以用链表实现。用数组实现的叫顺序队列，用链表实现的叫链式队列。数组实现队列时，会有数据搬移操作，要想解决此问题，我们可以基于数组实现循环队列。

循环队列是重点。要想写出没有 bug 的循环队列实现代码，关键要确定好队空和队满的判断条件，具体的代码要自己能写出来。

除此之外，还分享了几种高级队列结构，阻塞队列、并发队列（底层还是队列，在之上附加了很多其他功能）。 阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全。

技术拓展 ​

线程池无空闲空间问题 ​

线程池没有空闲空间时，新的任务请求线程资源时，线程池该如何处理？各种处理策略是如何实现的？

针对这种情况。第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。那如何存储排队请求？

我们希望公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求。之前我们说过，队列基于链表和数据有两种实现方式。那么这两种实现方式对于排队请求有什么区别？

基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的

基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对于响应时间敏感的系统来说，相对比较合理。不过，设置一个合理的队列大小，也是非常讲究的。队列太大导致等待请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

除了前面讲到队列应用在线程池请求排队的场景之外，队列还可以应用在任何有限资源池中，用于排队请求，比如数据库连接池。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过 “队列” 这种数据结构来实现请求排队。

队列排队请求的应用场景 ​

• 分布式锁中的消息队列 kafka
• sockets 网络连接队列
• 数据库连接队列

如何实现无锁并发队列 ​

CAS 实现无锁队列。

入队前，获取 tail 位置。入队时比较 tail 是否发生变化，如果否，允许入队；反之，入队失败。

出队则获取 head 位置，进行 CAS。

CAS（Compare and Swap），比较再交换。

CAS 是一种无锁算法，CAS 有 3 个操作数，内存值 V，旧的预期值 A，要修改的新值 B。当且仅当预期值 A 和 内存值 V 相同时，将内存值 V 修改为 B，否则什么都不做。

五、递归 ​

邀请好友返红包这个功能想必你应该并不陌生吧？现在很多 App 都有这个功能。这个功能中，用户 A 邀请 用户 B 来注册，用户 B 又邀请了用户 C 来注册。我们可以说，用户 C 的 “最终邀请人” 是用户 A，用户 B 的 “最终邀请人” 也是用户 A，而用户 A 没有 “最终邀请人”。

一般来说，我们会通过数据库来记录这种推荐关系。在数据库表中，我们可以记录两行数据，其中 actor_id 表示用户 id，invite_id 表示邀请人 id。

基于这个背景，我们可以提出一个问题，给定一个用户 ID，如何查找这个用户的 “最终邀请人”。带着这个问题，我们来学习今天的内容，递归（Recursion）。

递归是什么 ​

递归是一种应用非常广泛的算法（编程技巧）。很多数据结构与算法的编程实现都会用到递归，比如 DFS 深度优先搜索、前中后序二叉树遍历等等。所以，搞懂递归非常重要，否则，后面复杂一些的数据结构和算法学起来就会比较吃力。

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

递归需要满足三个条件 ​

递归究竟可以解决什么样的问题？通常情况下，只要同时满足以下三个条件，就可以用递归来解决。

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

何为子问题？子问题就是数据规模更小的问题。

这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样

存在递归终止条件

把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。

如何编写递归代码 ​

编写递归代码最关键的就是写出递归公式，找到终止条件，剩下将递归公式转换为代码就很简单了。

首先你要记住这个理论。然后可以根据下面的例子，帮助理解。

假如这里有 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(n) = f(n - 1) + f(n - 2);

有了递归公式，递归代码基本就完成一半。我们再来看下终止条件。当有一个台阶时，我们不需要递归，就只有一种走法。所以 f(1) = 1。这个递归条件并不够，我们还可以用 n = 1, n = 3 这样比较小的数试一下。

n = 2 时，f(2) = f(1) + f(0)。如果递归条件只有一个 f(1) = 1，那 f(2) 就无法求解了。所以除了 f(1) = 1 这个递归条件外，还要有 f(0) = 1，表示走 0 个台阶有一种走法，不过这样子看起来就不符合正常的逻辑思维。所以，我们可以把 f(2) = 2 作为一种终止条件，表示走 2 个台阶，有两种走法，一步走完或者分两步来走。

所以，递归终止条件就是 f(1) = 1，f(2) = 2。这个时候，你可以拿 n = 1，n = 4 来验证这个终止条件是否足够并且正确。

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

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

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

有了这个公式，转换为递归代码就简单多了。最终的递归代码如下：

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

function f (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 两层之间的关系即可，不需要一层一层往下思考与子问题之间的关系。屏蔽掉细节，理解起来就简单多了。

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

警惕堆栈溢出 ​

在实际的项目开发中，编写递归代码时，可能会遇到很多问题，比如堆栈溢出。堆栈溢出会导致系统性崩溃，后果非常严重。为什么递归代码容易造成堆栈溢出？该如何预防堆栈溢出？

函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完毕返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层级很深，一直入栈，就会有堆栈溢出的风险。

那么，如何避免堆栈溢出？

我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。但这种做法并不能完全解决问题，因为允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用。

警惕重复计算 ​

使用递归时还会出现重复计算的问题。下图是刚才递归代码例子的递归过程。

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

为了避免重复计算，我们可以通过一个数据结构（散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚才讲的问题。

const cache = new Map();

function f (n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  
  if (cache.has(n)) {
    return cache.get(n);
  }

  const ret = f(n - 1) + f(n - 2);
  cache.set(n, ret);
  
  return ret;
}

const cache = new Map();

function f (n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  
  if (cache.has(n)) {
    return cache.get(n);
  }

  const ret = f(n - 1) + f(n - 2);
  cache.set(n, ret);
  
  return ret;
}

除了堆栈溢出、重复计算这两个常见的问题。递归代码还有很多别的问题。

在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本。在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销。

如何把递归代码改写为非递归代码 ​

刚才我们说了，递归有利有弊。利是递归代码的表达力很强，写起来非常简洁；弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况选择是否需要用递归的方式来实现。

我们是否可以把递归代码改为非递归代码？刚才的例子就可以改为非递归代码。

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

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

是不是所有的递归代码都可以改为这种迭代循环的非递归写法？

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

但是这种思路实际上是将递归改为 “手动” 递归，本质并没有变，而且也没有解决前面讲的问题，还增加了复杂度。

总结 ​

递归是一种非常高效、简洁的编程技巧。只要满足 “三个条件” 的问题就可以通过递归代码来解决。

不过递归代码也比较难写、难理解。编写递归代码的关键就是不要把自己绕进去，正确姿势是写出递归公式，找出终止条件，然后再翻译成代码。

递归代码虽然简单高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所以，在编写递归代码的时候，一定要控制好这些副作用。

技术拓展 ​

最终邀请人 ​

寻找最终邀请人，大概代码如下：

function findRootInviteId (actorId) {
  const inviteId = select invite_id from [table] where actor_id = actorId;
  if (inviteId == null) return actorId;
  return findRootInviteId(inviteId);
}

function findRootInviteId (actorId) {
  const inviteId = select invite_id from [table] where actor_id = actorId;
  if (inviteId == null) return actorId;
  return findRootInviteId(inviteId);
}

是不是非常简洁明了，三行代码就可以搞定。但是实际项目中，上面的代码并不能工作。

第一，如果递归很深，可能存在堆栈溢出的问题。

第二，如果数据库里存在脏数据，还需要处理由此产生的无限递归问题。

第一个问题可以用限制递归深度来解决，第二个也可以用限制递归深度来解决。不过，还有一个更高级的处理方法，就是自动检测 “环” 的存在（双指针解法）。除此之外还可以通过散列表缓存已经存在的值，如果发现重复值，表示已经存在环。

递归代码如何调试 ​

打印日志发现，递归值。

结合条件断点进行调试。

六、排序 ​

排序对于任何一个程序员来说，可能都不陌生。你学习的第一个算法，可能就是排序。大部分编程语言中，也都提供了排序函数。在平常的项目中，我们也经常会用到排序。排序非常重要，所以值得我们花费时间去研究。

排序算法有很多，有些可能你连名字都没有听过，比如猴子排序、睡眠排序、面条排序等。当然，这篇文章也只介绍一些经典的排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。按照时间复杂度可以把他们分为三类。

带着问题去学习，是最有效的学习方法。有这样一个问题：插入排序和冒泡排序的时间复杂度相同，都是 $O(n^2)$，在实际的开发中，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法？

如何分析一个排序算法？ ​

学习排序算法，除了学习它的算法原理、代码实现之外，更重要的是要学会如何评价、分析一个排序算法。分析一个排序算法，可以从下面几个方面入手。

排序算法的执行效率 ​

对于排序算法执行效率的分析，一般会从这几个方面来衡量：

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。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫做稳定的排序算法；如果前端顺序发生变化，那对应的排序算法就叫做不稳定的排序算法。

你可能会问，两个 3 哪个在前，那个在后有什么关系，稳不稳定又有什么关系？为什么要注意排序算法的稳定性？

很多数据结构和算法的课程，在讲排序的时候，都是用整数举例，但在真正的软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个 key 来排序。

比如，我们要给电商交易系统中的 “订单” 排序。订单有两个属性，一个是下单时间，一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们应该怎么来做？

最先想到的方法就是先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来并不难，但是实现起来会很复杂。

借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样：先按照下单时间给订单排序，排序完成后使用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单也是按照下单时间从早到晚排序的。

稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一个排序之后，所有的订单按照下单时间从早到晚有序了。第二次排序中，我们使用的是稳定排序算法，所以经过二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。

冒泡排序（Bubble Sort） ​

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

我们用一个例子来看下冒泡排序的整个过程。我们要对一组数据 4，5，6，3，2，1，从小到大进行排序。

第一次冒泡操作的详细过程如下：

4 5 6 3 2 1
4 5 6 3 2 1
4 5 6 3 2 1
4 5 3 6 2 1
4 5 3 2 6 1
4 5 3 2 1 6

4 5 6 3 2 1
4 5 6 3 2 1
4 5 6 3 2 1
4 5 3 6 2 1
4 5 3 2 6 1
4 5 3 2 1 6

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

实际上，上面的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

冒泡排序算法的原理比较容易理解，具体代码如下：

function bubbleSort (arr, n) {
  if (n <= 1) return;

  for (let i = 0; i < n; i++) {
    let flag = false;

    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const tmp = arr[j];

        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;

        flag = true;
      }
    }

    if (!flag) break;
  }
}

function bubbleSort (arr, n) {
  if (n <= 1) return;

  for (let i = 0; i < n; i++) {
    let flag = false;

    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const tmp = arr[j];

        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;

        flag = true;
      }
    }

    if (!flag) break;
  }
}

结合刚才分析排序算法的三个方面，如下分析：

1. 冒泡排序是原地排序算法。

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的时间复杂度为 O(1)，是一个原地排序算法。

2. 冒泡排序是稳定排序算法。

冒泡排序中，只要交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

3. 冒泡排序的时间复杂度。

最好情况下，要排序的数据已经是有序了，我们只需要进行一次冒泡操作，就可以结束，所以最好情况时间复杂度是 O(n)。 最坏情况是，要排序的数据刚好是倒序排列，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度是 $O(n^2)$。

最好、最坏情况下的时间复杂度很容易分析，那平均情况下的时间复杂度是多少？平均时间复杂度就是加权平均期望时间复杂度，分析的时候要结合概率论的知识。

对于包含 n 个数据的数组，这 n 个数据就是 n! 种排列方式。不同的排列方式，冒泡排序执行的时间肯定是不同的。比如我们前面的例子，其中一个要进行 6 次冒泡，而另一个只需要四次。如果用概率论方法定量分析平均时间复杂度，涉及的数学推理和计算就会很复杂。这里其实还有一种思路，就是通过 “有序度” 和 "逆序度" 这两个概念来进行分析。

有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样：

有序元素对：a[i] <= a[j], 如果 i < j。

有序元素对：a[i] <= a[j], 如果 i < j。

比如 2, 4, 3, 1, 5, 6 这组数据的有序度为 11，因为其有序元素对有 11 个，分别是：

(2, 4)、(2, 3)、(2, 5)、(2, 6)
(4, 5)、(4, 6)、(3, 5)、(3, 6)
(1, 5)、(1, 6)、(5, 6)

(2, 4)、(2, 3)、(2, 5)、(2, 6)
(4, 5)、(4, 6)、(3, 5)、(3, 6)
(1, 5)、(1, 6)、(5, 6)

同理，对于一个倒序排列数组，比如 6，5，4，3，2， 1，有序度为 0；对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n * (n - 1) / 2，也就是 15。我们把这种完全有序的数组的有序度叫做满有序度。

等差数列公式 ：首项加末项的和乘项数除以二 ，这里的项数是n，首项是n-1,末项是0，所以：n(n+1+0)/2

逆序度的定义正好跟有序度相反（默认从大到小为有序）。

有序元素对：a[i] > a[j], 如果 i < j。

有序元素对：a[i] > a[j], 如果 i < j。

关于这三个概念，我们还可以得到一个公式：逆序度 = 满有序度 - 有序度。我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。

还是拿前面的例子来说明。要排序的数组的初始状态是 4，5，6，3，2，1，其中，有序元素对有 (4, 5)、(4, 6)、(5, 6) ，所以有序度是 3。 n = 6，所以排序完成之后终态的有序度为 n * (n - 1) / 2 = 15。

冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是 n * (n - 1) / 2 - 初始有序度。此例中就是 15 - 3 = 12，要进行 12 次交换操作。

对于包含 n 个数据的数组进行冒泡排序，平均次数是多少？最坏情况下，初始状态的有序度为 0，所以要进行 n * (n - 1) / 2 次交换。最好情况下，初始状态的有序度是 n * (n - 1) / 2，就不需要进行交换。我们可以取个中间值 n * (n - 1) / 4，来表示初始有序度既不是很高也不是很低的平均情况。

换句话来说，平均情况下，需要 n * (n - 1) / 4 次交换操作，比较操作肯定比交换操作多，而复杂度的上限是 $O(n^2)$，所以平均情况下的时间复杂度就是 $O(n^2)$。

夹挤定理，又称夹逼定理、三明治定理，是有关函数极限的定理。它指出若有两个函数在某点的极限相同，且有第三个函数的值在这两个函数之间，则第三个函数在该点的极限也相同。

插入排序（Insertion Sort） ​

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

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

插入排序是如何借助上面的思想来实现排序？

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

如果所示，要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素往后移动一位，这样才能空出位置给元素 a 插入。

对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。

为什么说移动次数等于逆序度？下面有个图，你一看你明白。首先满序度是 n * (n - 1) / 2 = 15，初始序列的有序度是 5，所以逆序度是 10。插入排序中，数据移动的个数总和也等于 10 = 3 + 3 + 4。

插入排序的原理也很简单，下面是代码实现。

function insertionSort (arr, n) {
  if (n <= 1) return;

  for (let i = 1; i < n; i++) {
    const tmp = arr[i];
    
    let j = i - 1;

    for (; j >= 0; j--) {
      if (arr[j] > tmp) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }

    arr[j + 1] = tmp;
  }
}

function insertionSort (arr, n) {
  if (n <= 1) return;

  for (let i = 1; i < n; i++) {
    const tmp = arr[i];
    
    let j = i - 1;

    for (; j >= 0; j--) {
      if (arr[j] > tmp) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }

    arr[j + 1] = tmp;
  }
}

现在，我们再来深入分析插入排序算法。

1. 插入排序是原地排序算法。

从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。

2. 插入排序是稳定排序算法。

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

3. 插入排序的时间复杂度。

如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数组里面查找元素位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好时间复杂度是 O(n)。注意，这里是从尾到头遍历已经有序的数据。

如果数据是倒序的，每次插入都相当于在数据的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 $O(n^2)$。

在数组中插入一个数据的平均时间复杂度是 O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 $O(n^2)$。

选择排序（Selection Sort） ​

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

选择排序代码实现：

function selectionSort (arr, n) {
  if (n <= 1) return;

  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;

    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }

    const tmp = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = tmp;
  }

}

function selectionSort (arr, n) {
  if (n <= 1) return;

  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;

    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }

    const tmp = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = tmp;
  }

}

同样，这里也对选择排序算法进行分析。

1. 选择排序是原地排序算法。

选择排序空间复杂度为 O(1)，是一种原地排序算法。

2. 选择排序不是稳定排序算法。

选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样就破坏了稳定性。

比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 的顺序就变了，所以就不稳定了。正因如此，相对于冒泡排序和插入排序，选择排序就稍微逊色。

3. 选择排序的时间复杂度。

选择排序的最好情况时间复杂度、最坏情况和平均时间复杂度都为 $O(n^2)$。

不管原来的顺序是什么，都要从无序数组中找到最小值，而最小值只能通过全部比较一次才能得到。

归并排序（Merge Sort） ​

前面介绍了冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是 $O(n^2)$，比较高，适合小规模数据的排序。接下来介绍两种时间复杂度为 $O(nlogn)$ 的排序算法，归并排序和快速排序。这两种排序算法适合大规模的数据排序，比之前介绍的三种排序算法更常用。

归并排序和快速排序都用到了分治思想，非常巧妙。我们可以借鉴这个思想，来解决非排序的问题，比如如何在 $O(n)$ 的时间复杂度内查找一个无序数组中的第 K 大元素？

原理 ​

归并排序的核心思想很简单。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就有序了。

归并排序使用的是分治思想。分治，即分而治之，就是将一个大问题分解为小的问题来解决。小的问题解决了，大问题就解决了。

从刚才的描述中，你有没有感觉到，分治思想跟我们前面讲的递归思想很像。的确是这样，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。

那么归并排序是如何使用递归代码来实现的？

我们知道编写递归代码的技巧就是，分析出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。所以，要想写出递归排序的代码，我们要先写出归并排序的递推公式。

// 递推公式
merge_sort(p ... r) = merge(merge_sort(p ... q), merge_sort(q + 1 ... r));

// 终止条件（不需要再分解）：
p >= r

// 递推公式
merge_sort(p ... r) = merge(merge_sort(p ... q), merge_sort(q + 1 ... r));

// 终止条件（不需要再分解）：
p >= r