Skip to content

Commit 77c511a

Browse files
itchargeitcharge
committed
修复和优化语句表述
1 parent 3af4e75 commit 77c511a

13 files changed

+1060
-900
lines changed

‎docs/01_array/01_15_array_two_pointers.md

Lines changed: 122 additions & 216 deletions
Large diffs are not rendered by default.

‎docs/01_array/01_16_array_sliding_window.md

Lines changed: 97 additions & 93 deletions
Large diffs are not rendered by default.

‎docs/02_linked_list/02_01_linked_list_basic.md

Lines changed: 173 additions & 218 deletions
Large diffs are not rendered by default.

‎docs/02_linked_list/02_02_linked_list_sort.md

Lines changed: 31 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,45 +1,51 @@
11
## 1. 链表排序简介
22

3-
在数组排序中，常见的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。
3+
链表排序相比数组排序具有独特的挑战性。由于链表 **不支持随机访问**，只能通过 $next$ 指针顺序遍历，这使得某些排序算法在链表上的实现更加复杂。
44

5-
而对于链表排序而言，因为链表不支持随机访问，访问链表后面的节点只能依靠 `next` 指针从头部顺序遍历，所以相对于数组排序问题来说，链表排序问题会更加复杂一点。
5+
### 1.1 算法适用性分析
66

7-
下面先来总结一下适合链表排序与不适合链表排序的算法：
7+
| 适用性 | 排序算法 | 说明 |
8+
|--------|----------|------|
9+
| **完全适合** | 冒泡排序、选择排序、插入排序、归并排序、快速排序 | 天然适合链表结构 |
10+
| **需要额外空间** | 计数排序、桶排序、基数排序 | 需要辅助数组，但算法逻辑适合 |
11+
| **不适合** | 希尔排序 | 依赖随机访问，链表无法高效实现 |
12+
| **不推荐** | 堆排序 | 完全二叉树结构用链表存储效率低 |
813

9-
- 适合链表的排序算法：**冒泡排序**、**选择排序**、**插入排序**、**归并排序**、**快速排序**、**计数排序**、**桶排序**、**基数排序**。
10-
- 不适合链表的排序算法：**希尔排序**。
11-
- 可以用于链表排序但不建议使用的排序算法：**堆排序**。
14+
### 1.2 关键限制因素
1215

13-
> 希尔排序为什么不适合链表排序？
16+
**希尔排序的限制**：希尔排序需要访问序列中第 $i + gap$ 个元素，链表无法直接跳转，必须从头遍历，时间复杂度从 $O(1)$ 退化为 $O(n)$。
1417

15-
**希尔排序**：希尔排序中经常涉及到对序列中第 $i + gap$ 的元素进行操作，其中 $gap$ 是希尔排序中当前的步长。而链表不支持随机访问的特性，导致这种操作不适合链表，因而希尔排序算法不适合进行链表排序。
18+
**堆排序的限制**：堆排序基于完全二叉树结构，数组可以通过下标 $O(1)$ 访问父子节点，而链表需要遍历查找，效率极低。
1619

17-
> 为什么不建议使用堆排序？
1820

19-
**堆排序**：堆排序所使用的最大堆 / 最小堆结构本质上是一棵完全二叉树。而完全二叉树适合采用顺序存储结构（数组）。因为数组存储的完全二叉树可以很方便的通过下标序号来确定父亲节点和孩子节点，并且可以极大限度的节省存储空间。
21+
## 2. 常见链表排序算法
2022

21-
而链表用在存储完全二叉树的时候，因为不支持随机访问的特性，导致其寻找子节点和父亲节点会比较耗时，如果增加指向父亲节点的变量，又会浪费大量存储空间。所以堆排序算法不适合进行链表排序。
23+
链表排序算法可分为 **比较排序** 和 **非比较排序** 两大类，每种算法都有其适用场景和性能特点。
2224

23-
如果一定要对链表进行堆排序，则可以使用额外的数组空间表示堆结构。然后将链表中各个节点的值依次添加入堆结构中，对数组进行堆排序。排序后，再按照堆中元素顺序，依次建立链表节点，构建新的链表并返回新链表头节点。
25+
### 2.1 比较排序算法
2426

