快速排序

q[N]指的是待排序的数组
基本思路：
1.确定分界点 ：

• 可以是q[l], q[l + r >> 1], q[r]。
  使用q[l + r >> 1], 可以避免出现边界问题

2.调整区间
3.重复多次

时间复杂度：

    最好为O(n log^n), 最坏为O(n^2）; 
                一般情况下不会被卡， 因为 x = q[l + r >> 1], 中间值随机选的， 不容易出现极端情况
 ![题解.png](https://cdn.acwing.com/media/article/image/2021/12/23/98720_1862fd4763-题解.png) 

C++代码

void quick_sort(int l, int r)
{
    if(l >= r) return ; 当区间里面只有一个数或者没有数时结束
    //1. 确定分界点
    int i = l - 1, j = r + 1, x = q[l + r >> 1];// 之所以这样设置是因为后面代码使用的是                                                                    do-while循环，无论如何必须执行一次
    while(i < j)
    {
        do i ++; while(q[i] < x); //寻找左半边部分大于 x 的数
        do j --; while(q[j] > x); //寻找又半边部分小于 x 的数
        //2. 调整区间
        if(i < j) swap(q[i], q[j]); // 当两个指针还没相遇时，交换两个元素。 当整个循环结束后，
                                    // 满足左半边的数小于等于又半边的数
    }
    //3. 重复多次
    quick_sort(l, j), quick_sort(j + 1, r);
    // 注意这里填的是 j ， 上一个while()循环结束后，j <= i。

}

关于快速排序和后面学的归并排序， 我的一些个人理解

    1. 快排的时间复杂度最好为O(nlong^n), 最坏为O(n^2);
        归并排序的时间复杂度为O(nlog^n), 它的时间复杂度是确定的。

    2. 在执行的策略上也不同。 快排是从上到下，每次都确保左边的数 <= 右边的数
                            归并排序是从下到上逐层排好序， 所以需要开一个额外的数组存储已经排好序的
                            然后将其返回给q[N];