排序算法之快速排序

第一

在一段需要排序的序列中，确定分界点x（可以是左端点，右端点，中间端点，任意端点，不同的端点带来的时间复杂度都不相同有好有坏），假设一个数组的左端点是 l ，右端点是 r  ,中间端点则为 l + r>>1  

第二

调整范围，给定两个指针 i 和 j，分别从最左端和最右端开始向中间扫，使得所有的i指针左边的元素都<= x,同理j就是>=x，如果遇到不满足的元素时，其中一个指针就停下来，交换两个元素

第三

递归处理左右两边的元素，注意:选择的分界点不同时，需要递归的左右的边界情况也不相同

#include 
#include
using namespace std;
const int N = 1e6+10;
int n;
int q[N];
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];//这里如果使用左边界的话会超时
    //这里为什么左右边界不是从l和r开始呢？ 
    //这是因为，向中间扫的时候，他是不管三七二十一，都先向中间移动一次，之后再判断时候满足条件，所以需要偏移//一位
    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()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    quick_sort(q,0,n-1);
    for (int i = 0; i < n; i ++ ) printf("%d ",q[i]);
    return 0;
}

这里留个问题没搞懂，为什么需要`l+r+1`加一，什么时候需要加一？以及使用`while (q[i] <= x);while (q[j] >= x);`
行不行？为什么？这些东西我觉得都是研究的边界的问题，可以不去搞懂，写算法时，记住一个模板即可，因为这些模板都是前人经过很多研究千锤百炼的结果可以避开这些坑。主要时快排的思想需要搞懂！