题面：
给定你一个长度为 \(n\) 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
原题链接：785. 快速排序 - AcWing
需要注意的几个点：
- 左右哨兵的发动顺序；
- 相同元素的相对位置；
- 边界划分问题[1]。
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n;
int a[N];
//啊哈算法P18
void quickSort(int l, int r) {
//当待排序的子序列长度为0或1（即left>right）时停止
if (l > r)
return;
int tmp = a[l]; //取当前数组区间首元素为基准数
int i = l;
int j = r;
while (i != j) {
//先从右往左找基准数右边第一个小于基准数的数
//TIP1 - 顺序很重要：基准数左侧均小于基准数，而右侧均大于基准数
//若先发动左指针找较大数，则会越过最终基准数应在的位置
while (a[j] >= tmp && i < j)
j--;
//再从左往右找基准数左边第一个大于基准数的数
//TIP2 - 判断条件中的“等于”很重要：
//若不考虑相等情况，那么相同元素的顺序将会改变，破坏排序的稳定性
while (a[i] <= tmp && i < j)
i++;
//若i与j指针未相遇，则交换i与j各自所指的数字
if (i < j)
swap(a[i], a[j]);
}
//此时i与j指针相遇，基准数归位
a[l] = a[i];
a[i] = tmp;
//左右分别递归
quickSort(l, i - 1);
quickSort(i + 1, r);
}
//法二
void quickSort2(int l, int r) {
if (l >= r)
return;
//始终取当前数组中位元素为基准数，无需根据比较结果将其移位
int tmp = a[(l + r) >> 1];
int i = l;
int j = r;
while (i <= j) {
//先从右往左找基准数右边第一个小于等于基准数的数
while (a[j] > tmp)
j--;
//再从左往右找基准数左边第一个大于等于基准数的数
while (a[i] < tmp)
i++;
//若i指针未越过j指针，则交换i与j，然后各自继续前进一步
//TIP3 - 边界问题：若此处不为≤，则会造成无限划分问题（将n分成0和n）
//原因：在数组递归到最终只有两个元素且有序的情况下，j会取到l-1
if (i <= j)
swap(a[i++], a[j--]);
}
quickSort2(l, j);
quickSort2(i, r);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
//quickSort(0, n - 1);
quickSort2(0, n - 1);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}
//法三
void quick_sort(int l, int r)
{
if(l==r)
return q[l];
LL x=q[(l+r)>>1];
int i=l-1;
int j=r+1;
while(i<j){
//为什么此处先发动左哨兵也没关系？
//因为判定条件并非“两哨兵相遇”
while(q[++i]<x);
while(q[--j]>x);
if(i<j)
swap(q[i],q[j]);
}
quick_sort(l, j);
quick_sort(j+1, r);
}