快速排序

大家最好都要掌握快排，很多时候要手写快速排序的。

基本思想

通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最终使整个序列有序。

算法步骤

1. 选取基准值x
2. 划分，根据选取的x将数组划分成小于等于x的部分和大于等于x的部分
3. 递归求解小于x和大于x的部分

容易遇到的问题

1. 基准值的选取：部分题目选取第一个数作为基准值会导致超时，可以通过选取中间的数作为基准值，或采用三数取中法。
2. i j的取值： i = l - 1, j = r + 1,为什么不是i = l, j = r。因为每次交换后，都有i++ j--，索性直接先改变i j的值，代码会简洁一些。
3. 无限分治问题： 每次写快排的时候基本都要调试一下，总是陷入死循环，原因是q[l..r]被划分为了q[l..l-1], q[l..r]，这里使用while(i < j) 就会避免这个问题。
4. 使用do while可以避免程序出现i j一直不更新的死循环情况。

C++代码 //快速读入模板深得潘老师真传 潘老师orz

using namespace std;
const int N = 1e5 + 5;
int q[N];
int n;
void QuickSort(int l,int r){
	if(l>=r)//为了跳出无限循环
		return ;
	int i = l - 1,j = r + 1,mid = q[(i+j) >> 1];
	while(i<j){
		do i++; while(q[i] < mid);
		do j--; while(q[j] > mid);
		if(i<j)
			swap(q[i],q[j]);
	}
	QuickSort(l,j);
	QuickSort(j+1,r);
}
void solve(){
	cin >> n ;
	for(int i=1;i<=n;i++){
		cin >> q[i];
	}
	QuickSort(0,n);
	for(int i=1;i<=n;i++){
		cout << q[i] << " ";
	}
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T = 1;
	// cin >> T ;
	while(T--) solve();
	return 0;
}