文章目录
前言
一、快速排序
二、例题，代码
AcWing 785. 快速排序
本题解析
AC代码
AcWing 786. 第k个数
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解数学知识：快速排序，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、快速排序
提供快排模板：
void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); }
本模板来自：AcWing算法基础课
二、例题，代码
AcWing 785. 快速排序
本题链接：AcWing 785. 快速排序
本博客提供本题截图：
本题解析
板子题，直接套模板
AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int q[N]; void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); quick_sort(q, 0, n - 1); for (int i = 0; i < n; i ++ ) printf("%d ", q[i]); return 0; }
AcWing 786. 第k个数
本题链接：AcWing 786. 第k个数
本博客提供本题截图：
本题解析
同样是直接套板子的题目
AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int q[N]; void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); } int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); quick_sort(q, 0, n - 1); printf("%d", q[k - 1]); return 0; }
三、时间复杂度
关于快速排序的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