25-
> 需要用到额外的辅助空间进行排序的算法
27+
| 算法 | 核心思想 | 时间复杂度 | 空间复杂度 | 特点 |
28+
|------|----------|------------|------------|------|
29+
| **冒泡排序** | 相邻节点比较交换 | $O(n^2)$ | $O(1)$ | 实现简单，适合小规模数据 |
30+
| **选择排序** | 选择最小节点交换 | $O(n^2)$ | $O(1)$ | 交换次数少，适合交换成本高的场景 |
31+
| **插入排序** | 逐个插入到有序序列 | $O(n^2)$ | $O(1)$ | 链表上表现优异，适合部分有序数据 |
32+
| **归并排序** | 分治合并 | $O(n \log n)$ | $O(1)$ | 链表上的最优选择，稳定高效 |
33+
| **快速排序** | 基准分割递归 | $O(n \log n)$ | $O(1)$ | 平均性能好，但最坏情况 $O(n^2)$ |
2634

27-
刚才我们说到如果一定要对链表进行堆排序，则需要使用额外的数组空间。除此之外，计数排序、桶排序、基数排序都需要用到额外的数组空间。
35+
### 2.2 非比较排序算法
2836

29-
接下来，我们将对适合链表排序的 8 种算法进行一一讲解。当然，这些排序算法不用完全掌握，重点是掌握 **「链表插入排序」**、**「链表归并排序」** 这两种排序算法。
37+
| 算法 | 核心思想 | 时间复杂度 | 空间复杂度 | 适用条件 |
38+
|------|----------|------------|------------|----------|
39+
| **计数排序** | 统计频率重建 | $O(n + k)$ | $O(k)$ | 值域范围小，$k$ 为值域大小 |
40+
| **桶排序** | 分桶排序合并 | $O(n)$ | $O(n + m)$ | 数据分布均匀，$m$ 为桶数 |
41+
| **基数排序** | 按位分桶排序 | $O(n \times d)$ | $O(n + k)$ | 数字位数 $d$ 较小 |
3042

31-
## 2. 常见链表排序算法
43+
### 2.3 算法选择建议
3244

33-
链表排序常用的方法有冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序。
45+
- **小规模数据**：选择冒泡排序或插入排序
46+
- **大规模数据**：优先考虑归并排序
47+
- **特定场景**：根据数据特征选择相应的非比较排序
3448

35-
- **链表冒泡排序**：每次比较相邻两个节点的值，大的往后移。重复多次，直到链表有序。时间复杂度 $O(n^2)$，空间复杂度 $O(1)$。
36-
- **链表选择排序**：每次从未排序部分找到最小的节点，和当前节点交换。重复操作，直到链表有序。时间复杂度 $O(n^2)$，空间复杂度 $O(1)$。
37-
- **链表插入排序**：每次取一个节点，插入到已排序部分的合适位置。不断重复，直到全部节点有序。时间复杂度 $O(n^2)$，空间复杂度 $O(1)$。
38-
- **链表归并排序**：把链表分成两半，递归排序，再合并。适合链表，时间复杂度 O$(n \log n)$，空间复杂度 $O(1)$。
39-
- **链表快速排序**：选一个基准值，把小于基准的放左边，大于的放右边。对两边递归排序。时间复杂度 $O(n \log n)$，空间复杂度 $O(1)$。
40-
- **链表计数排序**：先找最大最小值，用数组统计每个值出现次数，再按顺序重建链表。适合值域不大时用。时间复杂度 $O(n + k)$，空间复杂度 $O(k)$。
41-
- **链表桶排序**：把节点分到不同的桶里，每个桶内单独排序，再合并所有桶。适合数据分布均匀时用。时间复杂度 $O(n)$，空间复杂度 $O(n + m)$。
42-
- **链表基数排序**：按个位、十位、百位等分多轮，把节点分到不同的桶里，再合并。适合数字位数不多时用。时间复杂度 $O(n \times k)$，空间复杂度 $O(n + k)$。
4349

4450
## 参考资料
4551

‎docs/02_linked_list/02_03_linked_list_bubble_sort.md

Lines changed: 61 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,29 +1,57 @@
1-
## 1. 链表冒泡排序算法描述
1+
## 1. 链表冒泡排序算法思想
22

3-
1. 使用三个指针 `node_i`、`node_j` 和 `tail`。其中 `node_i` 用于控制外循环次数，循环次数为链节点个数（链表长度）。`node_j` 和 `tail` 用于控制内循环次数和循环结束位置。
4-
2. 排序开始前，将 `node_i` 、`node_j` 置于头节点位置。`tail` 指向链表末尾，即 `None`。
5-
3. 比较链表中相邻两个元素 `node_j.val` 与 `node_j.next.val` 的值大小，如果 `node_j.val > node_j.next.val`，则值相互交换。否则不发生交换。然后向右移动 `node_j` 指针，直到 `node_j.next == tail` 时停止。
6-
4. 一次循环之后，将 `tail` 移动到 `node_j` 所在位置。相当于 `tail` 向左移动了一位。此时 `tail` 节点右侧为链表中最大的链节点。
7-
5. 然后移动 `node_i` 节点，并将 `node_j` 置于头节点位置。然后重复第 3、4 步操作。
8-
6. 直到 `node_i` 节点移动到链表末尾停止，排序结束。
9-
7. 返回链表的头节点 `head`。
3+
> **链表冒泡排序基本思想**：
4+
>
5+
> **通过相邻节点比较和交换，将最大值逐步「冒泡」到链表末尾**。
106
11-
## 2. 链表冒泡排序算法实现代码
7+
与数组冒泡排序类似，但需要处理链表的指针操作。
8+
9+
## 2. 链表冒泡排序算法步骤
10+
11+
链表冒泡排序的算法步骤如下：
12+
13+
1. **外层循环**：控制排序轮数，每轮将当前最大值「冒泡」到末尾
14+
2. **内层循环**：比较相邻节点，必要时交换值
15+
3. **尾指针优化**：每轮结束后，末尾已排序部分不再参与比较
16+
17+
```
18+
初始状态：head → 4 → 2 → 1 → 3 → null
19+
↑
20+
node_i, node_j
21+
22+
第1轮内循环：
23+
- 比较 4 和 2：4 > 2，交换 → 2 → 4 → 1 → 3 → null
24+
- 比较 4 和 1：4 > 1，交换 → 2 → 1 → 4 → 3 → null
25+
- 比较 4 和 3：4 > 3，交换 → 2 → 1 → 3 → 4 → null
26+
27+
第1轮结束：tail 指向 4，4 已排好序
28+
第2轮内循环：只在 2 → 1 → 3 范围内比较
29+
...
30+
```
31+
32+
## 3. 链表冒泡排序实现代码
1233

1334
```python
1435
class Solution:
1536
def bubbleSort(self, head: ListNode):
37+
if not head or not head.next:
38+
return head
39+
40+
# 外层循环：控制排序轮数
1641
node_i = head
17-
tail = None
18-
# 外层循环次数为 链表节点个数
42+
tail = None # 尾指针，右侧为已排序部分
43+
1944
while node_i:
20-
node_j = head
45+
node_j = head # 内层循环指针
46+
47+
# 内层循环：比较相邻节点
2148
while node_j and node_j.next != tail:
2249
if node_j.val > node_j.next.val:
23-
# 交换两个节点的值
50+
# 交换相邻节点的值
2451
node_j.val, node_j.next.val = node_j.next.val, node_j.val
2552
node_j = node_j.next
26-
# 尾指针向前移动 1 位，此时尾指针右侧为排好序的链表
53+
54+
# 更新尾指针，右侧已排好序
2755
tail = node_j
2856
node_i = node_i.next
2957

@@ -33,21 +61,31 @@ class Solution:
3361
return self.bubbleSort(head)
3462
```
3563

36-
## 3. 链表冒泡排序算法复杂度分析
64+
## 4. 链表冒泡排序算法分析
3765

