geek

《数据结构与算法之美》-1-线性表

算法

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

基础架构研发工程师，写出达到开源水平的框架才是你的目标！

性能好坏起码是其中一个非常重要的评判标准。

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

重点：

  1. 首先要掌握一个数据结构与算法中最重要的概念——复杂度分析
  2. 10个数据结构
    1. 数组
    2. 链表
    3. 栈
    4. 队列
    5. 散列表
    6. 二叉树
    7. 堆
    8. 跳表
    9. 图
    10. Trie树
  3. 10个算法
    1. 递归
    2. 排序
    3. 二分查找
    4. 搜索
    5. 哈希算法
    6. 贪心算法
    7. 分治算法
    8. 回溯算法
    9. 动态规划
    10. 字符串匹配算法
  4. 技巧
    1. 边学边练，适度刷题
    2. 多问、多思考、多互动
    3. 打怪升级学习法
    4. 知识需要沉淀，不要想试图一下子掌握所有

复杂度分析

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

不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。

大O复杂度表示法

在采用大O标记复杂度的时候，可以忽略系数

  • 大O时间复杂度表示法
    • 表示代码执行时间随数据规模增长的变化趋势
    • 也叫作 渐进时间复杂度（asymptotic time complexity）
    • 简称 时间复杂度

\[ T(n)=O(f(n)) \]

  1. n：数据规模的大小
  2. T(n)：代码执行时间
  3. f(n)：每行代码执行的次数总和
  4. 公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比

记录一个最大量级

时间复杂度分析

  1. 只关注循环执行次数最多的一段代码
  2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

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

  1. 多项式量级
    1. 常量阶：\(O(1)\)
      1. 不存在循环语句、递归语句
    2. 对数阶：\(O(\log n)\)
      1. 忽略对数的“底”
    3. 线性阶：\(O(n)\)
      1. \(O(m+n)\)
    4. 线性对数阶： \(O(n \log n)\)
      1. 归并排序
      2. 快速排序
    5. 方阶：
      1. 平方阶： \(O(n^2)\)
      2. 立方阶： \(O(n^3)\)
      3. \(k\) 次方阶： \(O(n^{k})\)
  2. 非多项式量级（低效）
    1. 指数阶：\(O(2^{n})\)
    2. 阶乘阶：\(O(n!)\)

空间复杂度分析

  • 大O时间复杂度表示法
    • 算法的存储空间与数据规模之间的增长关系
    • 也叫作 渐进空间复杂度（asymptotic space complexity）
    • 简称 空间复杂度
  1. \(O(1)\)
  2. \(O(n)\)
  3. \(O(n^{2})\)

四个复杂度分析

  1. 最好情况时间复杂度（best case time complexity）
    1. 最理想的情况
  2. 最坏情况时间复杂度（worst case time complexity）
    1. 最糟糕的情况
  3. 平均情况时间复杂度（average case time complexity）
    1. 加权平均值
    2. 全称：加权平均时间复杂度
    3. 期望值
    4. 全称：期望时间复杂度
  4. 均摊时间复杂度（amortized time complexity）
    1. 摊还分析 / 平摊分析
    2. 均摊时间复杂度 就是一种 特殊 的 平均时间复杂度

基础

数组（Array）

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

  • 线性表（Linear List）
    • 线性表就是数据排成像一条线一样的结构
    • 每个线性表上的数据最多只有前和后两个方向
    • 类型
      1. 数组
      2. 链表
      3. 队列
      4. 栈

  • 非线性表
    1. 二叉树
    2. 堆
    3. 图

  • 连续的内存空间和相同类型的数据
    • 随机访问

1
a[i]_address = base_address + i * data_type_size

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

  • 插入操作
    • 交换最后
    • 快排

  • 删除操作
    • 记录下已经删除的数据

警惕数组的访问越界问题

容器能否完全替代数组？

Java ： ArrayList
C++ STL： vector

  • 将很多数组操作的细节封装起来
  • 支持动态扩容

数组 vs 容器：

  1. 数组
    1. 底层开发
    2. 关注性能 / 基本类型
    3. 数据大小事先已知 / 操作简单
    4. 多维数组直观
  2. 容器
    1. 业务开发

数组要从0开始编号

1
a[k]_address = base_address + k * type_size
  1. “偏移（offset）”
  2. 习惯：C语言设计者用 \(0\) 开始计数数组下标，

小结

数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为O(n)。在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。

链表（Linked list）

缓存

  1. CPU缓存
  2. 数据库缓存
  3. 浏览器缓存

缓存淘汰策略

  1. 先进先出策略 FIFO（First In，First Out）
  2. 最少使用策略 LFU（Least Frequently Used）
  3. 最近最少使用策略 LRU（Least Recently Used）

底层的存储结构

  1. 单链表
  2. 循环链表
  3. 双向链表

单链表

结点： 内存块
后继指针 next

  1. 头结点：第一个结点
  2. 尾结点：最后个结点
    • 指向一个空地址 NULL

查找、插入和删除操作

循环链表

循环链表是一种特殊的单链表

约瑟夫问题

双向链表

删除操作

  • 删除结点中“值等于某个给定值”的结点
    • \(O(n)\)
  • 删除给定指针指向的结点
    • \(O(1)\)

用空间换时间 的 设计思想

  1. 缓存
  2. 双向链表

双向循环链表

链表 VS 数组性能

LRU（Least Recently Used）缓存

  1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中，又可以分为两种情况：
    1. 如果此时缓存未满，则将此结点直接插入到链表的头部；
    2. 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

代码技巧

  1. 理解指针或引用的含义
  2. 警惕指针丢失和内存泄漏
    1. 插入结点时，一定要注意操作的顺序
    2. 删除链表结点时，也一定要记得手动释放内存空间
  3. 利用哨兵简化实现难度
    1. 针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理
  4. 重点留意边界条件处理
    1. 如果链表为空时，代码是否能正常工作？
    2. 如果链表只包含一个结点时，代码是否能正常工作？
    3. 如果链表只包含两个结点时，代码是否能正常工作？
    4. 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
  5. 举例画图，辅助思考
  6. 多写多练，没有捷径
    1. 单链表反转
    2. 链表中环的检测
    3. 两个有序的链表合并
    4. 删除链表倒数第n个结点
    5. 求链表的中间结点

内容小结

链表跟数组一样，也是非常基础、非常常用的数据结构。不过链表要比数组稍微复杂，从普通的单链表衍生出来好几种链表结构，比如双向链表、循环链表、双向循环链表。

和数组相比，链表更适合插入、删除操作频繁的场景，查询的时间复杂度较高。不过，在具体软件开发中，要对数组和链表的各种性能进行对比，综合来选择使用两者中的哪一个。

栈2

后进先出

栈是一种“操作受限”的线性表

操作

  • 插入：入栈 push()
  • 删除：出栈 pop()

栈顶指针

支持动态扩容的顺序栈

栈在函数调用中的应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}

栈在表达式求值中的应用

栈在括号匹配中的应用

\[ {[()]} \]

浏览器的前进和后退

队列

操作受限的线性表数据结构

操作

  • 插入：入队 enqueue()
  • 删除：出队 dequeue()

先进先出

实现 数组 链表
栈 顺序栈 链式栈
队列 顺序队列 链式队列
  • 一个是 head 指针，指向队头
  • 一个是 tail 指针，指向队尾

数据搬移

基于链表的队列实现方法

循环队列

阻塞队列和并发队列

阻塞队列：生产者-消费者模型

并发队列：线程安全的队列

对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

内容小结

队列：一种跟栈很相似的数据结构。

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

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

除此之外，我们还讲了几种高级的队列结构，阻塞队列、并发队列，底层都还是队列这种数据结构，只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全。

递归

  • 去的过程叫“递”
  • 回来的过程叫“归”

递归需要满足的三个条件

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

