思路：

快速排序主要运用了分治、递归的思路
主要分为三步骤：

• 确定分界点
  可以是数组起始位置，也可以是数组最后位置，当然也可以是数组中间位置等任意随机位置
• 调整数组
  调整数组元素位置，使得分界点左边的元素大小小于等于分界点元素，分界点右边的元素大小大于等于分界点元素
• 递归地处理左右两段

模板代码：

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;                  //如果数组里面只有一个元素，直接返回，不用再排序
    //这里把i作为第一个元素的前一个，j作为最后一个元素的后一个，分界点取为中间元素
    int i = l - 1, j = r + 1, x = q[l + r >> 1]; //加法运算优先级>右移运算，所以这里有没有括号都没关系
    while (i < j)     //两个指针只要没碰上，就一直处理
    {
        do i ++ ; while (q[i] < x);   //前指针先往后移，再判断
        do j -- ; while (q[j] > x);   //后指针先往前移，再判断
        if (i < j) swap(q[i], q[j]);  //但是还是要保证i<j,反过来就没必要换了
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);  //递归地对l-j，j+1-r去快速排序
}
作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing