2回答

liuyubobobo

2018-06-16

已采纳

赞！：）理解了就有进步！

----------

关于理解边界，一个关键就是：我们定义的变量的语意是什么！我们在书写逻辑时，要不停的维护变量的语意。印象里在这个课程的前面几章，我会一直强调这一点。在第五章讲解二分搜索法的时候，我会特别强调这一点。在我的课程，《玩转算法面试》中，在第三章的第1小节和第2小节，我还特别又针对二分搜索法举例，告诉大家，我们写算法的逻辑，只要维护住变量的语意，变量究竟是什么意思，可以随便定义的。如果没有买那个课程，在这个课程中学习完二分搜索法以后，也可以参考一下《玩转算法面试》中，在第三章的第1小节和第2小节的代码，理解一下为什么这两个不同的写法都是对的。（因为变量的语意变了，边界条件就变了！）传送门：https://github.com/liuyubobobo/Play-with-Algorithm-Interview

回到你的代码中。在我的原始代码中，对i和j的定义是这样的：

// arr[l+1...i) <= v; arr(j...r] >= v    
int i = l+1, j = r;

这个注释可以在我提供的代码中找到。传送门：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/07-Quick-Sort-Deal-With-Identical-Keys/main.cpp

注意，i和j都是开区间（这个定义直接影响了i和j的初值!），这就意味着：在你标记为的地方，只是i < j是不够的，因为i和j都再开区间，所以arr[i]和arr[j]的值是还没有考虑的！i < j的时候，在最极端的情况下， i + 1 == j的时候，中间还剩下两个元素（i和j所在的元素）没有考虑！

这也是为什么，在你标记为2，3的地方，我的逻辑中，i可以取到r（i<=r而不是i<r），j可以取到l+1（j>=l+1而不是j>l+1）的原因，因为i和j是开区间！请再体会一下，根据我们定义变量的语意的不同，我们的逻辑以及边界的位置就会改变：）

最后，上面我说的二分搜索法的例子，个人认为还是很重要的，学到那里的时候，一定要自己研究一下哦：）

加油！

2

6

慕沐9313579

非常感谢！

2018-06-16

共6条回复

慕沐9313579

提问者

2018-06-16

老师你的代码 

while(true){//1
   while(i <=r && arr[i] < v )//2
       i++;
   while(j>= l+1 && arr[j] > v)//3
       j--;
   if(i > j)
       break;
   swap( arr[i] ,arr[j]);
   i++;
   j--;
}

我改了后

while(i <= j){//1
   while(i <= j && arr[i] < v )//2
       i++;
   while(i <= j && arr[j] > v)//3
       j--;
   if(i > j)
       break;
   swap( arr[i] ,arr[j]);
   i++;
   j--;
}

我对1，2，3的地方改了下，我的代码那三个地方主要是加<还是<=有点迷糊

0

0