From 3bdfa720031ca9b7965bfe3e82dfca5c5892a7d6 Mon Sep 17 00:00:00 2001 From: Xeonacid Date: Mon, 19 Oct 2020 17:11:09 +0800 Subject: [PATCH] fix(quick-sort): remove duplicate, small refactor --- docs/basic/quick-sort.md | 32 +++++++++++++------------------- 1 file changed, 13 insertions(+), 19 deletions(-) diff --git a/docs/basic/quick-sort.md b/docs/basic/quick-sort.md index 46cadadb..ca9af2da 100644 --- a/docs/basic/quick-sort.md +++ b/docs/basic/quick-sort.md @@ -24,24 +24,6 @@ 第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。 -### 线性找第 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)$ 。 - -## 性质 - -### 稳定性 - -快速排序是一种不稳定的排序算法。 - -### 时间复杂度 - -快速排序的最优时间复杂度和平均时间复杂度为 $O(n\log n)$ ，最坏时间复杂度为 $O(n^2)$ 。 - ### 实现（C++）[^ref2] ```cpp @@ -76,6 +58,16 @@ void quick_sort(T arr[], const int len) { } ``` +## 性质 + +### 稳定性 + +快速排序是一种不稳定的排序算法。 + +### 时间复杂度 + +快速排序的最优时间复杂度和平均时间复杂度为 $O(n\log n)$ ，最坏时间复杂度为 $O(n^2)$ 。 + ## 优化 ### 朴素优化思想 @@ -136,7 +128,9 @@ void quick_sort(T arr[], const int len) { 从 2000 年 6 月起，SGI C++ STL 的 `stl_algo.h` 中 `sort()` 函数的实现采用了内省排序算法。 -## 线性找第 k 大的数 +## 应用 + +### 线性找第 k 大的数 找第 $k$ 大的数（K-th order statistic），最简单的方法是先排序，然后直接找到第 $k$ 大的位置的元素。这样做的时间复杂度是 $O(n\log n)$ ，对于这个问题来说很不划算。 -- 2.11.0