AcWing785. 快速排序
一、题目描述
给定你一个长度为 n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
二、算法原理
- 每次排序时选取一个基准，将小于基准的数全部放到基准点的左边，将大于或等于基准的数全部放到基准的右边。
- 完成后，得到了两个 整体 上有序的子数组，再递归继续，直至所有元素完成排序。
算法模拟
假设对6,1,2,7,9,3,4,5,10,86,1,2,7,9,3,4,5,10,8这1010个数进行排序：
本次模拟的基准是以数组的第一个元素为基准的。
从后向前扫描,i去向右找第一个大于 基准66 (这个66是选择的第一元素，代码中我们将选择中间位置的元素，道理都是一样的) 的数字,j向左查找第一个小于基准66数字：
交换之后：3,1,2,5,4,6,9,7,10,83,1,2,5,4,6,9,7,10,8, 一趟排序结束。
以基准值66划分的两堆数据,左手边都比66小，右手边都比66大，66在中间，然后再用同样的办法递归处理左右两边即可，此时，66就不参与了。
三、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N];
int n;
/**
* 功能：利用快速排序对数组进行排序
* @param q 要排序的数组
* @param l 左端下标位置
* @param r 右端下标位置
*/
void quick_sort(int q[], int l, int r) {
if (l >= r) return;
int i = l - 1, j = r + 1; // 从界外开始
int x = q[(l + r) >> 1]; // 基准值为中间位置的数值
while (i < j) { // 没有碰面就一直按这个逻辑跑一跑
do i++;
while (q[i] < x); // i哨兵向右走，找到第一个大于基准值的数，这个数的位置需要调整
do j--;
while (q[j] > x); // j哨兵向左走，找到第一个小于基准值的数，这个数的位置需要调整
if (i < j) swap(q[i], q[j]); // 如果还没有碰面，就对调一下
}
// 当退出上面的循环，就是两个人碰面的时候，此时左右两半都已经是有序的了，再递归处理
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> q[i];
quick_sort(q, 1, n);
for (int i = 1; i <= n; i++) printf("%d ", q[i]);
return 0;
}