标签: 算法基础

算法策略

1. 考点：分治法

1.1 知识点概览

算法策略 —— 考点：算法策略概述（分治法）

特征：把一个问题拆分成多个小规模的相同子问题，一般用递归解决，也可以用循环。
经典问题：归并排序、快速排序、矩阵乘法、二分搜索、斐波那契数列、大整数乘法、汉诺塔。
关键词：一分为二、一一合二。
注意：不要陷入到递归调用的证明，直接调用下层即可。

2026/9/19大约 12 分钟

排序算法对比

1. 考点：常见排序算法的对比

1.1 常见排序算法性能对比总览

类别	排序方法	平均情况时间复杂度	特殊情况时间复杂度	空间复杂度（辅助存储）	稳定性
插入排序	直接插入	O(n²)	基本有序最优 O(n)	O(1)	稳定
插入排序	Shell 排序	O(n^1.3)	—	O(1)	不稳定
选择排序	直接选择	O(n²)	—	O(1)	不稳定
选择排序	堆排序	O(n log₂ n)	—	O(1)	不稳定
交换排序	冒泡排序	O(n²)	基本有序最优 O(n)	O(1)	稳定
交换排序	快速排序	O(n log₂ n)	基本有序最差 O(n²)	O(1)	不稳定
归并排序		O(n log₂ n)	—	O(n)	稳定
基数排序		O(d(n + rd))	—	O(rd)	稳定

2026/9/19大约 6 分钟

基数排序

1. 考点：基础概况

1.1 知识点概览

排序算法 —— 其他类排序：基数排序（Radix Sort）

基本思想：
- 基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。
- 它不是基于关键字比较的排序方法，因此非常适合于元素数量很多但关键字较少的序列。
- 基数选择和关键字的分解取决于关键字的类型，例如十进制数可按个位、十位进行分解。

2026/9/19大约 1 分钟

归并排序

1. 考点：基础概念

排序算法 —— 归并排序（Merge Sort）

基本思想：归并也称为合并，是将两个或两个以上的有序子表合并成一个新的有序表。若将两个有序表合并成一个有序表，则称为二路合并。
- 合并过程：比较 $A[i]$ 和 $A[j]$ 的排序码大小，若 $A[i]$ 的排序码小于等于 $A[j]$ 的排序码，则将第一个有序表中的元素 $A[i]$ 复制到 $R[k]$ 中，并令 $i$ 和 $k$ 分别加 1；如此循环下去，直到其中一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到 $R$ 中。
算法特性：
- 稳定性：归并排序是一种稳定的排序方法。
- 时间复杂度：其时间复杂度约为 $O(n\log_2 n)$ 。
- 空间复杂度：在排序过程中需要一个元素的辅助空间用于数组元素的交互，同时需要一个新的数组存数据，所以空间复杂度为 $O(n)$ 。

2026/9/19大约 3 分钟

交换类排序

1. 考点：冒泡排序

1.1 知识点概览

排序算法 —— 交换类排序：冒泡排序（Bubble Sort）

基本思想：通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移向顶部。由于整个排序的过程元素就像水底的气泡一样逐渐向上冒，因此称为冒泡算法。
算法特性：
- 稳定性：冒泡排序是一种稳定的排序方法。
- 时间复杂度：其时间复杂度约为 $O(n^2)$ 。
- 空间复杂度：在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为 $O(1)$ 。

2026/9/19大约 6 分钟

选择类排序

1. 考点：直接选择排序

1.1 知识点概览

排序算法 —— 选择类排序：直接选择排序（Straight Selection Sort）

基本思想：首先在所有记录中选出排序码最小的记录，把它与第 1 个记录交换，然后在其余的记录内选出排序码最小的记录，与第 2 个记录交换……依次类推，直到所有记录排完为止。
算法特性：
- 稳定性：直接选择排序是一种不稳定的排序方法。
- 时间复杂度：其时间复杂度约为 $O(n^2)$ 。
- 空间复杂度：在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为 $O(1)$ 。

2026/9/19大约 5 分钟

插入类排序

1. 考点：直接插入排序

1.1 知识点概览

排序算法 —— 插入类排序：直接插入排序（Straight Insertion Sort）

基本思想：当插入第 $i$ 个记录时， $R_1, R_2, \cdots, R_{i-1}$ 均已排好序。因此，将第 $i$ 个记录 $R_i$ 依次与 $R_{i-1}, \cdots, R_2, R_1$ 进行比较，找到合适的位置插入。它简单明了，但速度很慢。
算法特性：
- 稳定性：直接插入排序是一种稳定的排序方法。
- 时间复杂度：平均和最坏情况下时间复杂度为 $O(n^2)$ ；在基本有序的情况下，时间复杂度接近线性，即 $O(n)$ 。
- 空间复杂度：在排序过程中仅需要一个元素的辅助空间，空间复杂度为 $O(1)$ 。

2026/9/19大约 4 分钟

排序算法的基本概念

1. 考点：知识点概览

排序算法 —— 基本概念与分类

排序的概念：
- 稳定与不稳定排序：相同大小元素排序前后的相对顺序不变就是稳定的，反之不稳定。
- 判断技巧：是否跨区域交换。
排序方法分类：
- 1、插入类排序：直接插入排序、希尔排序。
- 2、选择类排序：简单选择排序、堆排序。
- 3、交换类排序：冒泡排序、快速排序。
- 4、归并排序。
- 5、基数排序。

2026/9/19大约 1 分钟

哈希表查找

1. 考点：实例讲解

1.1 知识点概览

查找算法 —— 哈希表查找（Hash Table Search / 散列表查找）

基本思想：已知关键字集合 $U$ ，最大关键字为 $m$ ，设计一个函数 $\text{Hash}$ ，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间 $T[0..n-1]$ （其中 $n < m$ ）中，这个区间称为散列表（或哈希表），查找中使用的转换函数称为散列函数。

2026/9/19大约 5 分钟

二分查找

1. 考点：基础概述

查找算法 —— 二分查找（Binary Search / 折半查找）

基本思想（设 $R[\text{low}, \cdots, \text{high}]$ 是当前的查找区）：
1. 确定中点位置： $\text{mid} = \lfloor (\text{low} + \text{high}) / 2 \rfloor$ 。
2. 关键字比较：将待查的 $k$ 值与 $R[\text{mid}].\text{key}$ 比较：
  - 若相等，则查找成功并返回此位置。
  - 若 $R[\text{mid}].\text{key} > k$ ，则由表的有序性可知 $R[\text{mid}, \cdots, n].\text{key}$ 均大于 $k$ ，因此若表中存在关键字等于 $k$ 的结点，该结点必定是在位置 $\text{mid}$ 左边的子表 $R[\text{low}, \cdots, \text{mid}-1]$ 中。因此，新的查找区间是左子表，其中 $\text{high} = \text{mid}-1$ 。
  - 若 $R[\text{mid}].\text{key} < k$ ，则要查找的 $k$ 必在 $\text{mid}$ 的右子表 $R[\text{mid}+1, \cdots, \text{high}]$ 中，即新的查找区间是右子表，其中 $\text{low} = \text{mid}+1$ 。
3. 重复步骤：下一次查找是针对新的查找区间进行，重复步骤 (1) 和 (2)。
4. 终止条件：在查找过程中， $\text{low}$ 逐步增加，而 $\text{high}$ 逐步减少。如果 $\text{high} < \text{low}$ ，则查找失败，算法结束。

2026/9/19大约 5 分钟