编写递归代码

  1. 写出递推公式
  2. 找到终止条件
  3. 递推公式 -> 代码

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

  • 递归代码要警惕堆栈溢出

  • 递归代码要警惕重复计算

    • 通过一个数据结构（比如散列表）来保存已经求解过的f(k)

  • 递归代码 -> 为非递归代码（迭代循环）

内容小结

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

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

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

排序

排序比较3

排序 排序算法
理论 计算复杂性理论 大O符号 全序关系 数据结构列表 原地算法 稳定性 比较排序 自适应排序 排序网络 整数排序 X+Y排序 量子排序
交换排序 冒泡排序 鸡尾酒排序 奇偶排序 梳排序 侏儒排序 快速排序 臭皮匠排序 Bogo排序
选择排序 选择排序 堆排序 平滑排序 笛卡尔树排序 锦标赛排序 圈排序 弱堆排序
插入排序 插入排序 希尔排序 伸展排序 二叉查找树排序 图书馆排序 耐心排序
归并排序 归并排序 梯级归并排序 振荡归并排序 多相归并排序
分布排序 美国旗帜排序 珠排序 桶排序 爆炸排序 计数排序 比較計數排序 插值排序 鸽巢排序 相邻图排序 基数排序 闪电排序
并发排序 双调排序器 Batcher归并网络 两两排序网络
混合排序 塊排序 Tim排序 内省排序 Spread排序 归并插入排序
其他 拓扑排序 煎餅排序 意粉排序
en
zh
  • 均按从小到大排列
  • k 代表数值中的"数位"个数
  • n 代表数据规模
  • m 代表数据的最大值减最小值

如何分析一个“排序算法”？

  1. 排序算法的执行效率
    1. 最好情况、最坏情况、平均情况时间复杂度
    2. 时间复杂度的系数、常数 、低阶
    3. 比较次数和交换（或移动）次数
  2. 排序算法的内存消耗
    1. 原地排序（Sorted in place）
    2. 空间复杂度是O(1)
  3. 排序算法的稳定性

冒泡排序（Bubble Sort）

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

原子操作：

  1. 比较
  2. 交换

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 冒泡排序，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;  // 没有数据交换，提前退出
  }
}

有序度

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

满有序度

\(n*(n-1)/2\)

逆序度 = 满有序度 - 有序度

交换一次，有序度就加 1。

插入排序（Insertion Sort）

数据分为两个区间

  1. 已排序区间
  2. 未排序区间

原子操作：

  1. 比较
  2. 移动

移动次数 = 逆序度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 插入排序，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; // 插入数据
  }
}

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

冒泡排序中数据的交换操作：

1
2
3
4
5
6
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

插入排序中数据的移动操作：

1
2
3
4
5
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

选择排序（Selection Sort）

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。

但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

\(O(n^{2})\) 的排序算法：冒泡排序、插入排序、选择排序

归并排序（Merge Sort）

归并排序的核心思想

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

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

  • 分治 是一种解决问题的处理思想
  • 递归 是一种编程技巧

递推公式：

\(merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))\)

终止条件：

\(p >= r\) 不用再继续分解

merge_sort(p…r) 表示，给下标从 p 到 r 之间的数组排序。我们将这个排序问题转化为了两个子问题，merge_sort(p…q) 和 merge_sort(q+1…r)，其中下标 q 等于 p 和 r 的中间位置，也就是 (p+r)/2。当下标从 p 到 q 和从 q+1 到 r 这两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样下标从 p 到 r 之间的数据就也排好序了。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 归并排序算法, 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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]
  }
}

快速排序 / 快排（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\)

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
// 快速排序，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)
}

归并排序中有一个 merge() 合并函数，我们这里有一个 partition() 分区函数。

partition()分区函数实际上我们前面已经讲过了，就是随机选择一个元素作为 pivot（一般情况下，可以选择p到r区间的最后一个元素），然后对 A[p…r] 分区，函数返回 pivot 的下标。

不考虑空间消耗，申请 2 个新数组

考虑空间消耗，原地分区函数

1
2
3
4
5
6
7
8
9
10
11
12
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
}

