快速排序
算法思想
快排的思想是基于分治法，其思路是：
- 确定分界点：给定要排序的数组
q，先在数组中找一个数作为分界点值x，分界点可以取左边界值x = q[l]，可以取右边界值x = q[r]，可以取数组中间的数x = q[l + r >> 1]，也可以随机取一个。 - 调整区间：将数组划分成两个区间，使得左半部分所有的数都
<= x，右半部分所有的数都>= x。 - 递归处理左右两个区间。
快排有多种实现方法，在y总的模板里，分界点的位置不一定是x，因为x参与交换之后仍然会被留在左右区间中的一个里。
注意点1：指针移动的判断不带等号
使用两个指针i和j分别指向要处理的区间的左右两侧，每次向中间移动。只要q[i] < x成立就说明i位置的数在左侧区间是合理的，所以i ++，直到q[i] >= x停下来。接下来去移动j，只要q[j] > x成立就说明j位置的数在右侧区间是合理的，所以j --，直到q[j] <= x停下来。
这里考虑一个边界问题，为什么移动i和j指针的条件是q[i] < x和q[j] > x，而不是q[i] <= x和q[j] >= x？因为如果选取的x是数组里最大的数，那么一直都满足q[i] <= x，所以i会一直++发生越界都不会停下来。同理，如果选取的x是数组里最小的数，那么一直都满足q[j] >= x，所以j会一直发生越界都不会停下来。
注意点2：在交换前检查指针相对位置
当两个指针都停下来之后，这一对数都是错位的，所以把它们交换一下，交换完成之后q[i] < x并且q[j] > x，下一轮就可以让i和j（只要满足i < j）继续对向移动了。
这里考虑一个边界问题，试想q[i]和q[j]在i == j - 1时停下来做交换的场景，交换完成之后i和j会各自前进（i ++, j --）一步，形成i > j（具体是i == j + 1）的不合法局面，这时候就不应该做交换了，所以在swap之前需要再判断一次i < j。
注意点3：使用do-while而不是while循环
指针i和j初始化为数组两侧外一个元素，即i = l - 1，j = r + 1，然后在数组中使用do-while循环每次先进行一次指针的移动，再去看循环条件。
这里考虑一个边界问题，为什么不能让i = l和j = r然后使用while循环代替do-while循环？因为如果数组中存在重复的数字，那么某一轮可能存在i和j都指向重复的数字，并且划分数字x也是这个数字，那么while (q[i] < x)和while (q[j] > x)判断不成立不会进入，又因为q[i] = q[j] = x，交换它们之后这个局面仍然不会改变，所以要使用do-while循环，确保每次两个指针都至少会移动一步，以保证上一次交换的结果能被走掉。
注意点4：选取数组中间的数字作为划分值
与其选取左右两端的数作为划分值，不妨选取数组中间的数字。
这里考虑一个边界问题，如果数组已经是有序的了，那么选取数组开头或者结尾的数字就意味着每次将长度为 \(n\) 的数组划分成了长度为 \(1\) 和 \(n-1\) 的两段，这时候快速排序递归处理的子问题规模还是这么大，总的时间复杂度就达到了 \(O(n^2)\)，为了避免这种情况，要选取数组中间的数字作为划分值。
注意点5：使用[l, j]作为区间左半边而不是[l, i]
在快排一轮的处理结束后，递归处理的两个子区间应该是[l, j]、[j + 1, r]而不是[l, i]、[i + 1, r]。
这里考虑一个边界问题，试想q[i]和q[j]在i == j - 1时停下来做交换的场景，交换完成之后i和j会各自前进（i ++, j --）一步，形成i > j（具体是i == j + 1）的不合法局面。在这个局面下，满足性质<= x的区间是[l, j]而不是[l, i]，因此划分的两个区间是[l, j]、[j + 1, r]。
时间复杂度：\(O(N\log N)\)
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int a[], 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()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> q[i];
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++ ) cout << q[i] << ' ';
puts("");
return 0;
}