快排

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];
    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);
}

1. 为什么l>=r时结束
   • 当l=r时，说明当前子数组只有一个元素，已经是排好序的
   • 当l>r时，说明当前子数组为空，不需要排序

2. 为什么初始化int i = l - 1, j = r + 1
   因为在进入主循环前，i和j会先被更新（通过do i++和do j--），l-1和r+1是为了预先补回来这个1

3. 为什么i>=j时结束
   因为此时所有元素都已经被正确划分：
   • 索引j及其左侧的所有元素都≤轴心值
   • 索引j右侧的所有元素都≥轴心值

4. 为什么递归参数是j, j+1而不是i
   可以用i来划分，这里是我记错了，应该是 “不能改用quick_sort(q, l, j-1), quick_sort(q, j, r)作为划分”，至于为什么，可以自己模拟一下3 1 4 2 5的第一趟排序过程。

5. 注意区分i,j和l,r

6. do...while的语法——1️⃣不能加{ } 2️⃣while后面要有;

   do i++; while(q[i]<x); //correct
   do {j--}; while(q[j]>x)//error