归并排序 VS 快排

  1. 归并排序的处理过程是由下到上的，先处理子问题，然后再合并。
  2. 快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。

为什么 归并排序 并没有像 快排 应用广泛？

归并排序有一个致命的“弱点”，不是原地排序算法。

内容小结

归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。理解归并排序的重点是理解递推公式和 merge() 合并函数。同理，理解快排的重点也是理解递推公式，还有 partition() 分区函数。

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 \(O(n)\)。正因为此，它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是 \(O(n^{2})\)，但是平均情况下时间复杂度都是 \(O(n \log n)\)。不仅如此，快速排序算法时间复杂度退化到 \(O(n^{2})\) 的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。

桶排序（Bucket sort）

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

复杂度： \(O(n)\)

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

桶排序看起来很优秀，那它是不是可以替代我们之前讲的排序算法呢？

答案当然是否定的。为了让你轻松理解桶排序的核心思想，我刚才做了很多假设。实际上，桶排序对要排序数据的要求是非常苛刻的。

首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。

其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 \(O(n \log n)\) 的排序算法了。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

计数排序（Counting sort）：桶排序的一种特殊情况

当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

示例：高考分数

满分是 \(900\) 分，最小是 \(0\) 分，可以分成 \(901\) 个桶，对应分数从 \(0\) 分到 \(900\) 分。

桶内的数据都是分数相同的考生，所以并不需要再进行排序。

1
int A[8] = { 2，5，3，0，2，3，0，3 };

C[6] 表示桶 ,其中下标对应分数。不过，C[6] 内存储的并不是考生，而是对应的考生个数。

如何快速计算出，每个分数的考生在有序数组中对应的存储位置呢？

思路是这样的：我们对C[6]数组顺序求和，C[6]存储的数据就变成了下面这样子。C[k]里存储小于等于分数k的考生个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
  if (n <= 1) return;

  // 查找数组中数据的范围
  int max = a[0];
  for (int i = 1; i < n; ++i) {
    if (max < a[i]) {
      max = a[i];
    }
  }

  int[] c = new int[max + 1]; // 申请一个计数数组c，下标大小[0,max]
  for (int i = 0; i <= max; ++i) {
    c[i] = 0;
  }

  // 计算每个元素的个数，放入c中
  for (int i = 0; i < n; ++i) {
    c[a[i]]++;
  }

  // 依次累加
  for (int i = 1; i <= max; ++i) {
    c[i] = c[i-1] + c[i];
  }

  // 临时数组r，存储排序之后的结果
  int[] r = new int[n];
  // 计算排序的关键步骤，有点难理解
  for (int i = n - 1; i >= 0; --i) {
    int index = c[a[i]]-1;
    r[index] = a[i];
    c[a[i]]--;
  }

  // 将结果拷贝给a数组
  for (int i = 0; i < n; ++i) {
    a[i] = r[i];
  }
}

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

基数排序（Radix sort）

手机号码从小到大排序

按照每位来排序的排序算法要是稳定的。

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

线性排序（Linear sort）/ 复杂度是 \(O(n)\) 的排序算法：桶排序、计数排序、基数排序

它们对要排序的数据都有比较苛刻的要求，应用不是非常广泛。但是如果数据特征比较符合这些排序算法的要求，应用这些算法，会非常高效，线性时间复杂度可以达到O(n)。

桶排序和计数排序的排序思想是非常相似的，都是针对范围不大的数据，将数据划分成不同的桶来实现排序。基数排序要求数据可以划分成高低位，位之间有递进关系。比较两个数，我们只需要比较高位，高位相同的再比较低位。而且每一位的数据范围不能太大，因为基数排序算法需要借助桶排序或者计数排序来完成每一个位的排序工作。

如何实现一个通用的、高性能的排序函数？

  1. 线性排序算法的时间复杂度比较低，适用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。
  2. 首选时间复杂度是 \(O(n \log n)\) 的排序算法
    1. 小规模数据进行排序，可以选择时间复杂度是 \(O(n^{2})\) 的算法
    2. 大规模数据进行排序，时间复杂度是 \(O(n \log n)\) 的算法更加高效
  3. 对于小数据量的排序，不需要递归的插入排序算法

