算法+数据结构=程序，今天就来说说递归+排序+查找，再加上树与图

著名数据专家沃斯曾说：算法+数据结构=程序

上次讲了数据结构

这回就讲讲算法

复杂度

复杂度分析，是贯彻数据结构和算法中的一项基础技能，学习数据结构和算法的目的，无非就是要写出占用空间更小、运行时间更短的代码。

时间复杂度

1. 大O表示法： T(n) = O(f(n))

• 表示代码执行时间随数据规模增长的 变化趋势（注意只是表示「变化趋势」）
• 由于只是表示变化趋势，一般计算复杂度时，会忽略低阶、常量、系数

1. 几种常见的时间复杂度量级：
   
   

   image.png

多项式量级：

• 常数阶 O(1)
• 对数阶 O(logn)
• 线性阶 O(n)
• 线性对数阶 O(nlogn)
• 平方阶 O(n²) O(n³) ... O(n^k)

非多项式量级：(n越多，执行时间急剧上升，性能低)

• 指数阶 O(2^n)
• 阶乘阶 O(n!)

1. 加法法则和乘法法则

• 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

1. 平均时间复杂度：

• 也叫加权平均时间复杂度或者期望时间复杂度。
• 要会计算：最好、最坏、平均时间

1. 均摊时间复杂度

• 特殊的平均时间复杂度
• 相当于算法有规律可循，计算时间时，可以把一次耗时多的操纵的时间，均摊给多次耗时少的操纵。

算法

1. 递归

可以用递归的条件：

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

写递归算法的思路：

1. 归纳出递归表达式
2. 寻找终止条件

递归代码的弊端：

1. 堆栈溢出
2. 可能会重复计算
3. 函数调用耗时多
4. 空间复杂度高

2. 排序

衡量排序算法好坏的三要素：

1. 执行效率

• 最好时间复杂度
• 最坏时间复杂度
• 平均时间复杂度
• 时间复杂度的系数、常数 、低阶（因为排序的数据规模一般不会非常大）
• 比较、交换的次数

1. 额外内存消耗（内存消耗为O(1)的称为原地排序）
2. 稳定性，是否是稳定排序（即如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变）

按时间复杂度分类：

1. O(n²)： 冒泡排序、插入排序、选择排序
2. O(nlogn)：归并排序、快速排序
3. O(n) ：桶排序、计数排序、基数排序 （条件苛刻，适用于部分场景）

2.1 冒泡排序

原理： 从下往上，逐次比较两个相邻的数据，如果下面的数据比上面的数据大，则把这两个数据的位置互换。

image.png

image.png

• 最好时间复杂度 O(n)
• 最坏时间复杂度 O(n^2)
• 平均时间复杂度 O(n^2)
• 原地排序、稳定排序

2.2 插入排序

原理： 分为已排区域和未排区域，每次拿未排区域中的第一个数，插入到已排区域中正确的位置。

image.png

• 最好时间复杂度 O(n)
• 最坏时间复杂度 O(n^2)
• 平均时间复杂度 O(n^2)
• 原地排序、稳定排序

2.3 选择排序

原理： 分为已排区域和未排区域，每次从未排区域中选取最小的数，放到已排区域的最后面。

image.png

• 最好时间复杂度 O(n^2)
• 最坏时间复杂度 O(n^2)
• 平均时间复杂度 O(n^2)
• 原地排序、 非稳定的排序算法
• 一般都不考虑用该算法。

2.4 归并排序

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

image.png

• 非原地排序，空间复杂度为O(n)
• 稳定排序
• 利用分治递归思想
• 递推公式：  merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
• 最好、最坏、平均时间复杂度都是 O(nlogn)
  
  

  image.png

2.5 快速排序

image.png

image.png

• 原地排序
• 非稳定排序
• 递推公式：  quick_sort(p…r) = partition(p…r) + quick_sort(p…q-1) + quick_sort(q+1, r)
• 最好时间复杂度: O(nlogn)
• 最坏时间复杂度: O(n^2) （极小几率出现）
• 平均时间复杂度: O(nlogn)

2.6 桶排序

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

image.png

桶排序的时间复杂度为什么是 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)。

苛刻的条件：

1. 要排序的数据需要很容易就能划分成 m 个桶
2. 桶与桶之间有着天然的大小顺序
3. 数据在各个桶之间的分布是比较均匀的

2.7 计数排序

计数排序其实是桶排序的一种特殊情况： 数据的访问很小（例如年龄、考生的成绩），桶的数量是有限的。 以给高考考生成绩进行排名为例，考生的满分是 900 分，最小是 0 分，对应901个桶，把全国的考生放入这901个桶，桶内的数据都是分数相同的考生，所以并不需要再进行排序。

特殊要求：

1. 只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了
2. 计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。如果要排序的数据中有负数，数据的范围是 [-1000, 1000]，那我们就需要先对每个数据都加 1000，转化成非负整数。如果考生成绩精确到小数后一位，我们就需要将所有的分数都先乘以 10，转化成整数。

2.8 基数排序

我们再来看这样一个排序问题。假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？

我们之前讲的快排，时间复杂度可以做到 O(nlogn)，还有更高效的排序算法吗？桶排序、计数排序能派上用场吗？手机号码有 11 位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是 O(n) 的算法呢？现在我就来介绍一种新的排序算法，基数排序。

刚刚这个问题里有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。

借助稳定排序算法，这里有一个巧妙的实现思路。还记得我们第 11 节中，在阐述排序算法的稳定性的时候举的订单的例子吗？我们这里也可以借助相同的处理思路，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。

手机号码稍微有点长，画图比较不容易看清楚，我用字符串排序的例子，画了一张基数排序的过程分解图，你可以看下。

image.png

注意，这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。

根据每一位来排序，我们可以用刚讲过的桶排序或者计数排序，它们的时间复杂度可以做到 O(n)。如果要排序的数据有 k 位，那我们就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k*n)。当 k 不大的时候，比如手机号码排序的例子，k 最大就是 11，所以基数排序的时间复杂度就近似于 O(n)。

实际上，有时候要排序的数据并不都是等长的，比如我们排序牛津字典中的 20 万个英文单词，最短的只有 1 个字母，最长的我特意去 查了下，有 45 个字母，中文翻译是尘肺病。对于这种不等长的数据，基数排序还适用吗？

实际上，我们可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据ASCII 值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了。

我来总结一下，基数排序对要排序的数据是有要求的：

1. 需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了
2. 除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

3. 查找

3.1 二分查找法

1. 依赖于数组结构（数据量太大不适合用二分查找法，数据需要连续的存储空间）
2. 数据必须是排好序的
3. 时间复杂度：O(logn)

树与图

树与图.png

最后

学习视频内容可以看这里： https://zhuanlan.zhihu.com/p/96231226