目录
快速排序
快排属于分治算法
基本思想：当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。
总结下来即三步：
-
分成子问题
-
递归处理子问题
-
子问题合并
快排的具体实现
-
确定分界点x，这里取 x = q[l + r >> 1]。
-
划分区间：我们将一堆数分为两堆，左边分为<=x的，右边分为>=x。
-
递归处理左右两堆。
难点在于第2点，我们如何优雅而又简单的划分区间。这里我们可以使用双指针算法（不需要开辟额外空间）。
下面画图举例：
具体代码实现：
void quick_sort(int q[],int l,int r){
if(l>=r) return;//递归的结束条件
int i = l - 1,j = r + 1,x = q[l + r >> 1];//这里 i = l - 1,j = r + 1,
//为什么要这样,是因为下面的 ++i,--j。
// >> 1 <=> /2
// << 1 <=> *2
//(运算效率：移位 > 赋值 > 大小比较 > 加法 > 减法 > 乘法 > 取模 > 除法。)
while(i<j){
while(q[++ i]<x);//当前值<x，指针就继续往右走，直到当前值>=x。
while(q[-- j]>x);//当前值>x，指针就继续往左走，直到当前值<=x。
//交换两个值 => 达到左边都是小于x的值，右边都是大于x的值。
//异或 ^ 骚操作（不使用额外变量）
if(i<j){
q[i] = q[i] ^ q[j];
q[j] = q[i] ^ q[j];
q[i] = q[i] ^ q[j];
}
}
//递归处理（l，j) (j + 1, r)。
//边界问题建议背过。
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