如何优化快速排序？

被分区点分开的两个分区中，数据的数量差不多。

  1. 三数取中法
  2. 随机法

堆栈溢出

  1. 限制递归深度
    • 超过了我们事先设定的阈值，就停止递归
  2. 堆上模拟实现一个函数调用栈
    • 手动模拟递归压栈、出栈的过程

分析了一下如何来实现一个工业级的通用的、高效的排序函数，内容比较偏实战，而且贯穿了一些前面几节的内容，你要多看几遍。我们大部分排序函数都是采用O(nlogn)排序算法来实现，但是为了尽可能地提高性能，会做很多优化。

快速排序的一些优化策略，比如合理选择分区点、避免递归太深等等。

C语言中 qsort() 的底层实现原理：

  1. 分区点
    • 三数取中法
  2. 堆栈溢出
    • 实现一个堆上的栈，手动模拟递归
  3. 元素的个数 <= 4
    • 插入排序
  4. 优先使用
    • 归并排序
  5. 数据量比较大
    • 快速排序

二分查找（Binary Search）/ 折半查找

猜数字游戏

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

\(O(\log n)\) 惊人的查找速度

\(O(\log n)\) 对数时间复杂度

二分查找的递归与非递归实现

循环实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;

  while (low <= high) {
    // low+((high-low)>>1)
    // low+(high-low)/2
    int mid = (low + high) / 2;
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

容易出错的3个地方

  1. 循环退出条件
  2. mid 的取值
  3. low 和 high 的更新

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
  return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value) {
  if (low > high) return -1;

  int mid =  low + ((high - low) >> 1);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return bsearchInternally(a, mid+1, high, value);
  } else {
    return bsearchInternally(a, low, mid-1, value);
  }
}

二分查找应用场景的局限性

  1. 二分查找依赖的是顺序表结构，简单点说就是数组
  2. 二分查找针对的是有序数据
  3. 数据量太小不适合二分查找
  4. 数据量太大也不适合二分查找
    • 连续内存空间

二分查找是一种针对有序数据的高效查找算法，它的时间复杂度是 \(O(\log n)\)。

二分查找的核心思想理解起来非常简单，有点类似分治思想。即每次都通过跟区间中的中间元素对比，将待查找的区间缩小为一半，直到找到要查找的元素，或者区间被缩小为 0 。但是二分查找的代码实现比较容易写错。

着重掌握它的三个容易出错的地方：循环退出条件、mid 的取值，low 和 high 的更新。

二分查找虽然性能比较优秀，但应用场景也比较有限。底层必须依赖数组，并且还要求数据是有序的。对于较小规模的数据查找，我们直接使用顺序遍历就可以了，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

唐纳德·克努特（Donald E.Knuth）在《计算机程序设计艺术》的第3卷《排序和查找》中说到：“尽管第一个二分查找算法于1946年出现，然而第一个完全正确的二分查找算法实现直到1962年才出现。”

跳表

这种链表加多级索引的结构，就是跳表。

空间换时间

插入操作

跳表索引动态更新

随机函数生成了值K

跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 \(O(\log n)\)。

跳表的空间复杂度是 \(O(n)\)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单，但是作为一种动态数据结构，比起红黑树来说，实现要简单多了。所以很多时候，我们为了代码的简单、易读，比起红黑树，我们更倾向用跳表。

散列表 / 哈希表 / Hash表（Hash Table）

散列表 用的是 数组 支持按照 下标随机访问 数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

编号我们叫作 键（key） 或者 关键字。

编号转化为数组下标的映射方法就叫作 散列函数（或“Hash函数”“哈希函数”）。

而散列函数计算得到的值就叫作 散列值（或“Hash值”“哈希值”）。

时间复杂度是 \(O(1)\)

散列函数

hash(key) 的值表示经过散列函数计算得到的散列值。

散列函数设计的基本要求：

  1. 散列函数计算得到的散列值是一个非负整数；
  2. 如果 key1 = key2，那 hash(key1) == hash(key2)；
  3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

