/*
    时间：2021年12月19日23:51:40 
    内容： 快速排序算法模板 
    心得： 在使用快排的时候，一定要注意循环结束的条件，以及递归处理左边，右边的边界~
*/ 
// 这里我们实现从小到大排序 如果要实现从大到小排序 我们只需要改第13 14行 ~ 
void Quicksort(int q[], int l, int r)  // 给定要排序的数组 ，左边界，右边界 
{
    if(l >= r) return;    // 如果这个数组只有一个数或者不存在 则不需要排序 
    int i = l - 1, j = r + 1;     // 根据y总给的模板， 这里让 i 指向 左边界的前一个位置，j指向右边界的后一个位置，这样方便后面do...while()的操作 
    int p = q[i + j >> 1];   // 我们让标准数为中间值  >> 为右移运算符 >> 1 相当于除2   比如说 0101 右移1的话 为 010 开始0101是 5， 现在010 是 2 
    while(i < j)   // 只要左指针与右指针不重合 
    {
        do i++; while(q[i] < p);  // 我们记录一下左边第一个大于标准值的数 
        do j--; while(q[j] > p);  // 我们再记录一下右边第一个小于标准值的数 
        if(i < j) swap(q[i], q[j]);  // 如果 左指针不与右指针重合， 证明还没有完全遍历数组中所有的数， 此时我们交换左右两边各不满足要求的数，这样的话，就可以使小于标准值的数在左边，大于标准值的数在右边 
    } 
    Quicksort(q, l, j), Quicksort(q, j + 1, r);  //  此时我们已经得到了标准值所在的位置（标准值左边的数都小于标准值，右边的数都大于他），我们在递归排序左边，递归排序右边~ 
}