Skip to content

Commit 2d652cd

Browse files
SnailclimbSnailclimb
committed
docs: 更新计算机基础与 Java 金额类型文档
1 parent 2c95620 commit 2d652cd

34 files changed

Lines changed: 1203 additions & 956 deletions

‎docs/.vuepress/sidebar/cs-basics.ts‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -151,9 +151,14 @@ export const csBasics = [
151151
collapsible: true,
152152
children: [
153153
{ text: "⭐️进程与线程详解", link: "process-and-thread" },
154-
{ text: "进程间通信（IPC）详解", link: "ipc" },
155154
{ text: "⭐️锁与同步机制", link: "os-lock-and-sync" },
156155
{ text: "⭐️死锁详解", link: "dead-lock" },
156+
{
157+
text: "中断、异常与系统调用",
158+
link: "interrupt-exception-syscall",
159+
},
160+
{ text: "CPU 调度与系统负载", link: "cpu-scheduling-and-load" },
161+
{ text: "进程间通信（IPC）详解", link: "ipc" },
157162
],
158163
},
159164
{

‎docs/.vuepress/sidebar/index.ts‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -84,6 +84,10 @@ export default sidebar({
8484
"reflection",
8585
"proxy",
8686
"bigdecimal",
87+
{
88+
text: "Java 金额类型选择",
89+
link: "money-long-vs-bigdecimal",
90+
},
8791
"unsafe",
8892
"spi",
8993
"syntactic-sugar",

‎docs/cs-basics/README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -73,7 +73,7 @@ head:
7373
- [进程间通信（IPC）详解：管道、消息队列、共享内存、Socket 与 Binder](./operating-system/ipc.md)：对比管道、消息队列、共享内存、Socket、Binder 等 IPC 机制。
7474
- [操作系统锁与同步机制详解：mutex、semaphore、condition variable、spinlock 与 futex](./operating-system/os-lock-and-sync.md)：讲清临界区、互斥锁、信号量、条件变量、自旋锁和 futex。
7575
- [操作系统内存管理详解：分页、分段、页面置换、Swap 与 OOM](./operating-system/memory-management.md)：讲清内存分配、内存碎片、页表、TLB、页面置换、Swap 和 OOM。
76-
- [虚拟内存详解：地址转换、TLB、缺页中断与页面置换](./operating-system/virtual-memory.md)：讲清分页、页表、TLB、缺页中断和页面置换。
76+
- [虚拟内存详解：地址转换、TLB、缺页异常与页面置换](./operating-system/virtual-memory.md)：讲清分页、页表、TLB、缺页异常和页面置换。
7777
- [操作系统文件系统详解：inode、VFS、Page Cache 与日志机制](./operating-system/file-system.md)：讲清 inode、dentry、文件描述符、VFS、Page Cache 和日志机制。
7878
- [I/O 多路复用详解：select、poll、epoll 原理与区别](./operating-system/io-multiplexing.md)：讲清 select、poll、epoll 的实现原理、性能差异和适用场景。
7979
- [零拷贝详解：mmap、sendfile 与 splice](./operating-system/zero-copy.md)：讲清传统 I/O、mmap、sendfile、splice 的拷贝路径和工程应用。

‎docs/cs-basics/algorithms/10-classical-sorting-algorithms.md‎

Lines changed: 50 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -22,25 +22,27 @@ head:
2222

2323
常见的内部排序算法有：**插入排序**、**希尔排序**、**选择排序**、**冒泡排序**、**归并排序**、**快速排序**、**堆排序**、**基数排序**等，本文只讲解内部排序算法。用一张表格概括：
2424

25-
| 排序算法 | 时间复杂度（平均） | 时间复杂度（最差） | 时间复杂度（最好） | 空间复杂度 | 排序方式 | 稳定性 |
26-
| -------- | ------------------ | ------------------ | ------------------ | ---------- | -------- | ------ |
27-
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 内部排序 | 稳定 |
28-
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 内部排序 | 不稳定 |
29-
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 内部排序 | 稳定 |
30-
| 希尔排序 | O(nlogn) | O(n^2) | O(nlogn) | O(1) | 内部排序 | 不稳定 |
31-
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 外部排序 | 稳定 |
32-
| 快速排序 | O(nlogn) | O(n^2) | O(nlogn) | O(logn) | 内部排序 | 不稳定 |
33-
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 内部排序 | 不稳定 |
34-
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 外部排序 | 稳定 |
35-
| 桶排序 | O(n+k) | O(n^2) | O(n+k) | O(n+k) | 外部排序 | 稳定 |
36-
| 基数排序 | O(n×k) | O(n×k) | O(n×k) | O(n+k) | 外部排序 | 稳定 |
25+
| 排序算法 | 时间复杂度（平均） | 时间复杂度（最差） | 时间复杂度（最好） | 空间复杂度 | 是否原地 | 稳定性 |
26+
| -------- | ------------------ | ------------------ | ------------------ | ----------------------- | -------- | -------------- |
27+
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 是 | 稳定 |
28+
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 是 | 不稳定 |
29+
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 是 | 稳定 |
30+
| 希尔排序 | 取决于增量序列 | O(n^2) | O(nlogn) | O(1) | 是 | 不稳定 |
31+
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 否 | 稳定 |
32+
| 快速排序 | O(nlogn) | O(n^2) | O(nlogn) | 平均 O(logn)，最坏 O(n) | 是 | 不稳定 |
33+
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 是 | 不稳定 |
34+
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 否 | 稳定 |
35+
| 桶排序 | 和数据分布有关 | 取决于桶内排序 | O(n+k) | O(n+k) | 否 | 取决于桶内排序 |
36+
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 否 | 稳定 |
3737

3838
**术语解释**：
3939

4040
- **n**：数据规模，表示待排序的数据量大小。
41-
- **k**：“桶” 的个数，在某些特定的排序算法中（如基数排序、桶排序等），表示分割成的独立的排序区间或类别的数量。
42-
- **内部排序**：所有排序操作都在内存中完成，不需要额外的磁盘或其他存储设备的辅助。这适用于数据量小到足以完全加载到内存中的情况。
43-
- **外部排序**：当数据量过大，不可能全部加载到内存中时使用。外部排序通常涉及到数据的分区处理，部分数据被暂时存储在外部磁盘等存储设备上。
41+
- **k**：计数范围大小或桶的数量，具体含义需要结合算法说明。
42+
- **d**：基数排序处理的最大位数。
43+
- **r**：基数排序使用的基数，例如十进制的 `r=10`。
44+
- **内部排序**：待排序数据可以全部装入内存，排序操作主要在内存中完成。本文代码都是内部排序实现。
45+
- **外部排序**：数据量大到无法全部装入内存时，借助磁盘等外部存储分批处理。同一种算法可以有内存实现，也可以被改造成外部排序方案，因此这不是算法固有的分类标签。
4446
- **稳定**：如果 A 原本在 B 前面，而 $A=B$，排序之后 A 仍然在 B 的前面。
4547
- **不稳定**：如果 A 原本在 B 的前面，而 $A=B$，排序之后 A 可能会出现在 B 的后面。
4648
- **时间复杂度**：定性描述一个算法执行所耗费的时间。
@@ -52,11 +54,11 @@ head:
5254

5355
![排序算法分类](https://oss.javaguide.cn/github/javaguide/cs-basics/sorting-algorithms/sort2.png)
5456

55-
常见的**快速排序**、**归并排序**、**堆排序**以及**冒泡排序**等都属于**比较类排序算法**。比较类排序是通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 `O(nlogn)`，因此也称为非线性时间比较类排序。在冒泡排序之类的排序中，问题规模为 `n`，又因为需要比较 `n` 次，所以平均时间复杂度为 `O(n²)`。在**归并排序**、**快速排序**之类的排序中，问题规模通过**分治法**消减为 `logn` 次，所以时间复杂度平均 `O(nlogn)`。
57+
常见的**快速排序**、**归并排序**、**堆排序**以及**冒泡排序**等都属于**比较类排序算法**。比较类排序通过比较决定元素间的相对次序。在比较模型中，通用排序在最坏情况下需要 `Ω(nlogn)` 次比较。冒泡排序需要多轮扫描，平均时间复杂度为 `O(n²)`；归并排序和快速排序利用分治把问题拆成更小的子问题，平均时间复杂度为 `O(nlogn)`。
5658

5759
比较类排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
5860

59-
而**计数排序**、**基数排序**、**桶排序**则属于**非比较类排序算法**。非比较排序不通过比较来决定元素间的相对次序，而是通过确定每个元素之前，应该有多少个元素来排序。由于它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。非比较排序只要确定每个元素之前已有的元素个数即可，所以一次遍历即可解决。算法时间复杂度 $O(n)$。
61+
而**计数排序**、**基数排序**、**桶排序**则属于**非比较类排序算法**。它们利用键值范围、数据分布或数字位数等额外信息绕开比较排序的下界，但并非都能通过一次遍历以 `O(n)` 完成。计数排序通常是 `O(n+k)`，桶排序的效率取决于数据分布和桶内排序，基数排序通常是 `O(d(n+r))`。
6062

6163
非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
6264

@@ -213,7 +215,7 @@ public static int[] insertionSort(int[] arr) {
213215

214216
## 希尔排序（Shell Sort）
215217

216-
希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为递减增量排序算法，同时该算法是冲破 $O(n^2)$ 的第一批算法之一。
218+
希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为递减增量排序算法。它的性能高度依赖增量序列：一些后来设计的增量序列可以获得亚二次上界，但本文使用的 Shell 原始增量在最坏情况下仍为 $O(n^2)$。
217219

218220
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。
219221

@@ -264,7 +266,7 @@ public static int[] shellSort(int[] arr) {
264266
### 算法分析
265267

266268
- **稳定性**：不稳定
267-
- **时间复杂度**：最佳：$O(nlogn)$，最差：$O(n^2)$，平均：$O(nlogn)$
269+
- **时间复杂度**：最佳：$O(nlogn)$，最差：$O(n^2)$，平均复杂度取决于增量序列
268270
- **空间复杂度**：$O(1)$
269271

270272
## 归并排序（Merge Sort）
@@ -318,7 +320,7 @@ public static int[] merge(int[] arr_1, int[] arr_2) {
318320
int[] sorted_arr = new int[arr_1.length + arr_2.length];
319321
int idx = 0, idx_1 = 0, idx_2 = 0;
320322
while (idx_1 < arr_1.length && idx_2 < arr_2.length) {
321-
if (arr_1[idx_1] < arr_2[idx_2]) {
323+
if (arr_1[idx_1] <= arr_2[idx_2]) {
322324
sorted_arr[idx] = arr_1[idx_1];
323325
idx_1 += 1;
324326
} else {
@@ -437,7 +439,7 @@ class Solution {
437439

438440
- **稳定性**：不稳定
439441
- **时间复杂度**：最佳：$O(nlogn)$，最差：$O(n^2)$，平均：$O(nlogn)$
440-
- **空间复杂度**：$O(logn)$
442+
- **空间复杂度**：平均 $O(logn)$，最坏 $O(n)$（递归调用栈）
441443

442444
## 堆排序（Heap Sort）
443445

@@ -606,7 +608,7 @@ public static int[] countingSort(int[] arr) {
606608

607609
- **稳定性**：稳定
608610
- **时间复杂度**：最佳：$O(n+k)$，最差：$O(n+k)$，平均：$O(n+k)$
609-
- **空间复杂度**：$O(k)$
611+
- **空间复杂度**：$O(n+k)$
610612

611613
## 桶排序（Bucket Sort）
612614

@@ -655,7 +657,10 @@ private static int[] getMinAndMax(List<Integer> arr) {
655657
* @return
656658
*/
657659
public static List<Integer> bucketSort(List<Integer> arr, int bucket_size) {
658-
if (arr.size() < 2 || bucket_size == 0) {
660+
if (bucket_size <= 0) {
661+
throw new IllegalArgumentException("bucket_size must be positive");
662+
}
663+
if (arr.size() < 2) {
659664
return arr;
660665
}
661666
int[] extremum = getMinAndMax(arr);
@@ -672,7 +677,7 @@ public static List<Integer> bucketSort(List<Integer> arr, int bucket_size) {
672677
}
673678
for (int i = 0; i < buckets.size(); i++) {
674679
if (buckets.get(i).size() > 1) {
675-
buckets.set(i, sort(buckets.get(i), bucket_size / 2));
680+
buckets.get(i).sort(Integer::compareTo);
676681
}
677682
}
678683
ArrayList<Integer> result = new ArrayList<>();
@@ -687,13 +692,13 @@ public static List<Integer> bucketSort(List<Integer> arr, int bucket_size) {
687692

688693
### 算法分析
689694

690-
- **稳定性**：稳定
691-
- **时间复杂度**：最佳：$O(n+k)$，最差：$O(n^2)$，平均：$O(n+k)$
695+
- **稳定性**：取决于桶内排序。当前实现按原顺序入桶，并使用稳定的 `List.sort`，因此是稳定的
696+
- **时间复杂度**：当前实现最佳为 $O(n+k)$；数据均匀分布时，期望接近 $O(n+k)$；最坏为 $O(nlogn+k)$。如果桶内改用插入排序，最坏情况会退化到 $O(n^2)$
692697
- **空间复杂度**：$O(n+k)$
693698

694699
## 基数排序（Radix Sort）
695700

696-
基数排序也是非比较的排序算法，对元素中的每一位数字进行排序，从最低位开始排序，复杂度为 $O(n×k)$，$n$ 为数组长度，$k$ 为数组中元素的最大的位数；
701+
基数排序也是非比较的排序算法，对元素中的每一位数字进行排序，从最低位开始排序。设数组长度为 $n$、最大位数为 $d$、基数为 $r$，复杂度为 $O(d(n+r))$。下面的十进制 LSD 实现仅支持非负整数。
697702

698703
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
699704

@@ -722,6 +727,11 @@ public static int[] radixSort(int[] arr) {
722727
if (arr.length < 2) {
723728
return arr;
724729
}
730+
for (int element : arr) {
731+
if (element < 0) {
732+
throw new IllegalArgumentException("radixSort only supports non-negative integers");
733+
}
734+
}
725735
int N = 1;
726736
int maxValue = arr[0];
727737
for (int element : arr) {
@@ -756,8 +766,8 @@ public static int[] radixSort(int[] arr) {
756766
### 算法分析
757767

758768
- **稳定性**：稳定
759-
- **时间复杂度**：最佳：$O(n×k)$，最差：$O(n×k)$，平均：$O(n×k)$
760-
- **空间复杂度**：$O(n+k)$
769+
- **时间复杂度**：最佳、最差、平均均为 $O(d(n+r))$
770+
- **空间复杂度**：$O(n+r)$
761771

762772
**基数排序 vs 计数排序 vs 桶排序**
763773

@@ -777,17 +787,17 @@ public static int[] radixSort(int[] arr) {
777787

778788
排序算法面试一般不会要求你把 10 种排序全部手写，但复杂度、稳定性、原地排序和适用场景要能说清。
779789

780-
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 是否原地 |
781-
| -------- | -------------- | -------------- | ---------- | -------------- | -------- |
782-
| 冒泡排序 | `O(n^2)` | `O(n^2)` | `O(1)` | 稳定 | 是 |
783-
| 选择排序 | `O(n^2)` | `O(n^2)` | `O(1)` | 不稳定 | 是 |
784-
| 插入排序 | `O(n^2)` | `O(n^2)` | `O(1)` | 稳定 | 是 |
785-
| 归并排序 | `O(nlogn)` | `O(nlogn)` | `O(n)` | 稳定 | 否 |
786-
| 快速排序 | `O(nlogn)` | `O(n^2)` | `O(logn)` | 不稳定 | 是 |
787-
| 堆排序 | `O(nlogn)` | `O(nlogn)` | `O(1)` | 不稳定 | 是 |
788-
| 计数排序 | `O(n+k)` | `O(n+k)` | `O(n+k)` | 稳定 | 否 |
789-
| 桶排序 | 和数据分布有关 | `O(n^2)` | `O(n+k)` | 取决于桶内排序 | 否 |
790-
| 基数排序 | `O(nk)` | `O(nk)` | `O(n+k)` | 稳定 | 否 |
790+
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 是否原地 |
791+
| -------- | -------------- | -------------- | --------------------------- | -------------- | -------- |
792+
| 冒泡排序 | `O(n^2)` | `O(n^2)` | `O(1)` | 稳定 | 是 |
793+
| 选择排序 | `O(n^2)` | `O(n^2)` | `O(1)` | 不稳定 | 是 |
794+
| 插入排序 | `O(n^2)` | `O(n^2)` | `O(1)` | 稳定 | 是 |
795+
| 归并排序 | `O(nlogn)` | `O(nlogn)` | `O(n)` | 稳定 | 否 |
796+
| 快速排序 | `O(nlogn)` | `O(n^2)` | 平均 `O(logn)`，最坏 `O(n)` | 不稳定 | 是 |
797+
| 堆排序 | `O(nlogn)` | `O(nlogn)` | `O(1)` | 不稳定 | 是 |
798+
| 计数排序 | `O(n+k)` | `O(n+k)` | `O(n+k)` | 稳定 | 否 |
799+
| 桶排序 | 和数据分布有关 | 取决于桶内排序 | `O(n+k)` | 取决于桶内排序 | 否 |
800+
| 基数排序 | `O(d(n+r))` | `O(d(n+r))` | `O(n+r)` | 稳定 | 否 |
791801

792802
几个高频追问：
793803

0 commit comments

Comments
 (0)