38-
- **时间复杂度**：$O(n^2)$。
39-
- **空间复杂度**：$O(1)$。
66+
| 指标 | 复杂度 | 说明 |
67+
|------|--------|------|
68+
| **最佳时间复杂度** | $O(n)$ | 链表已有序，配合“提前终止”优化仅需一趟 |
69+
| **最坏时间复杂度** | $O(n^2)$ | 链表逆序，多轮遍历与相邻节点交换 |
70+
| **平均时间复杂度** | $O(n^2)$ | 一般情况下需要二重循环比较交换 |
71+
| **空间复杂度** | $O(1)$ | 原地排序，仅使用常数个指针变量 |
72+
| **稳定性** | ✅ 稳定 | 相等元素的相对次序保持不变 |
4073

41-
## 4. 总结
4274

43-
链表冒泡排序使用三个指针进行操作。`node_i` 控制外层循环次数，`node_j` 和 `tail` 控制内层循环。每次比较相邻节点的值，需要交换时就交换。每次内循环结束后，最大的节点会移动到链表末尾。
75+
**适用场景**：
4476

45-
这个算法的时间复杂度是 $O(n^2)$，因为需要进行两层循环。空间复杂度是 $O(1)$，因为只使用了固定数量的指针变量，没有使用额外空间。
77+
- **小规模数据**：节点数量 < 100
78+
- **教学演示**：理解排序算法原理
79+
- **特殊要求**：需要稳定排序且空间受限
4680

47-
链表冒泡排序适合小规模数据排序。对于大规模数据，其他排序算法可能更高效。实现时需要注意指针移动和节点交换的操作。
81+
## 5. 总结
4882

49-
## 练习题目
83+
链表中的冒泡排序是最简单的链表排序之一，通过相邻节点比较交换实现排序。虽然实现简单，但效率较低。
84+
85+
**优点**：实现简单，稳定排序，空间复杂度低
86+
**缺点**：时间复杂度高，交换次数多
5087

