双路快速排序这两个while循环条件，为什么i<=r以及j>=l+1 而不是i<=j

Question

RT..

Answer 1

liuyubobobo 2017-06-20 23:16:50

没有理解你的问题。双路快排在课程中有动画演示解释这一思路是如何运行的，在i<=r和j>=l+1的时候分别有自己的操作。请问你认为这些操作有什么问题？你认为应该改成在i<=j的时候进行什么操作？请贴出你认为正确的完整或者部分代码以方便讨论：）

• 提问者 易萧 #1

  大概是这样，下面代码是我自己写的但是写到这里的时候我参照了您的代码：
  while(i<=r && arr[i]<v) i++;
  while(j>=l+1 && arr[j]>v) j--;
  就是要保证 i 和 j 都不会越界的这个条件，如果改成以下：
  while(i<=j && arr[i]<v) i++;
  while(i<=j && arr[j]>v) j--;
  我想的是，当左指针i和右指针j相遇了，就可以停止判断了吧。这样是否可以呢，其它的不变。好像逻辑上没什么不一样，按原来的代码，如果i>j了，后面一个条件也自然不会成立了。但是就是怕万一后者有什么我自己没有发现的漏洞，所以就是求个断定。。。

• liuyubobobo 回复 提问者 易萧 #2

  理解了。非常非常赞！你的修改方式是可以的，而且在一些情况下效率更优，减少了一些比较次数！赞思考！

• 提问者 易萧 #3

  非常感谢！

点开查看后面3条评论