文章目录
-
- 📝 一、 字符串模式匹配算法
-
- 1. BF 算法（Brute-Force 暴力匹配）
- 2. KMP 算法
- 📝 二、 插入类排序（Insertion Sort）
-
- 1. 直接插入排序
- 2. 折半插入排序（Binary Insertion Sort）
- 3. 希尔排序（Shell Sort）
- 📝 三、 交换类排序（Exchange Sort）
-
- 1. 冒泡排序（Bubble Sort）
- 2. 快速排序（Quick Sort）
- 📝 四、 选择类排序（Selection Sort）
-
- 1. 简单选择排序（Simple Selection Sort）
- 2. 堆排序（Heap Sort）
- 📝 五、 归并排序与基数排序
-
- 1. 二路归并排序（2-Way Merge Sort）
- 2. 基数排序（Radix Sort）
- 📊 📊 六、 总结：408内部排序全算法速查大表
📝 一、 字符串模式匹配算法
1. BF 算法（Brute-Force 暴力匹配）
-
⚖️ 算法核心与方法总结（原笔记）：
-
“就像插槽一样，要求从左往右一一完全对应，才匹配”
-
做题切入点：在匹配过程中，若发生失配，主串指针需要回溯。核心技巧在于“看错最后一位”（注意失配位置与主串回溯的对应关系）。
-
⏳ 性能指标补充：
-
时间复杂度：最好情况
O
(
n
+
m
)
O(n+m)
O(n+m)，最坏情况
O
(
n
×
m
)
O(n \\times m)
O(n×m)（其中
n
n
n 为主串长度，
m
m
m 为模式串长度）。
-
空间复杂度：
O
(
1
)
O(1)
O(1)。
2. KMP 算法
-
⚖️ 算法核心与方法总结（原笔记）：
-
① 前缀串：例如，串 abc 的前缀包括 a, ab。
-
② 后缀串：例如，串 abc 的后缀包括 c, bc。
-
③ next[] 数组的求解：寻找前缀串与后缀串的“无相同字符”（最长公共前后缀）。若前缀和后缀完全无相同字符，则对应的公共长度为 0，指针根据对应的 next 规则回溯（无相同字符则向特定初始值靠拢）。
-
⏳ 性能指标补充：
-
时间复杂度：
O
(
n
+
m
)
O(n+m)
O(n+m)（主串指针不回溯，仅模式串指针利用 next 数组滑动）。
-
空间复杂度：
O
(
m
)
O(m)
O(m)（需要额外的 next 数组空间）。
📝 二、 插入类排序（Insertion Sort）
- ⚖️ 算法核心与方法总结（原笔记）：
- 将整个序列划分为“有序区”与“无序区”。
- 核心动作是“逐个插入”：依次将无序区的元素扫描并插入到有序区的合适位置。
1. 直接插入排序
-
⏳ 性能指标（原笔记）：
-
时间复杂度：
-
最好情况：
O
(
n
)
O(n)
O(n) （原本就已经是正序有序）
-
最坏/平均情况：
O
(
n
2
)
O(n^2)
O(n2)
-
空间复杂度：
O
(
1
)
O(1)
O(1)
2. 折半插入排序（Binary Insertion Sort）
- ⏳ 性能指标（原笔记）：
- 时间复杂度：最好情况
O
(
n
log
2
n
)
O(n \\log_2 n)
O(nlog2n)，最坏情况O
(
n
2
)
O(n^2)
O(n2)。 - 空间复杂度：
O
(
1
)
O(1)
O(1)。 - 💡 408 考点挖坑补充：折半插入排序仅减少了“比较”的次数（优化为
O
(
n
log
2
n
)
O(n \\log_2 n)
O(nlog2n)），但“移动”元素的次数依然是O
(
n
2
)
O(n^2)
O(n2)，因此总的最坏时间复杂度仍为O
(
n
2
)
O(n^2)
O(n2)。
3. 希尔排序（Shell Sort）
- ⏳ 性能指标（原笔记）：
- 时间复杂度：取决于步长序列的设定，一般约为
O
(
n
1.3
)
O(n^{1.3})
O(n1.3)，最坏情况为O
(
n
2
)
O(n^2)
O(n2)。 - 空间复杂度：
O
(
1
)
O(1)
O(1)。
📝 三、 交换类排序（Exchange Sort）
1. 冒泡排序（Bubble Sort）
-
⚖️ 算法核心与方法总结（原笔记）：
-
“一比一交换”：相邻元素两两比较并进行交换。
-
“每一次把最大的放在序列尾”（或将最小的元素浮动到序列头）。
-
⏳ 性能指标（原笔记）：
-
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
-
空间复杂度：
O
(
1
)
O(1)
O(1)
2. 快速排序（Quick Sort）
-
⚖️ 算法核心与方法总结（原笔记）：
-
基于“分治”思想。
-
“每一趟把枢轴元素放在最终位置”。
-
双指针移动口诀（做题追踪核心）：“high选一个低于/小于枢轴值的，low选一个高的 —— 直到 low = high”。
-
⏳ 性能指标（原笔记）：
-
时间复杂度：
O
(
n
log
2
n
)
O(n \\log_2 n)
O(nlog2n)
-
空间复杂度（递归调用栈深度）：
-
最好情况：
O
(
log
2
n
)
O(\\log_2 n)
O(log2n)
-
最坏情况：
O
(
n
)
O(n)
O(n) （当序列原本就有序或逆序，快排退化为冒泡）
📝 四、 选择类排序（Selection Sort）
- ⚖️ 算法核心与方法总结（原笔记）：
- “每次选一个最（大/小）元素放到最前/后”。
1. 简单选择排序（Simple Selection Sort）
- ⏳ 性能指标（原笔记）：
- 时间复杂度：
O
(
n
2
)
O(n^2)
O(n2) （无论初始状态如何，元素之间的比较次数都是固定不可省的n
(
n
−
1
)
2
\\frac{n(n-1)}{2}
2n(n−1)）。 - 空间复杂度：
O
(
1
)
O(1)
O(1)
2. 堆排序（Heap Sort）
- ⚖️ 结构分类（原笔记）：分为“大根堆”与“小根堆”。
- 做题切入点（原笔记红字）：初始建堆时，从
[
⌊
n
/
2
⌋
]
[\\lfloor n/2 \\rfloor]
[⌊n/2⌋]（即最后一个非叶子节点）“开始考虑”，自底向上逐步进行筛选和调整。 - ⏳ 性能指标补充：
- 时间复杂度：最好/最坏/平均情况均为
O
(
n
log
2
n
)
O(n \\log_2 n)
O(nlog2n)。 - 空间复杂度：
O
(
1
)
O(1)
O(1)。
📝 五、 归并排序与基数排序
1. 二路归并排序（2-Way Merge Sort）
- ⏳ 性能指标（原笔记）：
- 时间复杂度：
O
(
n
log
2
n
)
O(n \\log_2 n)
O(nlog2n) - 空间复杂度：
O
(
n
)
O(n)
O(n) （需要与原数组同等大小的辅助空间用于归并合并）。
2. 基数排序（Radix Sort）
-
⚖️ 算法核心与方法总结（原笔记）：
-
“低位开始分”：从个位、十位、百位等低位关键字依次开始。
-
核心步骤为“分配和收集”。
-
⏳ 性能指标（原笔记）：
-
时间复杂度：
O
(
d
(
n
+
r
)
)
O(d(n+r))
O(d(n+r)) （其中
d
d
d 为关键码的码数/位数，
r
r
r 为基数/桶数，如十进制则
r
=
10
r=10
r=10）。
-
空间复杂度：
O
(
r
)
O(r)
O(r) （需要
r
r
r 个队列做辅助空间）。
📊 📊 六、 总结：408内部排序全算法速查大表
为了方便博文读者整体复习和对比记忆，特将笔记中的性能指标提炼成下表：
| 插入类 | 直接插入排序 |
O ( n ) O(n) O(n) |
O ( n 2 ) O(n^2) O(n2) |
O ( n 2 ) O(n^2) O(n2) |
O ( 1 ) O(1) O(1) |
稳定 |
| 折半插入排序 |
O ( n log 2 n ) O(n \\log_2 n) O(nlog2n) |
O ( n 2 ) O(n^2) O(n2) |
O ( n 2 ) O(n^2) O(n2) |
O ( 1 ) O(1) O(1) |
稳定 | |
| 希尔排序 |
O ( n 1.3 ) O(n^{1.3}) O(n1.3) |
O ( n 2 ) O(n^2) O(n2) |
O ( n 1.3 ) O(n^{1.3}) O(n1.3) |
O ( 1 ) O(1) O(1) |
不稳定 | |
| 交换类 | 冒泡排序 |
O ( n ) O(n) O(n) |
O ( n 2 ) O(n^2) O(n2) |
O ( n 2 ) O(n^2) O(n2) |
O ( 1 ) O(1) O(1) |
稳定 |
| 快速排序 |
O ( n log 2 n ) O(n \\log_2 n) O(nlog2n) |
O ( n 2 ) O(n^2) O(n2) |
O ( n log 2 n ) O(n \\log_2 n) O(nlog2n) |
O ( log 2 n ) ∼ O ( n ) O(\\log_2 n) \\sim O(n) O(log2n)∼O(n) |
不稳定 | |
| 选择类 | 简单选择排序 |
O ( n 2 ) O(n^2) O(n2) |
O ( n 2 ) O(n^2) O(n2) |
O ( n 2 ) O(n^2) O(n2) |
O ( 1 ) O(1) O(1) |
不稳定 |
| 堆排序 |
O ( n log 2 n ) O(n \\log_2 n) O(nlog2n) |
O ( n log 2 n ) O(n \\log_2 n) O(nlog2n) |
O ( n log 2 n ) O(n \\log_2 n) O(nlog2n) |
O ( 1 ) O(1) O(1) |
不稳定 | |
| 归并类 | 二路归并排序 |
O ( n log 2 n ) O(n \\log_2 n) O(nlog2n) |
O ( n log 2 n ) O(n \\log_2 n) O(nlog2n) |
O ( n log 2 n ) O(n \\log_2 n) O(nlog2n) |
O ( n ) O(n) O(n) |
稳定 |
| 基数类 | 基数排序 |
O ( d ( n + r ) ) O(d(n+r)) O(d(n+r)) |
O ( d ( n + r ) ) O(d(n+r)) O(d(n+r)) |
O ( d ( n + r ) ) O(d(n+r)) O(d(n+r)) |
O ( r ) O(r) O(r) |
稳定 |