51-
- [0148. 排序链表](https://github.com/ITCharge/AlgoNote/tree/main/docs/solutions/0100-0199/sort-list.md)(链表冒泡排序会超时，仅做练习)
88+
## 练习题目
5289

90+
- [0148. 排序链表](https://github.com/ITCharge/AlgoNote/tree/main/docs/solutions/0100-0199/sort-list.md) (链表冒泡排序会超时，仅做练习)
5391
- [链表排序题目列表](https://github.com/ITCharge/AlgoNote/tree/main/docs/00_preface/00_06_categories_list.md#%E9%93%BE%E8%A1%A8%E6%8E%92%E5%BA%8F%E9%A2%98%E7%9B%AE)

‎docs/02_linked_list/02_04_linked_list_selection_sort.md

Lines changed: 53 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,46 +1,81 @@
1-
## 1. 链表选择排序算法描述
1+
## 1. 链表选择排序算法思想
22

3-
1. 使用两个指针 `node_i`、`node_j`。`node_i` 既可以用于控制外循环次数，又可以作为当前未排序链表的第一个链节点位置。
4-
2. 使用 `min_node` 记录当前未排序链表中值最小的链节点。
5-
3. 每一趟排序开始时，先令 `min_node = node_i`（即暂时假设链表中 `node_i` 节点为值最小的节点，经过比较后再确定最小值节点位置）。
6-
4. 然后依次比较未排序链表中 `node_j.val` 与 `min_node.val` 的值大小。如果 `node_j.val < min_node.val`，则更新 `min_node` 为 `node_j`。
7-
5. 这一趟排序结束时，未排序链表中最小值节点为 `min_node`，如果 `node_i != min_node`，则将 `node_i` 与 `min_node` 值进行交换。如果 `node_i == min_node`，则不用交换。
8-
6. 排序结束后，继续向右移动 `node_i`，重复上述步骤，在剩余未排序链表中寻找最小的链节点，并与 `node_i` 进行比较和交换，直到 `node_i == None` 或者 `node_i.next == None` 时，停止排序。
9-
7. 返回链表的头节点 `head`。
3+
> **链表选择排序基本思想**：
4+
>
5+
> 在未排序部分中找到最小元素，然后将其放到已排序部分的末尾。
106
11-
## 2. 链表选择排序实现代码
7+
## 2. 链表选择排序算法步骤
8+
9+
1. **初始化**：使用两个指针 `node_i` 和 `node_j`。`node_i` 指向当前未排序部分的第一个节点，同时也用于控制外循环。
10+
11+
2. **寻找最小值**：在未排序部分中，使用 `min_node` 记录值最小的节点。初始时假设 `node_i` 为最小值节点。
12+
13+
3. **比较交换**：遍历未排序部分，比较每个节点的值。如果发现更小的值，则更新 `min_node`。
14+
15+
4. **交换操作**：一趟排序结束后，如果 `min_node` 不等于 `node_i`，则交换两个节点的值。
16+
17+
5. **移动指针**：将 `node_i` 向右移动一位，继续处理剩余未排序部分。
18+
19+
6. **终止条件**：当 `node_i` 为 `None` 或 `node_i.next` 为 `None` 时，排序完成。
20+
21+
## 3. 链表选择排序实现代码
1222

1323
```python
1424
class Solution:
15-
def sectionSort(self, head: ListNode):
25+
def selectionSort(self, head: ListNode):
1626
node_i = head
17-
# node_i 为当前未排序链表的第一个链节点
27+
28+
# 外层循环：遍历每个节点
1829
while node_i and node_i.next:
19-
# min_node 为未排序链表中的值最小节点
30+
# 假设当前节点为最小值节点
2031
min_node = node_i
2132
node_j = node_i.next
33+
34+
# 内层循环：在未排序部分寻找最小值
2235
while node_j:
2336
if node_j.val < min_node.val:
2437
min_node = node_j
2538
node_j = node_j.next
26-
# 交换值最小节点与未排序链表中第一个节点的值
39+
40+
# 如果找到更小的值，则交换
2741
if node_i != min_node:
2842
node_i.val, min_node.val = min_node.val, node_i.val
43+
44+
# 移动到下一个节点
2945
node_i = node_i.next
3046

3147
return head
3248

3349
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
34-
return self.sectionSort(head)
50+
return self.selectionSort(head)
3551
```
3652

37-
## 3. 链表选择排序算法复杂度分析
53+
## 4. 链表选择排序算法复杂度分析
54+
55+
| 指标 | 复杂度 | 说明 |
56+
|------|--------|------|
57+
| **最佳时间复杂度** | $O(n^2)$ | 无论初始顺序如何，都需 $O(n^2)$ 次比较 |
58+
| **最坏时间复杂度** | $O(n^2)$ | 无论初始顺序如何，都需 $O(n^2)$ 次比较 |
59+
| **平均时间复杂度** | $O(n^2)$ | 比较次数与数据状态无关 |
60+
| **空间复杂度** | $O(1)$ | 原地排序，仅使用常数额外空间 |
61+
| **稳定性** | ❌ 不稳定 | 可能改变相等节点的相对次序 |
62+
63+
**适用场景**：
64+
65+
- **小规模数据**：节点数量较少的场景（如 < 100）
66+
- **对空间复杂度严格**：仅使用常数额外空间的需求
67+
- **交换代价高的场景**：选择排序交换次数少（最多 \(n-1\) 次）
68+
69+
70+
## 5. 总结
71+
72+
链表中的选择排序是一种简单直观的链表排序算法，通过在未排序部分中选择最小节点并将其放到已排序部分的末尾来完成排序。虽然实现简单，但效率较低。
3873

39-
- **时间复杂度**：$O(n^2)$。
40-
- **空间复杂度**：$O(1)$。
74+
**优点**：实现简单，空间复杂度低，交换次数少
75+
**缺点**：时间复杂度高，不稳定，不适合大规模数据
4176

4277
## 练习题目
4378

44-
- [0148. 排序链表](https://github.com/ITCharge/AlgoNote/tree/main/docs/solutions/0100-0199/sort-list.md)(链表选择排序会超时，仅做练习)
79+
- [0148. 排序链表](https://github.com/ITCharge/AlgoNote/tree/main/docs/solutions/0100-0199/sort-list.md)（链表选择排序会超时，仅做练习）
4580

4681
- [链表排序题目列表](https://github.com/ITCharge/AlgoNote/tree/main/docs/00_preface/00_06_categories_list.md#%E9%93%BE%E8%A1%A8%E6%8E%92%E5%BA%8F%E9%A2%98%E7%9B%AE)

0 commit comments

Comments
 (0)