快排

做法

快排，基于分治

1.确定分界点，q[l]，q[(l+r)/2]，q[r]，随机，四种都可以，但是推荐q[(l+r)/2]

2.[重点]调整区间，划分2个区间，使得左半边所有的数<=x，右半边所有的数>=x，注意，x不一定在两个区间交界处，可能在很奇怪的位置

3.递归处理左右两段

比较暴力的做法

先开两数组，a，b，然后把<=x放到a数组，>x的放到b数组，然后a数组的数放入q数组，b数组的数放入q数组

 如果忘了如何优雅写快排，就可以这样临时替代一下，虽然双倍空间，但是时间也是线性的

优美的做法

做法解析

基于双指针

 i在左端点开始往右找，j在右端点开始往左找。

i找每个数，如果q[i]<x ，i++，直到q[i]>=x，i停止。j找每个数，如果q[j]>x，j--，直到q[j]<=x，j停止

此时，i，j两个数正好相反，需要交换一下，swap(q[i], q[j])，交换完之后，然后i++，j--，因为两个数排好了

重复此过程，直到i，j相遇，停止

为什么是对的？

无论任何时刻，i左边的数都是<x的，j右边的数都是>=x的。等到i，j相遇，停止。会完美的划分出左半边<x，右半边>x，满足划分区间的性质

特殊求解

刚刚都是特殊情况，太抽象了，现在举个例子

数列3 1 2 3 5，假设x=3

i=1，发现3>=3，停止

j=5，发现5>3，j--，j=4，发现3<=3，停止

交换两数，i=2，j=3

i=2，1<3，i++，i=3。     2<3，i++，i=4         i=4，发现3>=3，停止

j=3，发现2<=3，停止

此时i，j已经穿过了，所以不交换2数

数列变成 3 1 2 3 5

                      j  i

我们发现，发现左边3个数（j）都<=3，右边2个数（i）都>=3

写法

注意边界问题！！！

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n, a[N];
void quick_sort(int a[], int L, int R)
{
	if (L>=R) return; //边界，区间只有1个数或者没有数就不排序了 
	
	int x=a[(L+R)/2]; //第一步，确定分界点 但是次情况不能取a[R]，不然有边界问题，例如n=2, a={1,2}，会死循环
	int i=L-1, j=R+1; //两个指针往左右两侧扩一格，跟后面写法有关 
	//原因：因为可以发现，i，j交换完都会移动一位，所以每次不管三七二十一先移动i，j 
	while (i<j) //每次迭代，移动再交换，算一次迭代
	{
		do i++; while (a[i]<x); //位置ok，往后面看 
		do j--; while (a[j]>x); //位置ok，往前面看 
		if (i<j) swap(a[i], a[j]); //需要交换位置了，前提是i<j 
	}
	
	//递归处理左右两边 
	quick_sort(a, L, j);
	quick_sort(a, j+1, R);
}
int main() 
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++) scanf("%d", &a[i]);
	quick_sort(a, 1, n);
	
	for (int i=1; i<=n; i++) printf("%d ", a[i]);
	return 0;
}