这篇文章是我刚学算法的时候写的。好家伙，我在第一个问题上卡了好久。但好消息是我没有得过且过。我花了一个晚上和一个早上的时间来经历所有的情况并思考迭代的过程。之后就觉得自己进门了，有种没有被其他后续问题卡那么久的感觉。整理代码运行状态很简单：MemoryLimitExceeded长时间。最后，我琢磨了很久的越线这件事。总结一句话：避免func(l,r){...func(l,r)...}（递归时传给下一层的边界值不收缩），因为这是一个无穷大环形。如何避免？例如，在func(l,r){func(l,j),func(j+1,r)}中，j至少满足j>r（j离开r，防止func(l,j)被func(l,r))，它是可用的。#includeusingnamespacestd;constintN=1e6+10;intn;intq[N];voidquick_sort(intq[],intl,intr){if(l>=r)return;inti=l-1,j=r+1,x=q[l+r>>1];while(ix);if(i>1];.那么我可以执行以下操作吗？x=q[l+r>>1];...quick_sort(q,l,j-1),quick_sort(q,j,r);//这不可以吗？x=q[l+r>>1];...quick_sort(q,l,i-1),quick_sort(q,i,r);//或者这不可能吗？x=q[l+r>>1];...quick_sort(q,l,i),quick_sort(q,i+1,r);//这不可能吗？x=q[l+r+1>>1];...quick_sort(q,l,j),quick_sort(q,j+1,r);//这不可能吗？x=q[l+r+1>>1];...quick_sort(q,l,j-1),quick_sort(q,j,r);//这不可能吗？x=q[l+r+1>>1];...quick_sort(q,l,i),quick_sort(q,i+1,r);以上都不行，我一一举出反例。我们输入一个长度为2的数组，然后第一层循环：l=0,r=1（即quick_sort(0,1)），如果进入第二层循环，就会有quick_sort(0,1),则陷入死循环。下表中“传递给函数的i,j”是指调用quick_sort(q,l,?i/j),quick_sort(q,?i/j,r)时i,j的值。在下表中，最后一列的标记x表示程序将陷入死循环。对于intmid=l+r>>1;：可以看出当intmid=l+r>>1;时，四种组合中只有jj+1经受住了01和10的双重考验。对于intmid=l+r+1>>1;：可以看出当intmid=l+r+1>>1;时，四种组合中只有i-1i经受住了01和10测试。为什么是这样？这里有一个相关的证明：AcWing785.快速排序算法的证明和边界分析[1]如果你迫不及待地想看上面更严谨的证明，你可以看一下我写在文末的，我在里面理解笨办法：intmid=l+r>>1;：可以证明j的取值范围是[l,r-1]，所以对于边界组合jj+1有quick_sort(q,l,j小于r),quick_sort(q,j+1大于l,r),quick_sort(q,l,r)永远不会出现。intmid=l+r+1>>1;:可以证明i的取值范围是[l+1,r],所以对于边界组合i-1i有quick_sort(q,l,i-1小于r),quick_sort(q,i大于l,r),永远不会有quick_sort(q,l,r)出现。OK，那么下面就是背诵：快速排序中，intmid=l+r>>1;（mid向下取整），就是jj+1，因为j的取值范围是[lr-1]我个人不喜欢背的，还是知道原理的，感觉可以很快推断和可靠。推导如下。以一种清晰但笨拙的方式证明当mid向下舍入时j属于[l,r-1]。向下取整时，j属于[l,r-1]==等价于==向下取整时，j--至少执行了两次可以看出，三种情况下j--都至少执行了两次.情况1：j不再是q[j]>xatr,i仍然满足q[i]x);step389step4ijswap(q[i],q[j]);step5ijdoi++;while(q[i]x);跳出循环while(ixatr,i仍然满足q[i]x，但i不再是q[i]x);step389跳出循环while(ix，因此，会继续执行j--，j必须小于r。情况3：j不再是q[j]>x在r，i不再是q[i]x);step388step4ijswap(q[i],q[j]);step5ijdoi++;while(q[i]x);跳转out循环while(ixatr,i不再是q[i]>1;那么一定有r=mid;，因为mid取下Integer，当l
