%%
# 纲要
> 主干纲要、Hint/线索/路标
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
# 正文
%%
%%
# 字典序（Lexicographical Order）
**字典序比较结果**：
- 结果 = 两个字符串中 "**从左到右首个不相同的字符**" 的比较结果（**取 ASCII 码比较**）
- 若**一个字符串为另一字符串前缀**，则**较短字符串==较小==**，**较长字符串==较大==**。
> [!NOTE] `strcmp` 即是执行字典序比较，一个自实现版本如下：
>
> ```cpp
> int strcmp(const char *s1, const char *s2) {
> // 0: eq; -1: s1 < s2; 1: s1 > s2;
> // 字典序比较
> for (; *s1 && (*s1 == *s2); ++s1, ++s2);
> return *(unsigned char*) s1 - *(unsigned char*) s2;
> }
> ```
>
> [!example] `"b" > "abc" > "ab"`， `"sigh" < "sight", "a < ab"`
假设只删除一个字母, 使得删除后的字符串字典序最小, 如何删除?
=> 尽可能把"小"的字符放前面, 找到首个降序位置(i,i+1), 有s[i]>s[i+1], 删除s[i], 即得到最小字典序.
%%
# 排序总结
排序算法可分为两类[^2]：
- **比较型排序**——**通过比较**来决定元素间的相对次序，其时间复杂度上限为 $O(n\log n)$。
- **非比较型排序**——**不通过比较**来决定元素间的相对次序，以线性时间运行，也称 "**线性时间排序**"。
| 排序算法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最优） | 空间复杂度 | 稳定性 |
| ---- | -------------------------------------------- | -------------------------------------------- | -------------------------------------------- | ----------------------------------------------------------------------------------------- | --- |
| 插入排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | ✔️ |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | ❌ |
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | ✔️ |
| | | | | | |
| 归并排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ | ✔️ |
| 快速排序 | $O(n\log n)$ | $O(n^2)$ | $O(n\log n)$ | $O(\log n)$ ~ $O(n)$ | ❌ |
| 堆排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(1)$ | ❌ |
| | | | | | |
| 计数排序 | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | ✔️ |
| 基数排序 | $O((n+r)\cdot K)$ | $O((n+r)\cdot K)$ | $O((n+r)\cdot K)$ | $O(n+r)$ | ✔️ |
| 桶排序 | $O\left( n+n\log{\large\frac{n}{k}} \right)$ | $O\left( n+n\log{\large\frac{n}{k}} \right)$ | $O\left( n+n\log{\large\frac{n}{k}} \right)$ | $O \left( n+k+\log\large \frac{n}{k} \right)$ ~ $O \left( n+k+\large \frac{n}{k} \right)$ | ❓ |
> [!NOTE] 备注——上表变量含义
>
> - 对所有排序， $n$ 是元素数量；
> - 对**计数排序**：$k$ 是数据**值域范围大小**；
> - 对**基数排序**：$K$ 是元素**数值的 "最大位数"** ；$r$ 是基数（**进制数**），例如十进制下即为常量 10。
> - 对**桶排序**：$k$ 是桶的数量；
>
> 注意，桶排序的时/空间复杂度及稳定性取决于 "桶内排序算法"，上表值以 "快排" 为例。
> [!info] 排序算法的 "**稳定性**" 是指：**两个具有相等值的元素**，在排序前后**其相对位置保持不变**。
> [!summary] 总结
>
> - 三种简单排序，平均时间复杂度均为 $O(n^2)$，其中**冒泡/插入排序**最好情况下是 $O (n)$；
> - 三种 $O(n\log n)$ 排序，只有**快排**最坏情况为 $O(n^2)$。
> - **稳定排序**：插入、冒泡、归并、计数、基数排序。
<br><br>
# 选择排序
思路：每一轮从**未排序序列**中选择**最小值**，然后与**当前轮的起始位置**的元素交换。
即对于下标 $i\in[0, n-1)$，**每次找出剩余范围 $j\in[i, n)$ 中的最小值下标，交换至位置 $i$**。
- 时间复杂度：$O(n^2)$，最优/平均/最坏均一样。
- 空间复杂度：$O(1)$
- 稳定性：❌ **当前轮起始位置的元素 A**会与选出的最小值 M 交换，这一步可能**破坏 A 与其后方等值元素 A' 的相对位置**（若 M 在 A'后方）
- 例如 `[(5,A),(3,B),(5,C),(2,D))`，第一轮选出 `(2,D)` 与 `(5,A)` 交换，则破坏了后者与 `(5,C)` 的相对位置
```cpp
// 选择排序. 任何情况都是O(n^2).
void SelectSort(vector<int> &nums) {
int n = nums.size();
for (int i = 0; i < n - 1; ++i) { // 每轮排序确定下标位置i上的正确元素, 共需n-1轮.
int min_idx = i;
for (int j = i + 1; j < n; ++j) {
if (nums[j] < nums[min_idx]) {
min_idx = j;
}
}
swap (nums[i], nums[min_idx]);
}
}
```
<br>
# 插入排序
思考：每一轮将 "**未排序序列起始元素**" 插入到 "**已排序序列**" 中恰当位置。
即**对下标 $i\in[1,n)$ 处的元素，将其 "==插入==" 到前方合适位置**。
- 时间复杂度：$O(n^2)$，最优/平均/最坏均一样。
- 空间复杂度：$O(1)$
- 稳定性：✔️ 向前查找 `nums[i]` 插入位置时，**若遇见等值元素，会将其插入到后方**。
- 注：🚨 如果将代码里的 `>` 改为 `>=`，即相等时也后移，就不稳定了。
```cpp
void InsertSort(vector<int> &nums) {
int n = nums.size();
for (int i = 1; i < n; ++i) {
int val = nums[i];
int j = j - 1; // j指向待检查的元素.
while (j >= 0 && nums[j] > val) { // nums[j]比val大
nums[j + 1] = nums[j]; // 将nums[j]后移
--j;
}
nums[j + 1] = val;
}
}
```
<br>
# 冒泡排序
思路（升序）：**每一轮从下标 0 起始，以==两两相邻元素交换==的方式，将较大元素后移**。第 $i$ 轮结束后，会将**倒数第 $i$ 大的元素放置 $n-i$ 下标位置，故共需 n-1 轮。**
- 时间复杂度：
- 平均/最坏为 $O(n^2)$；
- 最优为 $O(n)$ ：带 "flag" 时，若有序则遍历一趟后 break。
- 空间复杂度：$O(1)$
- 稳定性：✔️ **当两个元素相等时，==不会执行交换操作==**。
- 注：🚨 如果将代码里的 `>` 改为 `>=`，即相等时也交换，就不稳定了。
```cpp
// 冒泡排序
void BubbleSort(vector<int> arr) {
int n = arr.size();
for (int i = n - 1; i > 0; --i) { // 此轮冒泡将确定元素arr[i].
bool swapped = false;
for (int j = 0; j < i; ++j) { // 此轮冒泡范围: [0, i]
if (arr[j] > arr[j+1]) { // 严格"大于", 故排序是稳定的.
swap(arr[j], arr[j+1]);
swapped = true;
}
}
if (!swapped) break;
}
}
```
<br><br>
# 快速排序
### 快排的基本思想
快排算法的基本思想（即「**单路快排**」）如下：
1. 从**剩余待排序区间 `[l, r]`** 中**选取一项元素**作为「**轴/支点`pivot`**」；
2. **将 `pivot` 放置到 "==整个数组排序后，其应当位于的正确下标位置`pivot_idx`处=="**，并且**以 `pivot_idx` 作为分割点，将区间 `[l, r]` 拆分成`<=val` 和 `>val`（或`<val` 和`>=val`）的两部分区间 `[l, pivot_idx-1], [pivot_idx+1, r]`**；
3. **递归地对这两个剩余区间分别进行排序**。
上述过程概括为三步：
1. 「**选取轴点/基准值 pivot**」
2. 「**基于 pivot 进行分区（Parition)**」
3. 「**对剩余待排序区间递归排序**」
其中，"**==尽可能均等地划分区间==**" 是影响快排效率的关键。
#### 复杂度分析
| | 最好 | 平均 | ==最坏== |
| ----- | ------------ | ------------ | -------- |
| 时间复杂度 | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ |
| 空间复杂度 | $O(\log n)$ | $O(\log n)$ | $O(n)$ |
> [!danger] **最坏情况**
>
> 每次选取的**基准值`pivot`** 都是 **==剩余待排序区间中的最大或最小值==** 时，
> **`Partition`划分出的其中一个是==空区间==**，**另一个区间即是==整个剩余待排序区间==**，
> 时间开销 **退化为最坏的 $O(n^2)$**，递归深度为 $n$。
### 单路快排的缺点
由于 "**单路 `Partition`**" 是将区间 `[l, r]` 划分成 **`<=val` 和 `>val`（或`<val` 和`>=val`）的两部分**，
因此如果 **==数组中存在大量重复值==**，当这一值**被选为`pivot`** 时，会导致执行`Partition` 后==**分区不平衡**==，即"**==重复值全都堆积到其中一侧区间==**"，进而**降低执行效率**。
最坏情况下，**==数组元素全部相同==时**，**每次 `Partion` 后都将会得到==一个空区间==和==整个待排序剩余区间==**，此时排序的时间开销 **退化为最坏的 $O(n^2)$**。
### 快排的不同变种
快速排序有如下几个变种：
- **单路快排**（最基本的快排）
- `Partition` 将**剩余待排序区间 `[l, r]`** 划分成 **`<= pivot` 和 `> pivot`**（或 `< pivot` 和 `>= pivot` ）的**两部分**：`[l, pivot_idx-1], [pivot_idx+1, r]`
- **双路快排**
- `Partition` 将**剩余待排序区间 `[l, r]`** 划分成 **`<= pivot` 和 `>= pivot`** 的**两部分**：`[l, pivot_idx-1], [pivot_idx+1, r]`，**尝试让 `pivot` 的相同值均等分布于两区间中**。
- **三路快排** ⭐
- `Partition` 将**剩余待排序区间 `[l, r]`** 划分成**三部分**：
- ` < pivot` 的区间 `[l, lt)`；
- `== pivot` 的区间 `[lt, gt]`；
- ` > pivot` 的区间 `(gt, r]`;
- 递归排序时，**只对剩余待排序区间 `[l, lt-1]` 与 `[gt+1, r]` 进行**。
为解决当序列中存在 "**==大量重复值==**" 时 "**单路快排**" 的**效率退化问题**，衍生出了**双路快排**、**三路快排**变种。其中，**三路快排** 效果最优。
> [!caution] 双路、三路快排只解决 "**==存在大量重复值==**" 时的效率退化问题
>
> 对于双路、三路快排，**如果每次选中的 `pivot` 都是==剩余待排序区间中的 "最值"==** ，则**时间开销仍然会退化为最坏情况 $O(n^2)$**。
> [!FAQ] ❓ <font color="#c00000">单路快排、双路快排，三路快排的核心差异是什么？</font>
>
> 唯一差异即在于 **"`Partition`" 的处理逻辑不同**，其余均相同。
> [!example]
> 原始序列 `[5, 3, 8, 5, 2, 5, 7, 5]`，三种版本 **首次 `Partition`** 后的分区如下：
>
> - **单路快排**（取 `pivot` 为末尾元素 `5`）：`[5, 3, 5, 2, 5] *5* [8, 7]`
> - **双路快排**（取 `pivot` 为首项元素 `5`）：`[2, 3, 5, 5] *5* [5, 7, 8]`
> - **三路快排**（取 `pivot` 为首项元素 `5`）：`[3, 2] 5 5 5 5 [7, 8]`
<br><br>
## 单路快排
###### 核心思想
- `Partition`：**将下标 `pivot_idx` 处的元素 `val` 放置到 "==整个数组排序后，其应当位于的下标位置=="**，并且将**剩余待排序区间 `[l, r]`** 划分成 **`<= pivot` 和 `> pivot`**（或 `< pivot` 和 `>= pivot` ）的**两部分**：`[l, pivot_idx-1], [pivot_idx+1, r]`
#### 单路 `Partition` 的三种实现
- **基于单层 for 循环的双指针实现（交换元素）**
- **基于双层 while 循环的双指针实现（==交换==元素的写法）**
- **基于双层 while 循环的双指针实现（==覆盖==元素的写法）**
###### （1）**基于单层 for 循环的实现**
- 思路：双指针，将 `<=pivot` 的元素都 "**交换**" 到序列前段
- 取区间 `[l, r]` 的**末尾元素`arr[r]`为 `pivot`**
- 循环不变量：
- `i` 指向 "**下一个待插入 `<=pivot` 的元素的位置**" ，
- `j` 指向 "**剩余待处理区间`[j, r-1]`的头部**"，
- `[l, i)` 为`<=pivot`的区间；
- `[i, j)` 为 `>pivot` 的区间；
- 循环结束后：
- 交换 `arr[i]` 与 `arr[r]`，返回 `i` 即为排序后的 `pivot_idx`。
```cpp
int PartitionV1(vector<int>& arr, int l, int r, int pivot_idx) {
swap(arr[r], arr[pivot_idx]); // 最后一项为 r.
int pivot = arr[r];
int i = l;
for (int j = l; j < r; ++j) {
if (arr[j] <= pivot) {
swap(arr[i++], arr[j]);
}
}
swap(arr[i], arr[r]);
return i;
}
```
###### （2）**基于双层 while 循环的实现（交换元素的写法）**
循环不变量：
- 双指针 `i` 和 `j` 分别指向 "**剩余待搜索区间**" 的**头尾**，**相向移动**；
- 区间 `[i, j]` 为 **剩余待搜索区间**；
- **区间 `[l, i)`与`(j, r]` 的含义可以是以下三种组合**，取决于**两个内层 `while` 循环里`arr[i]` 和`arr[j]` 与 `pivot` 比较时的判断逻辑**：
- **`<=pivot` 与 `>pivot` 的元素**；
- **`<pivot` 与 `>=pivot` 的元素**；
- **`<=pivot` 与 `>=pivot` 的元素**（**即==双路快排==的写法**）
- （不能是`<pivot` 与 `>pivot`，会导致死循环，无法处理`==pivot`的情况）
**`pivot` 既可以取区间==首项==元素 `arr[l]`，也可以取==尾部==元素 `arr[r]`**：
- 若取首项 `arr[l]`，则最后需要 **`swap(arr[l], arr[j])`**，
**保证交换到位置 `l` 的是 `<=pivot` 的元素`arr[j]`**；
- 若取尾部 `arr[r]`，则最后需要 `swap(arr[r], arr[i])`，
**保证交换到位置 `r` 的是 `>=pivot` 的元素 `arr[i]`**；
```cpp
// 双指针, 交换的写法.
// 区间[l, i)为 `<pivot`或`<=pivot`的元素,
// 区间(j, r]为 `>pivot`或`>=pivot`的元素.
// 两个区间不能分别是`<pivot` 和 `>pivot`, 否则无法处理重复值, 存在死循环.
// 除此以外的三种组合都可, 取决于两个内层while循环的判断逻辑.
// pivot可以取首项arr[l]或末尾arr[r].
// - 如果取首项arr[l]为pivot, 则最后需要swap(arr[l], arr[j]), 因为arr[j]<=pivot.
// - 如果取尾项arr[r]为pivot, 则最后需要swap(arr[r], arr[i]), 因为arr[i]>=pivot.
int PartitionV2_l_as_pivot(vector<int>& arr, int l, int r, int pivot_idx) {
// 以arr[l]为pivot, 最后swap(arr[l], arr[j]);
swap(arr[l], arr[pivot_idx]);
int pivot = arr[l];
int i = l + 1, j = r;
while (i <= j) {
while (i <= j && arr[i] <= pivot) ++i; // 指向>pivot的元素.
while (i <= j && arr[j] > pivot) --j; // 指向<pivot的元素.
if (i > j) break;
swap(arr[i++], arr[j--]);
}
swap(arr[l], arr[j]);
return j;
}
int PartitionV2_r_as_pivot(vector<int>& arr, int l, int r, int pivot_idx) {
// 以arr[r]为pivot, 最后swap(arr[r], arr[i]).
swap(arr[r], arr[pivot_idx]);
int pivot = arr[r];
int i = l, j = r - 1;
while (i <= j) {
while (i <= j && arr[i] <= pivot) ++i;
while (i <= j && arr[j] > pivot) --j;
if (i > j) break;
swap(arr[i++], arr[j--]);
}
swap(arr[r], arr[i]);
return i;
}
```
###### （3）**基于双层 while 循环的实现（覆盖元素的写法）**
```cpp
int PartitionV3_l_as_pivot(vector<int> &arr, int l, int r, int pivot_idx) {
// 以arr[l], 每轮循环要先找到一个arr[j]来覆盖arr[i], 再找到arr[i']来覆盖arr[j]
int pivot = arr[l];
int i = l, j = r;
while (i < j) {
while (i < j && arr[j] > pivot) --j; // 找到<=pivot的.
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) ++i; // 找到>pivot的
arr[j] = arr[i];
}
arr[i] = pivot;
return i;
}
int PartitionV3_r_as_pivot(vector<int> &arr, int l, int r, int pivot_idx) {
// 以arr[r]为pivot, 每轮循环要先找到一个arr[i]来覆盖arr[j], 再找到arr[j']来覆盖arr[i]
int pivot = arr[r];
int i = l, j = r;
while (i < j) {
while (i < j && arr[i] <= pivot) ++i; // 找到>pivot的
arr[j] = arr[i];
while (i < j && arr[j] > pivot) --j; // 找到<=pivot的.
arr[i] = arr[j];
}
arr[i] = pivot;
return i;
}
```
<br><br>
## 双路快排
###### 核心思想
- `Partition` ：**将下标 `pivot_idx` 处的元素 `val` 放置到 "==整个数组排序后，其应当位于的下标位置=="**，同时**剩余待排序区间 `[l, r]`** 划分成 **`<= pivot` 和 `>= pivot`** 的**两部分**：
`[l, pivot_idx-1], [pivot_idx+1, r]`，**尝试让 `pivot` 的相同值均等分布于两区间中**。
###### 具体实现
- 取**区间首项** `arr[l]` 作为 `pivot`，**==`arr[l]` 最后需要与一项 `<=pivot`的元素交换==**。
- **循环不变量**：
- 双指针 `i` 和 `j` 分别指向 "**剩余待搜索区间**" 的**头尾**，**相向移动**；
- 初始化：`i==l+1`，`j==r`
- **剩余待搜索区间**为 `[i, j]`
- **区间 `[l, i)`** 为 `<= pivot` 的元素；
- **区间 `(j, r]`** 为 `>= pivot` 的元素；
- 循环条件： `while (i<=j)` ，**剩余待搜索区间不为空**；
- 循环逻辑：
- `i` 移动到下一个 `>= pivot` 的元素或越界；
- `j` 移动到下一个 `<= pivot` 的元素或越界；
- 检查`i` 、`j` 是否越界：
- 若 `i > j`，说明 "**剩余待处理空间为 0**" ，跳出循环。
- 交换 `arr[i]` 和 `arr[j]`，随后 `i++` 和 `--j`。
- 循环外：`(j, r]` 区间是 `>=pivot`的元素，而 `j` 指向必然是最后一个 `<= pivot` 的元素，因此**应当==将 `arr[l]` 与 `arr[j]` 交换==**。
> [!NOTE] 与单路快排的差异
>
> 当 `i` 和 `j` 指向的**元素值相同**（`i!=j`）时，**同时跳过两个等值元素**，
> 即**相当于将两个等值元素==分别放置==在了`[l,i)` 和 `(j,r]` 两区间中**，
> 从而**尽可能地 "让相等值均等分布于两区间**"。
###### `Partition` 示意图
![[Excalidraw-Solution/排序算法_0.excalidraw.svg|550]]
%%[[Excalidraw-Solution/排序算法_0.excalidraw.md|🖋 Edit in Excalidraw]]%%
```cpp
/* 双路快排
*
* 思路: 让等于pivot的元素尽可能均衡地分布在划分出的两个分区中.
* => 与pivot的同值的元素, 在pivot_idx两侧近似均衡分布.
*
* 循环不变量:
* - 双指针i和j分别指向"剩余待搜索区间" 的首、尾, 相向移动.
* - 初始化 i = l+1, j = r;
* - 区间[l, i)的元素都 ≤ pivot。
* - 区间(j, r]的元素都是 ≥ pivot。
* - 区间[i，j]中的元素是"尚未被检查或确定位置"的。
* 循环体逻辑:
* - `i` 移动到首个 `>= pivot` 的元素或越界；
* - `j` 移动到首个 `<= pivot` 的元素或越界；
* - 若i和j未越界(i<=j), 则 swap(arr[i++], arr[j--]);
* i > j 时, 剩余待搜索空间为空,
* 此时(j,r]中元素>=pivot, 而j必然指向"<=pivot"的元素, 因此将pivot==arr[l]与arr[j]交换.
*
* 由于当 arr[i]==arr[j]==pivot且i!=j时, i和j都会相向移动一步,
* 相当于将两个等值元素分别放置在了[l,i)和(j, r]两区间中,
* 从而尽可能"让相等值均等分布于两区间".
*/
// 双路快排
class TwoWayQuickSort {
private:
static int Partition(std::vector<int> &arr, int l, int r, int pivot_idx);
static void QuickSort(std::vector<int> &arr, int l, int r);
public:
static void QuickSort(std::vector<int> &arr);
};
int TwoWayQuickSort::Partition(vector<int> &arr, int l, int r, int pivot_idx) {
// 将pivot交换到头部.
swap(arr[l], arr[pivot_idx]);
int pivot = arr[l];
int i = l + 1, j = r;
while (i <= j) {
while (i <= j && arr[i] < pivot) ++i; // 直到指向一个>=pivot的元素, 或者越界;
while (i <= j && arr[j] > pivot) --j; // 直到指向一个<=pivot的元素, 或者越界.
if (i > j) break; // i和j越界, 无效, 剩余待搜索空间为空.
swap(arr[i++], arr[j--]);
}
swap(arr[l], arr[j]); // 将pivot放置到正确位置.
return j; // 返回更新后的pivot_indx.
}
void TwoWayQuickSort::QuickSort(vector<int> &arr, int l, int r) {
if (l >= r) return;
int pivot_idx = l + rand()%(r-l+1); // arr[l..r]范围中随机选择一个作为pivot
pivot_idx = Partition(arr, l, r, pivot_idx);
QuickSort(arr, l, pivot_idx - 1);
QuickSort(arr, pivot_idx + 1, r);
}
void TwoWayQuickSort::QuickSort(vector<int> &arr) {
srand(time(nullptr)); // 初始化随机种子
QuickSort(arr, 0, arr.size() - 1);
}
```
<br><br>
## 三路快排 ⭐
#### **核心思想**
- `Partition`：**将==值为 pivot 的所有元素==放置到 "==整个数组排序后，其应当位于的下标位置=="**，同时**将区间 `[l, r]` 分成如下三个部分**，返回值`==pivot`的==**区间边界 {lt, gt}**==`
- ` < pivot` 的区间 `[l, lt)`；
- `== pivot` 的区间 `[lt, gt]`；
- ` > pivot` 的区间 `(gt, r]`;
- 递归排序时，**==跳过 `==pivot`的部分==**，**只对两侧剩余区间 `[l, lt-1]` 与 `[gt+1, r]` 排序**。
###### `Partition` 示意图
![[Excalidraw-Solution/排序算法_1.excalidraw.svg|600]]
%%[[Excalidraw-Solution/排序算法_1.excalidraw.md|🖋 Edit in Excalidraw]]%%
#### 具体实现
##### 三路 `Partition` 实现
`Partition` 的实现即 "**荷兰国旗算法（三指针）**"，参见 [[00-数据结构与算法笔记/专题总结/双指针#示例二：将区间`[l, r]`内元素依次分成 `<val`、`==val`、`>val` 的三段|双指针]]
```cpp
pair<int, int> ThreeWayPartition(vector<int>& arr, int l, int r, int pivot_idx) {
int pivot = arr[pivot_idx];
int lt = l, gt = r, i = l;
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr[i++], arr[lt++]);
} else if (arr[i] > pivot) {
swap(arr[i], arr[gt--])
} else {
++i;
}
}
return {lt, gt};
}
```
对 "**==索引数组==**" 进行排序（**值相同时，判定下标小的为较小元素**）时，三路 `Partition` 如下：
- `pivot_idx` 取得的是 `idx` 数组中的下标；
- `ori_pivot_idx` 是 `idx[pivot_idx]`，即**原数组中==作为 pivot 的元素值的下标==**；
- `pivot` 是 `nums[ori_pivot_idx]` ，即**原数组中==作为 pivot 的元素值==**
需要用一个额外变量 `ori_pivot_idx` 来记录**原数组中作为 pivot 的元素值的下标**。
```cpp
// 对idx进行排列, 被排列元素为 idx[i], 而比较时的取值是len1[idx[i]].
pair<int, int> ThreeWayPartitionForIndexArr(
vector<int>& nums, vector<int>& idx, int l, int r, int pivot_idx) {
int pivot_idx = l + rand()%(r-l+1); // idx中的下标
int ori_pivot_idx = idx[pivot_idx]; // 原数组中作为pivot的元素的下标.
int pivot = nums[ori_pivot_idx]; // 原数组中作为pivot的元素值
while (i <= gt) {
if (nums[idx[i]] < pivot || nums[idx[i]] == pivot && idx[i] < ori_pivot_idx) {
swap(idx[i++], idx[lt++]);
} else if (nums[idx[i]] > pivot || nums[idx[i]] == pivot && idx[i] > ori_pivot_idx) {
swap(idx[i], idx[gt--]);
} else {
++i;
}
return {lt, gt};
}
```
##### 三路快排完整实现
```cpp
/** 三路快排
*
* Partition: 将[l,r]分成三部分:
* - ` <pivot`的部分: [l, lt)
* - `==pivot`的部分: [lt, gt]
* - ` >pivot`的部分: (gt, r].
* 返回 {lt, gt}.
*/
class ThreeWayQuickSort {
private:
// Partition: 将[l,r]分成三部分: [l, lt)区间`<pivot`, [lt, gt]区间`==pivot`, (gt, r]区间`>pivot`.
static std::pair<int, int> Partition(std::vector<int> &arr, int l, int r, int pivot_idx);
static void QuickSort(std::vector<int> &arr, int l, int r);
public:
static void QuickSort(std::vector<int> &arr);
};
pair<int, int> ThreeWayQuickSort::Partition(
vector<int> &arr, int l, int r, int pivot_idx) {
int pivot = arr[pivot_idx]; // 轴元素
int lt = l; // lt指向"待插入下一个<pivot的元素的位置"
int gt = r; // gt指向"待插入下一个>pivot的元素的位置"
int i = l; // i指向剩余待处理区间的头部.
while (i <= gt) { // 区间[i, gt]为剩余待搜索区间. 循环条件即为该区间非空.
if (arr[i] < pivot) {
// 由于[lt, i)区间全为==val的元素, 所以交换到位置i的就是val值.
// 因此同时后移 lt 和 i.
swap(arr[i++], arr[lt++]);
} else if (arr[i] > pivot) {
swap(arr[i], arr[gt--]);
} else {
++i;
}
}
return {lt, gt};
}
void ThreeWayQuickSort::QuickSort(vector<int> &arr, int l, int r) {
if (l >= r) return;
// 获取一个随机pivot_idx.
int pivot_idx = l + rand()%(r-l+1);
// [p.first, p.second]即[lt, gt]为 `==arr[pivot_idx]`的区间.
auto p = Partition(arr, l, r, pivot_idx);
QuickSort(arr, l, p.first - 1); // 递归对[l, lt)部分排序
QuickSort(arr, p.second + 1, r); // 递归对(gt, r]部分排序
}
void ThreeWayQuickSort::QuickSort(vector<int> &arr) {
srand(time(nullptr)); // 初始化随机种子
QuickSort(arr, 0, arr.size() - 1);
}
```
<br><br><br>
# Quick-Select 快速选择算法
> 基于快速排序中 `Partition` 功能的算法。
![[Excalidraw-Solution/排序算法_2.excalidraw.svg|600]]
%%[[Excalidraw-Solution/排序算法_2.excalidraw.md|🖋 Edit in Excalidraw]]%%
### Quick-Select 算法的作用
`QuickSelect(arr, k)`：**给定下标 `k` 位置**，**==重排序列==** 使得：
1. **下标位置 `k` 处的元素**即为"**整个数组完全排序后==该位置上所应有的元素==**"；
2. **位置 `k` 之前的元素都 `<=arr[k]`**，**且位置 `k` 之后的元素都 `>=arr[k]`**。
**常用于**：**找出数组中==第 k 大/小的元素==；获取数组中==最大/最小的 k 个数==**（平均 $O(n)$，最坏 $O(n^2)$ ）
### Quick-Select 算法过程
> 与快排一样，**三路 Partition 能够解决存在大量重复值时的效率退化问题**。
> 如果**不存在重复值**（或者**值相同时比较下标**），用单路 Partition 即可。
#### 三路 Partition
1. 随机选取一个**轴点 pivot**
2. 基于轴点对剩余待处理区间`[l, r]`进行**分区**（ 三路`Partition`）
- 将 `pivot` 放置于 "**整个数组完全排序后，其应当位于的==位置==`pivot_idx`上**"，
- 同时将剩余区间 `[l, r]` 划分为三部分，返回边界下标 `{lt, gt}`
- `< pivot` 的区间 `[l, lt)`；
- `==pivot` 的区间`[lt, gt]`;
- `> pivot` 的区间 `(gt, r]`
3. **检查目标下标 `k` 所位于的区间**：
- 若 `k >= lt && k <= gt`，则结束；
- 若 `k < lt`，则递归地对区间 `[l, lt-1]` 重复上述过程；
- 若 `k > gt`，则递归地对区间 `[gt+1, r]` 重复上述过程；
4. 返回下标位置 `k` 处的元素 `arr[k]`
#### 单路 Parition
1. 随机选取一个**轴点 pivot**
2. 基于轴点对剩余待处理区间`[l, r]`进行**分区**（ `Partition`）
- 将 `pivot` 放置于 "**整个数组完全排序后，其应当位于的==位置==`pivot_idx`上**"，同时 `pivot_idx` 将整个数组划分为 `<=pivot`，`>pivot`的两部分区间：`[l, pivot_idx-1], [pivot_idx+1, r]`**，返回位置下标`pivot_idx`**
3. 检查 `pivot_idx` 是否为 `k`：
- 若**恰好 `pivot_idx == k`**，则结束；
- 反之，**检查 `k` 位于 `pivot_idx` 哪一侧的区间**，进入该区间重复上述过程，**直至某一次分区后 `pivot_idx == k`**。
### 复杂度分析
| | 最好 | 平均 | ==最坏== |
| ----- | ----------- | ----------- | -------- |
| 时间复杂度 | $O(n)$ | $O(n)$ | $O(n^2)$ |
| 空间复杂度 | $O(\log n)$ | $O(\log n)$ | $O(n)$ |
- **理想和平均**情况下：
- **每一次 `Partition` 将剩余区间分成两个大致均等的部分**，此时算法的时间复杂度可由以下递归式表示：$T(n)=T\left(\frac{n}{2}\right)+O(n)$，通过**解递推方程 or 主定理**可得总时间复杂度为 $O(n)$；
- **==最坏情况==** 下：
- `Partition` 将数组分成**极不平衡的两部分**，例如**每次选择的轴值都是剩余区间中的最小或最大元素**，则**递归深度将是 $n$**，递归式变为 $T(n) = T(n-1)+O(n)$，解得**时间复杂度为 $O(n^2)$**
### Quick-Selection 完整实现（基于三路 `Partition`）
```cpp
class QuickSelectMethod {
private:
// 采用三路Partition, 划分成 >pivot, ==pivot, <pivot的三部分.
static std::pair<int,int> Partition(std::vector<int>&arr, int l, int r, int pivot_idx);
static void QuickSelect(std::vector<int>&arr, int l, int r, int k);
public:
// 令指定下标`k`处的元素即为排序后"该位置上所应有的元素", 同时:
// 位置`k`之前的元素都`<=arr[k]`, 位置`k`之后的元素都`>=arr[k]`.
static void QuickSelect(std::vector<int>& arr, int k);
// 获取数组中第k大的元素
static int GetKthElement(std::vector<int>& arr, int k);
// 获取数组中最大的k个元素
static std::vector<int> GetTheLargestKElements(std::vector<int>& arr, int k);
};
/** 快速选择算法
* 作用: 使得指定下标位置`k`处的元素即为排序后"该位置上所应有的元素", 同时:
* - 位置 k 之前的元素都 <= arr[k]
* - 位置 k 之后的元素都 >= arr[k].
*
* 执行完成后, 前k+1项元素[0, k]即为前k+1大的元素.
*/
void QuickSelectMethod::QuickSelect(vector<int> &arr, int l, int r, int k) {
if (l >= r) return;
// 获取一个随机Pivot.
int pivot_idx = l + rand()%(r-l+1);
// 调用三路Partition, 将pivot置于"整个数组完全排序后其应当位于的位置上"
auto [lt, gt] = Partition(arr, l, r, pivot_idx);
if (k >= lt && k <= gt) {
return;
} else if (k < lt) {
QuickSelect(arr, l, lt - 1, k); // 下标k在[l, lt]区间
} else {
QuickSelect(arr, gt + 1, r, k); // 下标k在[gt+1, r]区间
}
}
/** 三路Partition
* 采用三路Partition, 解决存在大量重复值时的效率退化问题
* 将区间[l, r]划分成:
* `> pivot`的[l, lt)
* `==pivot`的[lt,gt]
* `< pivot`的(gt,r]
* 返回 `{lt,gt}`
*/
pair<int,int> QuickSelectMethod::Partition(vector<int>& arr, int l, int r, int pivot_idx) {
int pivot = arr[pivot_idx];
int lt = l;
int gt = r;
int i = l;
while (i <= gt) {
if (arr[i] > pivot) {
swap(arr[i++], arr[lt++]);
} else if (arr[i] < pivot) {
swap(arr[i], arr[gt--]);
} else {
++i;
}
}
return {lt, gt};
};
void QuickSelectMethod::QuickSelect(vector<int>& arr, int k) {
if (k < 0 || k >= arr.size()) return;
// 使得指定下标位置`k`处的元素即为排序后"该位置上所应有的元素".
return QuickSelect(arr, 0, arr.size() - 1, k);
}
// 获取数组中第n大的元素.
int QuickSelectMethod::GetKthElement(vector<int>& arr, int k) {
if (k <= 0 || k > arr.size()) return -1;
// 数组降序排列后, 第k大的元素的下标应为k-1.
// 调用QuickSelect, 令下标k-1位置上的元素即为数组完全排序后改位置上应有的元素.
// 随后, 返回下标k-1位置上的元素即可.
QuickSelect(arr, 0, arr.size() - 1, k - 1);
return arr[k - 1];
}
// 获取数组中前k大的元素
vector<int> QuickSelectMethod::GetTheLargestKElements(vector<int>& arr, int k) {
if (k <= 0 || k > arr.size()) return {};
QuickSelect(arr, 0, arr.size() - 1, k - 1);
return vector<int>(arr.begin(), arr.begin() + k); // 取前k项, 即为前k大的元素.
}
```
<br><br>
# 归并排序
> 参见[^1]
两种写法：
- **自顶向下的递归写法**（直观）；
- **自底向上的迭代写法**
#### 复杂度分析
- 时间复杂度：$O(n\log n)$，最优/平均/最坏均一样。
- 空间复杂度：$O(n)$，**递归栈的空间** + **临时数组的空间**。
### 自顶向下的递归写法
递归：**每次将待排序数组拆分成==两个大小近乎均等的子数组==，分别对两个子数组排序，再 "合并" 两个有序子数组。**
![[_attachment/00-数据结构与算法笔记/基本算法/排序算法.assets/IMG-排序算法-F11B0828553F0E17086D4D48C6049A4C.png|556]]
```cpp
// 归并排序, 递归写法, merge
void MergeSort::Merge(vector<int> &nums, vector<int> &tmp, int l, int mid, int r) {
//将nums中[l, mid]与[mid+1, r]区间的元素按序归并, 放到临时数组temp中, 再将temp中的归并得到的有序排列拷贝回nums中的[l, r]区间
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
for (int p = 0; p < k; p++) {
nums[l + p] = tmp[p];
}
}
// 归并排序, 递归写法, merge sort help
void MergeSort::MergeSortRecursive(vector<int> &nums, vector<int> &tmp, int l, int r) {
if (l >= r) return;
int mid = l + (r-l)/2;
MergeSortRecursive(nums, tmp, l, mid);
MergeSortRecursive(nums, tmp, mid + 1, r);
Merge(nums, tmp, l, mid, r);
}
// 归并排序. 递归写法
void MergeSort::MergeSortRecursive(vector<int> &nums) {
int n = nums.size();
if (n < 2) return;
vector<int> tmp(n, 0);
MergeSortRecursive(nums, tmp, 0, nums.size() - 1);
}
```
### 自底向上的迭代写法
从 `seq=1` 开始，每一轮中，**将数组中==两两相邻==的大小为 `seq` 的子数组作为一组，进行有序合并**。
**每完成一轮，令 `seq*=2`，将其大小翻倍**。 重复该过程，直至 `seq >= n`。
![[_attachment/00-数据结构与算法笔记/基本算法/排序算法.assets/IMG-排序算法-3092D3FC5B14E4B8D84FE97D72D3C461.png|672]]
```cpp
// 归并排序. 迭代写法
void MergeSort::MergeSortReccurent(vector<int> &nums) {
int n = nums.size();
if (n < 2) return;
vector<int> tmp(n, 0);
int seq = 1;
while (seq < n) {
for (int start = 0; start < n; start += 2*seq) {
int mid = min(start + seq, n), end = min(start + 2*seq, n);
int p1 = start, p2 = mid, k = 0; // p1, p2, k三个指针, 分别指向nums中的[l,mid), [mid,r]区间, 以及temp数组.
while (p1 < mid || p2 < end) {
if (p1 < mid && (p2 == end || nums[p1] <= nums[p2])) {
tmp[k++] = nums[p1++];
} else {
tmp[k++] = nums[p2++];
}
}
for (int i = 0; i < k; ++i) { // 归并完成, 将temp中归并得到的有序结果拷贝回nums中[l,r]区间
nums[start + i] = tmp[i];
}
}
seq *= 2;
}
}
```
<br><br>
# 堆排序
![[00-数据结构与算法笔记/数据结构/堆（二叉堆）#堆排序|堆（二叉堆）]]
<br><br>
# 计数排序
**计数排序（CountingSort）** 是非比较型排序，适用于 **元素值范围确定** 且 **范围不大** 的情况[^3]。
思路：
1. 记元素值范围为 `[min_v, max_v]`，开一个 `size = (max_v-min_v+1)` 的 **count 数组**，偏移量 `offset = -min_v`。
2. 令 **count 数组计数各个值出现频次**，值 `v` 对应的 bucket 下标为 `vi = v + offset`。
3. 对 **count 数组求==前缀和==**，得到 **`count[v + offset]` 表示 `≤ v` 的值的数量**。
4. **从后往前遍历==原数组==**，根据 `count[v+offset]` **将原数组元素 `v` 填入到 `output` 数组中**。
5. 令 `output` 数组**覆盖原数组**。
#### 复杂度分析
- 时间复杂度：$O(n+k)$； 最优/平均/最坏均一样。
- $k$ 是**值域范围大小**。
- 排序过中，需遍历原数组、遍历 `count` 数组，后者大小为 $k$
- 空间复杂度：$O(n+k)$；
- count 数组的大小是 $k$，output 数组的大小是 $n$。
- 稳定性：✔️
```cpp
// 计数排序
void countingSort(vector<int>& arr) {
int n = arr.size();
if (n <= 1) return;
int max_v = INT_MIN, min_v = INT_MAX;
for (int x : arr) {
max_v = max(max_v, x);
min_v = min(min_v, x);
}
vector<int> count(max_v - min_v + 1, 0);
vector<int> output(n);
int offset = -min_v;
// 1. 计数各元素值出现次数
for (int x : arr) {
++count[x + offset];
}
// 2. 求前缀和, 得到count[i+offset]表示小于等于i的元素数量
for (int i = 1; i < count.size(); ++i) {
count[i] += count[i-1];
}
// 3. 从后往前遍历原数组, 根据count填入output
for (int i = n - 1; i >= 0; --i) {
int idx = arr[i] + offset;
output[count[idx] - 1] = arr[i];
--count[idx];
}
// 4. 令output覆盖原数组
swap(output, arr);
}
```
<br><br>
# 基数排序
**基数排序（Radix Sort）** 是非比较型排序。适用于**数据能表示成固定位数的格式**（浮点数不适用），**位数不多**的情况（数据范围可以较大，例如 $m=10^8$）。
思路：**逐位排序**：从**最低有效位**开始，依次在 "**==每个数位==**" 上进行一轮 "**==稳定==排序**"（通常搭配 "**计数排序**"）：
1. 根据数组元素的进制数（即每个数字位`Digit`可能的情况 $k$ ）共设置 $k$ 个桶，例如 **10 进制就设置 10 个桶**；
2. 取每个元素**当前数位的值`d`** 计数 `++count[d]`，对`count`求前缀和后再根据其值填入到 `output` 中，再将 `output` 覆盖原数组；
> [!NOTE] 基数排序是从 "**最低有效位**" 开始，依次**在每个数位上**进行一轮排序。
>
> 有些类似于 "**按多关键字排序**" 的思想，即先令**最低有效位有序**，然后应用 "**==稳定==排序算法**"，令**次低位有序**，**==次低位相同==时则仍按==最低位有序==排列**，依此类推。
>
> 以 `[5, 321, 123, 42]` 为例，每一步需应用 "稳定排序"，保留既有相对顺序：
>
> 1. 按**最低位**排序，得到 `[321, 42, 123, 5]`;
> 2. 再按**次低位**排序，得到 `[5, 321, 123, 42]`；
> 3. 再按**右起第三位**排序，得到 `[5, 42, 123, 321]`。
> [!caution] **基数排序不能直接处理 "==负数=="**
>
> 对于负数，有两种处理办法：
>
> - 方式一：**==整体映射==**
> 1. 取 `offset = -min_v`，对所有数组元素进行映射：`x' = x + offset`，即将最小负数映射为 0，使**映射后所有元素非负**，对映射后数组应用基数排序；
> 2. 对排序后的数组元素减去 `offet`，恢复原始值。
> - 方式二：**==对正、负数分组==**，分别排序
> 1. 将**负数放入另一数组**，**按绝对值排序**，再翻转顺序。
> 2. 拼接两个有序数组，令负数数组在前。
>
> 以方式一为例，原数组是：`[-50, -20, 10, 0, -5]`
>
> 1. 最小值是 `-50`，则 `offset = 50` ，对原数组映射得到 → `[0, 30, 60, 50, 45]`
> 2. 排序后变成 → `[0, 30, 45, 50, 60]`
> 3. 再减回去 → `[-50, -20, -5, 0, 10]`
>
#### 复杂度分析
- 时间复杂度：$O((n+r)\cdot K)$；最优/平均/最坏均一样。
- $K$ 是**数值最大位数**，$r$ 是进制数，对十进制即为常量 10。
- 每一轮 **按位排序** 使用计数排序的开销是是 $O(n + r)$，共 $K$ 位。
- 空间复杂度：$O(n+r)$；
- count 数组的大小是 $r$，output 数组的大小是 $n$。
- 稳定性：✔️
```cpp
// 基数排序(可处理负数, 映射法)
void radixSort(vector<int>& arr) {
int n = arr.size();
if (n <= 1) return;
int min_v = INT_MAX, max_v = INT_MIN;
for (int x : arr) {
min_v = min(min_v, x);
max_v = max(max_v, x);
}
// 处理负数: 整体映射为[0, ...)
int offset = -min_v;
if (min_v < 0) {
for (int& x : arr) {
x += offset;
}
max_v += offset;
}
// 计数排序(exp: 当前数位的10的幂)
auto countingSort = [&](int exp) {
vector<int> count(10);
vector<int> output(n);
// 取数位
auto digit = [&exp](int x) { return (x / exp) % 10; };
// 1) 计数
for (int x : arr) {
++count[digit(x)];
}
// 2) 求前缀和
for (int i = 1; i < count.size(); ++i) {
count[i] += count[i-1];
}
// 3) 反向遍历原数组, 填入output, 保持排序稳定性
for (int i = n - 1; i >= 0; --i) {
int d = digit(arr[i]);
output[count[d] - 1] = arr[i];
--count[d];
}
// 4) output覆盖原数组
swap(output, arr);
};
for (long long exp = 1; exp <= max_v; exp *= 10) {
countingSort(exp);
// if (exp > INT_MAX / 10) break;
}
// 处理负数: 还原偏移
if (min_v < 0) {
for (int& x : arr) {
x -= offset;
}
}
}
```
<br><br>
# 桶排序
**桶排序（BucketSort）** 的思路和 "计数排序" 类似，差别在于 **"计数排序" 是每个值一个 bucket**，而桶排序是 "**==按区间划分 bucket==**"，故适用于**数据均匀分布**的情况，例如 **`[0, 1)` 区间浮点数**。
思路：
1. 根据数组中最小值和最大值确定 ==**值域区间**==，将该区间**划分为多段**，每段对应一个桶;
2. 遍历数组，**每个桶存储一个区段内的元素值**，将各元素放入桶中。
3. **独立地对每个桶进行排序**（例如，使用**插入排序** or **快排**等）
4. 依照**桶的顺序**，依次将所有元素合并。
> [!faq] 稳定性：❓取决于**各个桶内排序时，所用排序算法的稳定性**。
#### 复杂度分析
以 "**快排**" 作为桶内排序算法为例，复杂度如下：
| | 平均 | 最好 | ==最坏== |
| ----- | --------------------------------------------- | --------------------------------------------- | ----------------------------------------- |
| 时间复杂度 | $O\left( n+n\log{\large\frac{n}{k}} \right)$ | $O\left( n+n\log{\large\frac{n}{k}} \right)$ | $O(n^2)$ |
| 空间复杂度 | $O \left( n+k+\log\large \frac{n}{k} \right)$ | $O \left( n+k+\log\large \frac{n}{k} \right)$ | $O \left( n+k+\large \frac{n}{k} \right)$ |
| 备注 | 元素均匀分布，各桶内元素数量相近时 | 同← | 所有元素落入同一桶，且快排最坏情况 |
n 个元素划分入 k 个桶，假设每个桶分布均匀，应用 $O(n\log n)$ 排序算法，则时间复杂度为 $O\left( n+k\cdot{\large\frac{n}{k}}\log{\large\frac{n}{k}} \right)$。
```cpp
// 桶排序
void bucketSort(vector<int>& arr, int num_bucket = 10) {
int n = arr.size();
if (n <= 1) return;
// 确定区间
int min_v = INT_MAX, max_v = INT_MIN;
for (int x : arr) {
min_v = min(min_v, x);
max_v = max(max_v, x);
}
// 确定桶范围(上取整, 保证num_bucket个桶覆盖整个值域范围), 创建指定数量的桶
int bucket_range = (0LL + max_v - min_v + 1 + num_bucket - 1) / num_bucket;
vector<vector<int>> buckets(num_bucket);
// 元素分桶
for (int x : arr) {
int idx = (x - min_v) / bucket_range;
buckets[idx].push_back(x);
}
// 对每个桶独立排序
for (auto& bucket : buckets) {
sort(bucket.begin(), bucket.end());
}
// 合并各个桶内数据
int i = 0;
for (auto& bucket: buckets) {
for (int x : bucket) {
arr[i++] = x;
}
}
}
```
<br><br>
# 参考资料
[深入理解快速排序（随机快排、双路快排、三路快排）-CSDN博客](https://blog.csdn.net/u012104219/article/details/80873484)
[图解快速排序及双路三路快速排序](https://segmentfault.com/a/1190000021726667)
[快速排序：解决快排的超时问题](https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/2647778/javapython3cdui-pai-xu-kuai-su-pai-xu-ji-jcb9/)
# Footnotes
[^1]: [图解排序算法(四)之归并排序 - dreamcatcher-cx - 博客园](https://www.cnblogs.com/chengxiao/p/6194356.html)
[^2]: [十大排序算法合集超详细--原理、描述、动画、源码、复杂度、稳定性分析- 掘金](https://juejin.cn/post/6860273835074617358)
[^3]: [漫画：什么是计数排序？-腾讯云开发者社区-腾讯云](https://cloud.tencent.com/developer/article/1684188)