排序算法（分治）
快速排序：
题面：
给定你一个长度为 \(n\) 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 \(n\)。
第二行包含 \(n\) 个整数（所有整数均在 \(1 \sim 10^9\) 范围内），表示整个数列。
输出格式
输出共一行，包含 \(n\) 个整数，表示排好序的数列。
数据范围
\(1 \le n \le 100000\)
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
思路：
快速排序是以一种分治思想而实现的。
首先对于一个左端点为 \(l\) 右端点为 \(r\) 的一个数组 \(q\)，我们进行一下 3 中操作：
- 选定一个分界点：\(q_l,q_r,q_{\frac{l+r}{2}}\)，我们先将分界点记作 \(x\)。
- 将小于 \(x\) 的数放在 \(q\) 数组的左边，大于 \(x\) 的数放在 \(q\) 数组的右边，等于 \(x\) 的数就不用管，放在那一边都可以。
- 递归处理小于 \(x\) 左边数组和大于 \(x\) 右边数组即可。
1 和 3 操作都很轻松，问题就是在 2 步，如何优美地处理后面大小分明的数组。
显然我们可以使用双指针，\(i\) 从前往后找到第一个大于等于 \(x\) 的数，\(j\) 从后往前找到第一个小于等于 \(x\) 的数，如果 \(i<j\) 就将这两个数调换即可。
递归边界？显然就是 \(l=r\) 的时候停止。
AC code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+100;
int n,q[N];
void quick_sort(int q[],int l,int r){
if(l>=r) return ;
int x=q[l+r>>1],i=l-1,j=r+1;
while(i<j){
while(q[++i]<x);
while(q[--j]>x);
//每次先+1和-1可以确保不会死循环
if(i<j) swap(q[i],q[j]);
}
quick_sort(q,l,j),quick_sort(q,j+1,r);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++) cin>>q[i];
quick_sort(q,1,n);
for(int i=1;i<=n;i++) cout<<q[i]<<' ';cout<<'\n';
return 0;
}