对于为什么是while(i<=r && arr[i]<v) i++;而不是while(i<=r && arr[i]<=v) i++;的一点思考
来源：3-7 双路快速排序法
shanmufeng
2017-01-13
实验与结果：
将arr[i]<v和arr[j]>v：
while(i<=r && arr[i]<v) i++; while(j>=l+1 && arr[j]>v) j--;
改为arr[i]<=v和arr[j]>=v：
while(i<=r && arr[i]<=v) i++; while(j>=l+1 && arr[j]>=v) j--;
testSort就会运行100s+，也就是说，多了个等号的判断也会造成两棵子树不平衡
讨论：
比如数组 1,0,0, ..., 0, 0
a. 对于arr[i]<v和arr[j]>v的方式，第一次partition得到的分点是数组中间；
b. 对于arr[i]<=v和arr[j]>=v的方式，第一次partition得到的分点是数组的倒数第二个。
这是因为对于连续出现相等的情况，a方式会交换i和j的值；而b方式则会将连续出现的这些值归为其中一方，使得两棵子树不平衡
不知道我的理解是否恰当
8回答
-
非常非常非常正确！大赞实验精神和把问题彻底想明白的精神！！！
也感谢分享！：）
2262020-06-04 -
IntenseCrazy
2017-02-19
意思和楼主差不多，只是想换一种表达
我觉得是这样的：a方式：不会进入while循环，直接交换数据(对于相等的情况可以不需要)后，i++，j--进行下一轮比较。两路都有重复的元素这样的递归树比较均衡。
b方式 : 会将重复元素归为一路，这样就不平衡。
412018-05-18 -
慕UI5306203
2018-06-06
让重复相等的数据不归为一颗子树所有，从而保持两个子树的平衡性。
20 -
LukeInCanada
2020-04-01
a. 在碰到很多连续相同数字的情况下，i只向后移动一次，同时j至少向前移动一次，相对平衡。
b, 在碰到很多连续相同数字的情况下, i首先不停向后移动，直到满足条件为止，造成不平衡。
10 -
船长will
2019-11-04
直观来讲，用小于号，遇到大量相等的partition元素的时候，程序可以通过i++,j++使得树的分裂点更居中，因此树也更趋于平衡
00 -
慕设计7465963
2018-12-14
a的情况也应该是,第一次partition在数组的倒数第二位：{0,0,0,...,0,0,0,1}
032019-01-18 -
三郎_
2018-11-20
看来我的理解能力有问题了，这块想不明白~~
00 -
水瓶座妙妙
2017-03-03
一下就看明白了！谢谢楼主！
00
相似问题