AcWing 785. 快速排序

题面：
给定你一个长度为 \(n\) 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

原题链接：785. 快速排序 - AcWing

需要注意的几个点：

1. 左右哨兵的发动顺序；
2. 相同元素的相对位置；
3. 边界划分问题^[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);
}