对于为什么是while(i<=r && arr[i]<v) i++;而不是while(i<=r && arr[i]<=v) i++;的一点思考

Question

实验与结果：

将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方式则会将连续出现的这些值归为其中一方，使得两棵子树不平衡

不知道我的理解是否恰当

Answer 1

liuyubobobo 2017-01-13 20:53:05

非常非常非常正确！大赞实验精神和把问题彻底想明白的精神！！！

也感谢分享！：）

• 提问者 shanmufeng #1

  谢谢老师夸奖：）

• Dragonmage #2

  我一开始还以为<=比<快呢，感觉可以减少swap次数

• 慕娘1235822 #3

  老师，如果在随机选择pivot之后碰巧pivot的值没有变（如果在range[0，10]中选1百万个数这样的概率应该还是不小吧），那么以上说的a和b都会产生极度不平衡的递归子树吧，不知道我理解得对不对？

点开查看后面3条评论

Answer 2

IntenseCrazy 2017-02-19 21:26:14

意思和楼主差不多，只是想换一种表达

我觉得是这样的：a方式：不会进入while循环，直接交换数据(对于相等的情况可以不需要)后，i++，j--进行下一轮比较。两路都有重复的元素这样的递归树比较均衡。

                          b方式 : 会将重复元素归为一路，这样就不平衡。

• 西西雪凌 #1

  说的很好

Answer 3

慕UI5306203 2018-06-06 18:08:14

让重复相等的数据不归为一颗子树所有，从而保持两个子树的平衡性。

Answer 4

LukeInCanada 2020-04-01 05:56:12

a. 在碰到很多连续相同数字的情况下，i只向后移动一次，同时j至少向前移动一次，相对平衡。

b, 在碰到很多连续相同数字的情况下, i首先不停向后移动，直到满足条件为止，造成不平衡。

Answer 5

船长will 2019-11-04 18:01:43

直观来讲，用小于号，遇到大量相等的partition元素的时候，程序可以通过i++,j++使得树的分裂点更居中，因此树也更趋于平衡

Answer 6

慕设计7465963 2018-12-14 16:48:09

a的情况也应该是,第一次partition在数组的倒数第二位：{0,0,0,...,0,0,0,1}

• 慕娘1235822 #1

  我觉得提问的同学pivot选的是0，而你选的是1，如果pivot是1的话a和b应该是一样的，还是会发生退化的现象。不知道我理解得对不对，希望老师解答下

• liuyubobobo 回复 慕娘1235822 #2

  这一轮会退化，但这一轮之后，1放到了正确的位置（最后），剩下的未处理元素是全0，使用课程中的二路快排，可以生成平衡的递归树。这一轮的退化不会使得整个算法退化为O(n^2)的算法：）

• 慕娘1235822 回复 liuyubobobo #3

  明白了，谢谢老师~

Answer 7

三郎_ 2018-11-20 17:33:20

看来我的理解能力有问题了，这块想不明白~~

Answer 8

水瓶座妙妙 2017-03-03 20:27:40

一下就看明白了！谢谢楼主！