散列冲突

  • 开放寻址法（open addressing）
    • 线性探测（Linear Probing）
      • \(hash(key)+0，hash(key)+1，hash(key)+2……\)
    • 二次探测（Quadratic probing）
      • \(hash(key)+0，hash(key)+1^{2}，hash(key)+2^{2}……\)
    • 双重散列（Double hashing）
      • \(hash1(key)，hash2(key)，hash3(key)……\)

插入

查找

删除：特殊标记为 deleted

装载因子（load factor）来表示空位的多少

\[ 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度 \]

  • 链表法（chaining）

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。

在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

散列表来源于数组，它借助散列函数对数组这种数据结构进行扩展，利用的是数组支持按照下标随机访问元素的特性。散列表两个核心问题是散列函数设计和散列冲突解决。散列冲突有两种常用的解决方法，开放寻址法和链表法。散列函数设计的好坏决定了散列冲突的概率，也就决定散列表的性能。

如何设计散列函数？

  1. 散列函数的设计不能太复杂
  2. 散列函数生成的值要尽可能随机并且均匀分布

方法：

  1. 数据分析法
  2. 直接寻址法
  3. 平方取中法
  4. 折叠法
  5. 随机数法

动态扩容的散列表

如何避免低效地扩容？

如何选择冲突解决方法？

  • 开放寻址法

当数据量比较小、装载因子小的时候，适合采用开放寻址法。

Java 中的 ThreadLocalMap 使用开放寻址法解决散列冲突的原因。

  • 链表法

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

工业级散列表举例分析：Java 中的 HashMap

  1. 初始大小
    • 默认的初始大小是16
  2. 装载因子和动态扩容
    • 最大装载因子默认是0.75
    • 超过 0.75*capacity（capacity表示散列表的容量）的时候，启动扩容
    • 每次扩容都会扩容为原来的两倍大小
  3. 散列冲突解决方法
    • < 8：链表法
    • > 8：红黑树
  4. 散列函数
    • 简单高效
    • 分布均匀
1
2
3
4
int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capitity -1); // capicity 表示散列表的大小
}

对于动态散列表来说，不管我们如何设计散列函数，选择什么样的散列冲突解决方法。随着数据的不断增加，散列表总会出现装载因子过高的情况。这个时候，我们就需要启动动态扩容。

为什么散列表和链表经常会一起使用

使用双向链表存储数据，链表中的每个结点处理存储数据（data）、前驱指针（prev）、后继指针（next）之外，还新增了一个特殊的字段 hnext。

散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是刚刚，另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中，hnext 指针是为了将结点串在散列表的拉链中。

散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说，它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历。

因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据的时候，都需要先排序，那效率势必会很低。为了解决这个问题，我们将散列表和链表（或者跳表）结合在一起使用。

哈希算法

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是 哈希算法，而通过原始数据映射之后得到的二进制值串就是 哈希值。

要求：

  1. 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
  2. 对输入数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的哈希值也大不相同；
  3. 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
  4. 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

MD5 的哈希值是 128位 的 Bit 长度

应用 (盐（salt）)

  1. 安全加密
    • MD5（MD5 Message-Digest Algorithm，MD5消息摘要算法）
    • SHA（Secure Hash Algorithm，安全散列算法）
    • DES（Data Encryption Standard，数据加密标准）
    • AES（Advanced Encryption Standard，高级加密标准）
  2. 唯一标识
    • 完整性和正确性
    • 信息摘要
    • 网盘秒传
  3. 数据校验
    • 下载校验
  4. 散列函数
    • 简单
    • 追求效率
  5. 负载均衡
    • 客户端 IP地址 或者 会话ID 与 服务器编号 映射
  6. 数据分片
    • MapReduce
  7. 分布式存储
    • 一致性哈希算法

  1. https://time.geekbang.org/column/intro/126↩︎

  2. https://github.com/wangzheng0822/algo↩︎

  3. https://zh.wikipedia.org/zh-cn/排序算法↩︎