From 14a6e107e5476aa30ce4f493de1321fb55881981 Mon Sep 17 00:00:00 2001
From: partychicken <44670668+partychicken@users.noreply.github.com>
Date: Mon, 1 Apr 2019 14:42:37 +0800
Subject: [PATCH] =?utf8?q?=E6=9B=B4=E6=96=B0=E6=8E=92=E5=BA=8F=E9=83=A8?=
 =?utf8?q?=E5=88=86=E7=9B=AE=E5=BD=95=E7=BB=93=E6=9E=84=20&=20=E6=B7=BB?=
 =?utf8?q?=E5=8A=A0=E6=8E=92=E5=BA=8F=E7=9B=B8=E5=85=B3stl=E5=86=85?=
 =?utf8?q?=E5=AE=B9=20=20(#1131)?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

* Update structure of sort

* move stl-sort out of quick-sort

* Update merge sort

* Update mkdocs.yml

* Update mkdocs.yml

* Update basic.md

* Update merge-sort.md

* Update stl-sort.md

* Update bucket-sort.md

* Update bucket-sort.md

* Update bucket-sort.md

少加了个括号。。。
---
 docs/basic/bubble-sort.md    |  23 +++++
 docs/basic/bucket-sort.md    |  11 ++
 docs/basic/heap-sort.md      |   5 +
 docs/basic/insertion-sort.md |   4 +
 docs/basic/merge-sort.md     |  52 ++++++++++
 docs/basic/quick-sort.md     |  41 ++++++++
 docs/basic/radix-sort.md     |  17 +++
 docs/basic/selection-sort.md |   3 +
 docs/basic/shell-sort.md     |   8 ++
 docs/basic/sort-intro.md     |  23 +++++
 docs/basic/sort.md           | 241 -------------------------------------------
 docs/basic/stl-sort.md       | 112 ++++++++++++++++++++
 docs/basic/use-of-sort.md    |   9 ++
 docs/graph/basic.md          |   2 +-
 mkdocs.yml                   |  14 ++-
 15 files changed, 322 insertions(+), 243 deletions(-)
 create mode 100644 docs/basic/bubble-sort.md
 create mode 100644 docs/basic/bucket-sort.md
 create mode 100644 docs/basic/heap-sort.md
 create mode 100644 docs/basic/insertion-sort.md
 create mode 100644 docs/basic/merge-sort.md
 create mode 100644 docs/basic/quick-sort.md
 create mode 100644 docs/basic/radix-sort.md
 create mode 100644 docs/basic/selection-sort.md
 create mode 100644 docs/basic/shell-sort.md
 create mode 100644 docs/basic/sort-intro.md
 delete mode 100644 docs/basic/sort.md
 create mode 100644 docs/basic/stl-sort.md
 create mode 100644 docs/basic/use-of-sort.md

diff --git a/docs/basic/bubble-sort.md b/docs/basic/bubble-sort.md
new file mode 100644
index 00000000..0db935d1
--- /dev/null
+++ b/docs/basic/bubble-sort.md
@@ -0,0 +1,23 @@
+冒泡排序是一种稳定的排序方法。
+
+以升序为例，冒泡排序每次检查相邻两个元素，如果前面的元素大于后面的元素，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
+
+不难发现，我们最多需要扫描 $n$ 遍数组才能完成排序。
+
+```cpp
+void bubble_sort() {
+  for (int i = 1; i <= n; i++) {
+    bool flag = false;
+    for (int j = 1; j < n; j++)
+      if (a[j] > a[j + 1]) {
+        flag = true;
+        int t = a[j];
+        a[j] = a[j + 1];
+        a[j + 1] = t;
+      }
+    if (!flag) break;  //如果没有执行交换操作，说明数列已经有序
+  }
+}
+```
+
+在序列完全有序时，该算法只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 $O(n)$ 。在最坏情况下，冒泡排序要执行 $\frac{(n-1)n}{2}$ 次交换操作，时间复杂度为 $O(n^2)$ 。在平均情况下，冒泡排序的时间复杂度也是 $O(n^2)$ 。
\ No newline at end of file
diff --git a/docs/basic/bucket-sort.md b/docs/basic/bucket-sort.md
new file mode 100644
index 00000000..4784e112
--- /dev/null
+++ b/docs/basic/bucket-sort.md
@@ -0,0 +1,11 @@
+计数排序也称桶排序，可以在 $O(n)$ 的时间复杂度内对数组进行排序，但是它的空间复杂度与需要排序的数组的值域相关。
+
+但实际操作时，由于时空同阶，时间复杂度应为 $O(\max\left(n,U\right))$，其中 $U$ 代表数组元素的值域大小。
+
+!!! warning "注"
+    注意区分 **基数排序** 与 **桶排序**
+
+算法流程就是记录每一个数出现了多少次，然后从小到大依次输出。
+
+一般考虑的是某一范围内的整数，但是计数排序也可以和[离散化](/misc/discrete)一起使用，来对浮点数、大整数进行排序。
+
diff --git a/docs/basic/heap-sort.md b/docs/basic/heap-sort.md
new file mode 100644
index 00000000..0c3c4230
--- /dev/null
+++ b/docs/basic/heap-sort.md
@@ -0,0 +1,5 @@
+对所有记录建[堆](/ds/heap/)
+
+每次取出堆顶元素，就可以依次得到排好序的序列。
+
+时间复杂度为 $O(n\log n)$ 。
\ No newline at end of file
diff --git a/docs/basic/insertion-sort.md b/docs/basic/insertion-sort.md
new file mode 100644
index 00000000..e5e773de
--- /dev/null
+++ b/docs/basic/insertion-sort.md
@@ -0,0 +1,4 @@
+插入排序依次处理待排序的记录，每个记录和之前处理过的序列中的记录进行比较，然后插入到其中适当的位置。
+
+时间复杂度是 $O(n^2)$ 。
+
diff --git a/docs/basic/merge-sort.md b/docs/basic/merge-sort.md
new file mode 100644
index 00000000..f4c4ec18
--- /dev/null
+++ b/docs/basic/merge-sort.md
@@ -0,0 +1,52 @@
+## 算法
+
+归并排序是一种采用了[分治](/basic/divide-and-conquer)思想的排序算法，其本质是一种 [CDQ 分治](/misc/cdq-divide)。
+
+归并排序分为三个过程：
+
+1. 将数列随意划分为两部分（在均匀划分时时间复杂度为 $O\left(n\log{n}\right)$ ）
+2. 递归地分别对两个子序列进行归并排序
+3. 合并两个子序列
+
+不难发现，归并排序的核心是如何合并两个子序列，前两步都很好实现。
+
+其实合并的时候也不难操作。注意到两个子序列在第二步中已经保证了都是有序的了，第三步中实际上是想要把两个 **有序** 的序列合并起来。
+
+```cpp
+void merge(int ll, int rr) {
+  // 用来把 a[ll.. rr - 1] 这一区间的数排序。 t 数组是临时存放有序的版本用的。
+  if (rr - ll <= 1) return;
+  int mid = ll + (rr - ll >> 1);
+  merge(ll, mid);
+  merge(mid, rr);
+  int p = ll, q = mid, s = ll;
+  while (s < rr) {
+    if (p >= mid || (q < rr && a[p] > a[q])) {
+      t[s++] = a[q++];
+      // ans += mid - p;
+    } else
+      t[s++] = a[p++];
+  }
+  for (int i = ll; i < rr; ++i) a[i] = t[i];
+}
+```
+
+由于 `||` 是短路运算符，这里面 if 判断的情况是“第一部分已经完全合并完了”或者“两个都没有合并完，且前一个的队首要大于后一个”，这两种情况都是要把后一个子序列的队首放到新序列的当前位置中。
+
+## 逆序对
+
+归并排序还可以用来求逆序对的个数。
+
+所谓逆序对，就是满足 $a_{i} > a_{j}$ 且 $i < j$ 的数对 $(i, j)$ 。
+
+可以用[树状数组](/ds/bit)、[线段树](/ds/segment/)等数据结构来求，也可以用归并排序来求。
+
+具体来说，上面归并排序中间注释掉的 `ans += mid - p` 就是在统计逆序对个数。
+
+是因为，那里把靠后的数放到前面了（较小的数放在前面），所以在这个数的原来位置之前的、比它大的数都会和它形成逆序对，而这个个数就是还没有合并进去的数的个数，即为 `mid - p` 。
+
+使用归并排序求逆序对的时间复杂度也是 $O(n \log n)​$ 。
+
+## 参考
+
+<https://www.geeksforgeeks.org/merge-sort/>
diff --git a/docs/basic/quick-sort.md b/docs/basic/quick-sort.md
new file mode 100644
index 00000000..5f849125
--- /dev/null
+++ b/docs/basic/quick-sort.md
@@ -0,0 +1,41 @@
+##  算法
+
+快速排序是[分治](/basic/divide-and-conquer)地来将一个数组排序。
+
+快速排序分为三个过程：
+
+1. 将数列划分为两部分（不是直接分，要求保证相对大小关系）
+2. 递归到两个子序列中分别进行快速排序
+3. 不用合并，因为此时数列已经完全有序
+
+和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。
+
+第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。
+
+具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。
+
+怎么操作呢？为了保证平均时间复杂度，一般是随机选择一个数 m 来当做两个子数列的分界。
+
+之后，维护一前一后两个指针 p 和 q，依次考虑当前的数是否放在了应该放的位置（前还是后），当前位置放对了之后，再移动指针继续处理，直到两个指针相遇。
+
+如果当前的数没放对呢？比如说如果后面的指针 q 遇到了一个比 m 小的数，那么可以交换 p 和 q 位置上的数，再把 p 向后移一位。
+
+其实，快速排序没有指定应如何具体实现第一步，不论是选择 m 的过程还是划分的过程，都不是只有一种实现方法。
+
+注意，一般我们说的快速排序的时间复杂度是平均为 $O(n\log n)$ ，最坏是 $O(n^2)$ ，只不过实践中几乎不可能达到最坏情况。
+
+其实，在选择 m 的过程中使用 [Median of Medians](https://en.wikipedia.org/wiki/Median_of_medians) 算法，就可以保证最坏时间复杂度为 $O(n\log n)$ ，但是由于其过于复杂，实践中一般不使用。
+
+## 线性找第 k 大的数
+
+找第 k 大的数（K-th order statistic），最简单的方法是先排序，然后直接找到第 k 大的位置的元素。这样做的时间复杂度是 $O(n\log n)​$ ，对于这个问题来说很不划算。事实上，我们有时间复杂度 $O(n)​$ 的解法。
+
+考虑快速排序的划分过程，在快速排序的“划分”结束后，数列 $A_{p} \cdots A_{r}​$ 被分成了 $A_{p} \cdots A_{q}​$ 和 $A_{q+1} \cdots A_{r}​$ ，此时可以按照左边元素的个数（ $q - p + 1​$ ）和 k 的大小关系来判断是只在左边还是只在右边递归地求解。
+
+可以证明，在期望意义下，程序的时间复杂度为 $O(n)$ 。
+
+### 参考
+
+<https://stackoverflow.com/questions/22339240/what-algorithms-are-used-in-c11-stdsort-in-different-stl-implementations>
+
+<https://en.cppreference.com/w/cpp/algorithm/sort>
\ No newline at end of file
diff --git a/docs/basic/radix-sort.md b/docs/basic/radix-sort.md
new file mode 100644
index 00000000..ff84c672
--- /dev/null
+++ b/docs/basic/radix-sort.md
@@ -0,0 +1,17 @@
+基数排序是将待排序码拆分成多个部分分别来比较。
+
+按照排序码的先后顺序，分为两种：
+
+1. 高位优先（MSD）
+   先对高位排序，分成若干子序列，对每个子序列根据较低位排序，是一个分、分、……、分、收的过程。
+2. 低位优先（LSD）
+   从低位开始，对于排好的序列用次低位排序，（每次排序的都是全体元素）是一个分、收、分、收、……、分、收的过程。
+
+低位优先速度较快，便于处理，更常用。
+
+基数排序对关键码值进行 $O(\log_r n)$ 次运算，因此处理 n 个不同的关键码时，基数排序的时间代价为 $O(n \log n)$ 。
+
+### 参考
+
+<http://atool.org/sort.php>ATool 的排序演示动画  
+<https://www.geeksforgeeks.org/counting-sort/>
\ No newline at end of file
diff --git a/docs/basic/selection-sort.md b/docs/basic/selection-sort.md
new file mode 100644
index 00000000..067671bf
--- /dev/null
+++ b/docs/basic/selection-sort.md
@@ -0,0 +1,3 @@
+每次找出第 i 小的元素，将这个元素与数组第 i 个位置上的元素交换。
+
+时间复杂度为 $O(n^2)$ 。
\ No newline at end of file
diff --git a/docs/basic/shell-sort.md b/docs/basic/shell-sort.md
new file mode 100644
index 00000000..477eb5bc
--- /dev/null
+++ b/docs/basic/shell-sort.md
@@ -0,0 +1,8 @@
+Shell 排序是以它的发明者命名的，也称为缩小增量排序法。Shell 排序对不相邻的记录进行比较和移动：
+
+1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）
+2. 对这些子序列进行插入排序
+3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1
+
+Shell 排序的复杂度和间距序列的选取（就是间距如何减小到 1）有关，比如“间距每次除以 3”的 Shell 排序的复杂度是 $O(n^{3/2})$ 。
+
diff --git a/docs/basic/sort-intro.md b/docs/basic/sort-intro.md
new file mode 100644
index 00000000..134cdc48
--- /dev/null
+++ b/docs/basic/sort-intro.md
@@ -0,0 +1,23 @@
+**排序算法多种多样**，性质也大多不同。
+
+## 稳定性
+
+稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
+
+基数排序、计数排序（桶排序）、插入排序、冒泡排序、归并排序是稳定排序。
+
+选择排序、堆排序、快速排序不是稳定排序。
+
+## 时间复杂度
+
+时间复杂度用来衡量一个算法的运行时间和输入规模的关系，类似的有空间复杂度，用来描述算法的空间消耗的规模。
+
+简单计算复杂度的方法一般是统计“简单操作”的执行次数，有时候也可以直接数循环的层数来近似估计。
+
+时间复杂度分为最坏时间复杂度、平均时间复杂度、最好时间复杂度等等。OI 竞赛中要考虑的一般是最坏时间复杂度，因为它代表的是算法运行水平的下界，在评测中不会出现更差的结果了。
+
+基于比较的排序算法的时间复杂度下限是 $O(n\log n)$ 的。
+
+当然也有不是 $O(n\log n)$ 的，桶排序的时间复杂度是 $O(n)$ ，但是它是在「用空间换时间」，它的空间复杂度是 $O($ 所排序的最大数 $)$ 
+
+当待排序的关键码序列基本有序时，插入排序最快。
\ No newline at end of file
diff --git a/docs/basic/sort.md b/docs/basic/sort.md
deleted file mode 100644
index d5891d61..00000000
--- a/docs/basic/sort.md
+++ /dev/null
@@ -1,241 +0,0 @@
-排序算法多种多样，性质也大多不同。
-
-## 稳定性
-
-稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
-
-基数排序、计数排序（桶排序）、插入排序、冒泡排序、归并排序是稳定排序。
-
-选择排序、堆排序、快速排序不是稳定排序。
-
-## 时间复杂度
-
-时间复杂度用来衡量一个算法的运行时间和输入规模的关系，类似的有空间复杂度，用来描述算法的空间消耗的规模。
-
-简单计算复杂度的方法一般是统计“简单操作”的执行次数，有时候也可以直接数循环的层数来近似估计。
-
-时间复杂度分为最坏时间复杂度、平均时间复杂度、最好时间复杂度等等。OI 竞赛中要考虑的一般是最坏时间复杂度，因为它代表的是算法运行水平的下界，在评测中不会出现更差的结果了。
-
-基于比较的排序算法的时间复杂度下限是 $O(n\log n)$ 的。
-
-当然也有不是 $O(n\log n)$ 的，桶排序的时间复杂度是 $O(n)$ ，但是它是在「用空间换时间」，它的空间复杂度是 $O($ 所排序的最大数 $)$ 
-
-当待排序的关键码序列基本有序时，插入排序最快。
-
-## 冒泡排序
-
-冒泡排序是一种稳定的排序方法。
-
-以升序为例，冒泡排序每次检查相邻两个元素，如果前面的元素大于后面的元素，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
-
-不难发现，我们最多需要扫描 $n$ 遍数组才能完成排序。
-
-```cpp
-void bubble_sort() {
-  for (int i = 1; i <= n; i++) {
-    bool flag = false;
-    for (int j = 1; j < n; j++)
-      if (a[j] > a[j + 1]) {
-        flag = true;
-        int t = a[j];
-        a[j] = a[j + 1];
-        a[j + 1] = t;
-      }
-    if (!flag) break;  //如果没有执行交换操作，说明数列已经有序
-  }
-}
-```
-
-在序列完全有序时，该算法只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 $O(n)$ 。在最坏情况下，冒泡排序要执行 $\frac{(n-1)n}{2}$ 次交换操作，时间复杂度为 $O(n^2)$ 。在平均情况下，冒泡排序的时间复杂度也是 $O(n^2)$ 。
-
-## 插入排序
-
-插入排序依次处理待排序的记录，每个记录和之前处理过的序列中的记录进行比较，然后插入到其中适当的位置。
-
-时间复杂度是 $O(n^2)$ 。
-
-## Shell 排序
-
-Shell 排序是以它的发明者命名的，也称为缩小增量排序法。Shell 排序对不相邻的记录进行比较和移动：
-
-1.  将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）
-2.  对这些子序列进行插入排序
-3.  减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1
-
-Shell 排序的复杂度和间距序列的选取（就是间距如何减小到 1）有关，比如“间距每次除以 3”的 Shell 排序的复杂度是 $O(n^{3/2})$ 。
-
-## 选择排序
-
-每次找出第 i 小的元素，将这个元素与数组第 i 个位置上的元素交换。
-
-时间复杂度为 $O(n^2)$ 。
-
-## 堆排序
-
-对所有记录建[堆](/ds/heap/)
-
-每次取出堆顶元素，就可以依次得到排好序的序列。
-
-时间复杂度为 $O(n\log n)$ 。
-
-## 归并排序
-
-归并排序是一种采用了[分治](/basic/divide-and-conquer)思想的排序算法。
-
-归并排序分为三个过程：
-
-1.  将数列随意划分为两部分（在均匀划分时时间复杂度为 $O\left(n\log{n}\right)$ ）
-2.  递归地分别对两个子序列进行归并排序
-3.  合并两个子序列
-
-不难发现，归并排序的核心是如何合并两个子序列，前两步都很好实现。
-
-其实合并的时候也不难操作。注意到两个子序列在第二步中已经保证了都是有序的了，第三步中实际上是想要把两个 **有序** 的序列合并起来。
-
-```cpp
-void merge(int ll, int rr) {
-  // 用来把 a[ll.. rr - 1] 这一区间的数排序。 t 数组是临时存放有序的版本用的。
-  if (rr - ll <= 1) return;
-  int mid = ll + (rr - ll >> 1);
-  merge(ll, mid);
-  merge(mid, rr);
-  int p = ll, q = mid, s = ll;
-  while (s < rr) {
-    if (p >= mid || (q < rr && a[p] > a[q])) {
-      t[s++] = a[q++];
-      // ans += mid - p;
-    } else
-      t[s++] = a[p++];
-  }
-  for (int i = ll; i < rr; ++i) a[i] = t[i];
-}
-```
-
-由于 `||` 是短路运算符，这里面 if 判断的情况是“第一部分已经完全合并完了”或者“两个都没有合并完，且前一个的队首要大于后一个”，这两种情况都是要把后一个子序列的队首放到新序列的当前位置中。
-
-### 逆序对
-
-归并排序还可以用来求逆序对的个数。
-
-所谓逆序对，就是满足 $a_{i} > a_{j}$ 且 $i < j$ 的数对 $(i, j)$ 。
-
-可以用[树状数组](/ds/bit)、[线段树](/ds/segment/)等数据结构来求，也可以用归并排序来求。
-
-具体来说，上面归并排序中间注释掉的 `ans += mid - p` 就是在统计逆序对个数。
-
-是因为，那里把靠后的数放到前面了（较小的数放在前面），所以在这个数的原来位置之前的、比它大的数都会和它形成逆序对，而这个个数就是还没有合并进去的数的个数，即为 `mid - p` 。
-
-使用归并排序求逆序对的时间复杂度也是 $O(n \log n)$ 。
-
-### 参考
-
-<https://www.geeksforgeeks.org/merge-sort/>
-
-## 快速排序
-
-快速排序是[分治](/basic/divide-and-conquer)地来将一个数组排序。
-
-快速排序分为三个过程：
-
-1.  将数列划分为两部分（不是直接分，要求保证相对大小关系）
-2.  递归到两个子序列中分别进行快速排序
-3.  不用合并，因为此时数列已经完全有序
-
-和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。
-
-第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。
-
-具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。
-
-怎么操作呢？为了保证平均时间复杂度，一般是随机选择一个数 m 来当做两个子数列的分界。
-
-之后，维护一前一后两个指针 p 和 q，依次考虑当前的数是否放在了应该放的位置（前还是后），当前位置放对了之后，再移动指针继续处理，直到两个指针相遇。
-
-如果当前的数没放对呢？比如说如果后面的指针 q 遇到了一个比 m 小的数，那么可以交换 p 和 q 位置上的数，再把 p 向后移一位。
-
-其实，快速排序没有指定应如何具体实现第一步，不论是选择 m 的过程还是划分的过程，都不是只有一种实现方法。
-
-注意，一般我们说的快速排序的时间复杂度是平均为 $O(n\log n)$ ，最坏是 $O(n^2)$ ，只不过实践中几乎不可能达到最坏情况。
-
-其实，在选择 m 的过程中使用 [Median of Medians](https://en.wikipedia.org/wiki/Median_of_medians) 算法，就可以保证最坏时间复杂度为 $O(n\log n)$ ，但是由于其过于复杂，实践中一般不使用。
-
-### STL
-
-C 函数模板库实现了快速排序，即 `stdlib.h` 当中的 `qsort` 。
-
-但在 OI 相关比赛当中，更为常见的库排序函数是 C++ `algorithm` 库中的 `std::sort` 函数。
-
-C++ 标准并未严格要求此函数的实现算法，具体实现取决于编译器。
-
-旧版 C++ 标准中仅要求它的 **平均** 时间复杂度达到 $O(n\log n)$，但 C++11 标准要求它的 **最坏** 时间复杂度是达到 $O(n\log n)$ 。可以查阅 [std::sort()](https://en.cppreference.com/w/cpp/algorithm/sort)
-
-在 [libstdc++](https://github.com/mirrors/gcc/blob/master/libstdc++-v3/include/bits/stl_algo.h) 和 [libc++](http://llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm) 中使用的都是 [Introsort](https://en.wikipedia.org/wiki/Introsort)。
-
-Introsort 限制了快速排序的分治深度，当分治达到一定深度之后，改用最坏时间复杂度为 $O(n\log n)$ 的排序算法（比如堆排序）来给子数组排序。
-
-Introsort 的这个限制使得它的最坏时间复杂度是 $O(n\log n)$ 的。
-
-快速用法：
-
-```cpp
-// a[0] .. a[n - 1] 为需要排序的数列
-std::sort(a, a + n);
-// 这句代码直接修改 a 数组里的元素顺序，使得现在它是从小到大排列的
-```
-
-### 线性找第 k 大的数
-
-找第 k 大的数（K-th order statistic），最简单的方法是先排序，然后直接找到第 k 大的位置的元素。这样做的时间复杂度是 $O(n\log n)$ ，对于这个问题来说很不划算。事实上，我们有时间复杂度 $O(n)$ 的解法。
-
-考虑快速排序的划分过程，在快速排序的“划分”结束后，数列 $A_{p} \cdots A_{r}$ 被分成了 $A_{p} \cdots A_{q}$ 和 $A_{q+1} \cdots A_{r}$ ，此时可以按照左边元素的个数（ $q - p + 1$ ）和 k 的大小关系来判断是只在左边还是只在右边递归地求解。
-
-可以证明，在期望意义下，程序的时间复杂度为 $O(n)$ 。
-
-### 参考
-
-<https://stackoverflow.com/questions/22339240/what-algorithms-are-used-in-c11-stdsort-in-different-stl-implementations>
-
-<https://en.cppreference.com/w/cpp/algorithm/sort>
-
-## 计数排序
-
-计数排序也称桶排序，可以在 $O(n)$ 的时间复杂度内对数组进行排序，但是它的空间复杂度与需要排序的数组的值域相关。
-
-!!! warning "注"
-    注意区分 **基数排序** 与 **桶排序**
-
-算法流程就是记录每一个数出现了多少次，然后从小到大依次输出。
-
-一般考虑的是某一范围内的整数，但是计数排序也可以和[离散化](/misc/discrete)一起使用，来对浮点数、大整数进行排序。
-
-## 基数排序
-
-基數排序是将待排序码拆分成多个部分分别来比较。
-
-按照排序码的先后顺序，分为两种：
-
-1.  高位优先（MSD）
-    先对高位排序，分成若干子序列，对每个子序列根据较低位排序，是一个分、分、……、分、收的过程。
-2.  低位优先（LSD）
-    从低位开始，对于排好的序列用次低位排序，（每次排序的都是全体元素）是一个分、收、分、收、……、分、收的过程。
-
-低位优先速度较快，便于处理，更常用。
-
-基数排序对关键码值进行 $O(\log_r n)$ 次运算，因此处理 n 个不同的关键码时，基数排序的时间代价为 $O(n \log n)$ 。
-
-### 参考
-
-<http://atool.org/sort.php>ATool 的排序演示动画  
-<https://www.geeksforgeeks.org/counting-sort/>
-
-## 排序的应用
-
-借助排序，我们可以降低求解问题所需要的时间复杂度。
-
-考虑一个数列，你需要检查其中是否有元素相等。
-
-一个朴素的做法是检查每一个数对，并判断这一对数是否相等。时间复杂度是 $O(n^2)$ 。
-
-我们不妨先对这一列数排序，之后不难发现：如果有相等的两个数，它们一定在新数列中处于相邻的位置上。这时，只需要 $O(n)$ 地扫一遍新数列了。总的时间复杂度是排序的复杂度（ $O(n\log n)$ ）。
-
-排序也是[二分查找](/basic/binary/)所要做的预处理工作。在排序后使用[二分查找](/basic/binary/)，我们可以在 $O(\log n)$ 的时间内在序列中查找指定的元素。
diff --git a/docs/basic/stl-sort.md b/docs/basic/stl-sort.md
new file mode 100644
index 00000000..c18517ec
--- /dev/null
+++ b/docs/basic/stl-sort.md
@@ -0,0 +1,112 @@
+## sort
+
+C 函数模板库实现了快速排序，即 `stdlib.h` 当中的 `qsort` 。
+
+但在 OI 相关比赛当中，更为常见的库排序函数是 C++ `algorithm` 库中的 `std::sort` 函数。
+
+C++ 标准并未严格要求此函数的实现算法，具体实现取决于编译器。
+
+旧版 C++ 标准中仅要求它的 **平均** 时间复杂度达到 $O(n\log n)$，但 C++11 标准要求它的 **最坏** 时间复杂度是达到 $O(n\log n)$ 。可以查阅 [std::sort()](https://en.cppreference.com/w/cpp/algorithm/sort)
+
+在 [libstdc++](https://github.com/mirrors/gcc/blob/master/libstdc++-v3/include/bits/stl_algo.h) 和 [libc++](http://llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm) 中使用的都是 [Introsort](https://en.wikipedia.org/wiki/Introsort)。
+
+Introsort 限制了快速排序的分治深度，当分治达到一定深度之后，改用最坏时间复杂度为 $O(n\log n)$ 的排序算法（比如堆排序）来给子数组排序。
+
+Introsort 的这个限制使得它的最坏时间复杂度是 $O(n\log n)$ 的。
+
+快速用法：
+
+```cpp
+// a[0] .. a[n - 1] 为需要排序的数列
+std::sort(a, a + n);
+// 这句代码直接修改 a 数组里的元素顺序，使得现在它是从小到大排列的
+```
+
+## nth_element
+
+作用是找到选定区间内第 $k​$ 大的数，并将所有比它小的数与比它大的数分别置于两侧，返回它的地址。
+
+原理是未完成的快速排序
+
+用法
+
+```cpp
+std::nth_element(begin,mid,end);
+```
+
+时间复杂度：期望 $O(n)$
+
+常用于构建 K-DTree
+
+## stable_sort
+
+稳定的 $O(nlogn)$ 排序，即保证相等元素排序后的相对位置与原序列相同。
+
+用法
+
+```cpp
+std::stable_sort(begin,end,cmp);
+```
+
+## partial_sort
+
+将序列中前 $k$ 小元素按顺序置于前 $k$ 个位置，后面的元素不保证顺序。
+
+复杂度：$O(nlogk)$
+
+用法：
+
+```cpp
+std::partial_sort(begin,begin+k,end);
+```
+
+原理：
+
+实现 partial_sort 的思想是：对原始容器内区间为 $[first, middle)$ 的元素执行make_heap() 操作构造一个大根堆，然后拿 $[middle, last)$ 中的每个元素和 $first$ 进行比较，$first$ 内的元素为堆内的最大值。如果小于该最大值，则互换元素位置，并对 $[first, middle)$ 内的元素进行调整，使其保持最大堆序。比较完之后在对 $[first, middle)$ 内的元素做一次对排序 sort_heap() 操作，使其按增序排列。注意，堆序和增序是不同的。
+
+## 定义运算符
+
+对于内置类型（如 `int` ）和用户定义的结构体，你都可以定义调用 STL 排序函数时使用的**小于运算符**。你可以在调用函数时同时传入一个比较运算符的函数（一般是最后一项），也可以直接重载该类型的默认运算符。参见 [cppreference](https://zh.cppreference.com/w/cpp/language/operators) 。
+下面是几个例子：
+
+```cpp
+int a[1009], n = 10;
+// ......
+std::sort(a + 1, a + 1 + n); // 不重载，从小到大排序。
+std::sort(a + 1, a + 1 + n, greater<int>()); // 重载小于运算符为大于，从大到小排序。
+```
+
+```cpp
+struct data {
+    int a, b;
+    bool operator < (const data rhs) const {
+        return (a == rhs.a) ? (b < rhs.b) : (a < rhs.a);
+    }
+} da[1009];
+bool cmp (const data u1, const data u2) {
+    return (u1.a == u2.a) ? (u1.b > u2.b) : (u1.a > u2.a);
+}
+// ......
+std::sort(da + 1, da + 1 + 10, cmp); // 不重载，从小到大排序。
+std::sort(da + 1, da + 1 + 10, cmp); // 重载小于运算符为大于，从大到小排序。
+```
+
+### 严格弱序
+
+进行排序的运算符必须满足严格弱序（ [Strict weak orderings](https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings) ），否则会出现不可预料的情况（如运行时错误）。
+严格弱序的要求：
+
+1. $x \not< x$ （非自反性）
+2. 若 $x < y$ ，则 $y \not< x$ （非对称性）
+3. 若 $x < y, y < z$ ，则 $x < z$ （传递性）
+4. 若 $x \not< y, y \not< x, y \not< z, z \not< y$，则 $x \not< z, z \not< x$ （不可比性的传递性）
+
+常见的错误做法：
+
+* 使用 `<=` 来定义排序中的小于运算符。
+* 在调用排序运算符时，读取外部数值可能会改变的数组。（常见于最短路算法）
+* 将多个数的最大最小值进行比较的结果作为排序运算符。
+
+### Reference
+
+* [浅谈邻项交换排序的应用以及需要注意的问题](https://ouuan.github.io/浅谈邻项交换排序的应用以及需要注意的问题/)
diff --git a/docs/basic/use-of-sort.md b/docs/basic/use-of-sort.md
new file mode 100644
index 00000000..1f121f59
--- /dev/null
+++ b/docs/basic/use-of-sort.md
@@ -0,0 +1,9 @@
+借助排序，我们可以降低求解问题所需要的时间复杂度。
+
+考虑一个数列，你需要检查其中是否有元素相等。
+
+一个朴素的做法是检查每一个数对，并判断这一对数是否相等。时间复杂度是 $O(n^2)$ 。
+
+我们不妨先对这一列数排序，之后不难发现：如果有相等的两个数，它们一定在新数列中处于相邻的位置上。这时，只需要 $O(n)$ 地扫一遍新数列了。总的时间复杂度是排序的复杂度（ $O(n\log n)$ ）。
+
+排序也是[二分查找](/basic/binary/)所要做的预处理工作。在排序后使用[二分查找](/basic/binary/)，我们可以在 $O(\log n)$ 的时间内在序列中查找指定的元素。
\ No newline at end of file
diff --git a/docs/graph/basic.md b/docs/graph/basic.md
index 022dc292..6122f1c9 100644
--- a/docs/graph/basic.md
+++ b/docs/graph/basic.md
@@ -36,7 +36,7 @@
 
 其中 `head[i]` 用来存以 $i$ 为起点的边， `edge` 数组是边表。
 
-那么什么是前向星呢？事先把 `edge` 数组排个序即可。这里可以使用[基数排序](/basic/sort)做到 $O(m)$ 。
+那么什么是前向星呢？事先把 `edge` 数组排个序即可。这里可以使用[基数排序](/basic/radix-sort)做到 $O(m)$ 。
 
 ## 图的基本概念
 
diff --git a/mkdocs.yml b/mkdocs.yml
index 2cf1ab2d..3132b853 100644
--- a/mkdocs.yml
+++ b/mkdocs.yml
@@ -43,7 +43,19 @@ nav:
     - 模拟: basic/simulate.md
     - 递归 & 分治: basic/divide-and-conquer.md
     - 贪心: basic/greedy.md
-    - 排序: basic/sort.md
+    - 排序: 
+      - 排序简介: basic/sort-intro.md
+      - 选择排序: basic/selection-sort.md
+      - 冒泡排序: basic/bubble-sort.md
+      - 插入排序: basic/insertion-sort.md
+      - 计数排序: basic/bucket-sort.md
+      - 快速排序: basic/quick-sort.md
+      - 归并排序: basic/merge-sort.md
+      - 堆排序: basic/heap-sort.md
+      - 基数排序: basic/radix-sort.md
+      - 希尔排序: basic/shell-sort.md
+      - 排序相关 STL: basic/stl-sort.md
+      - 排序应用: basic/use-of-sort.md
     - 表达式求值: basic/expression.md
     - 二分: basic/binary.md
     - 构造: basic/construction.md
-- 
2.11.0