波波老师，我改了下代码逻辑，不好理解这种边界问题，这种逻辑下多边界判断我就晕了，您的代码确实好理解多了：）

Question

//1 嵌入您的代码能运行

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

//2不能运行

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

Answer 1

liuyubobobo 2018-06-16 10:36:05

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

----------

关于理解边界，一个关键就是：我们定义的变量的语意是什么！我们在书写逻辑时，要不停的维护变量的语意。印象里在这个课程的前面几章，我会一直强调这一点。在第五章讲解二分搜索法的时候，我会特别强调这一点。在我的课程，《玩转算法面试》中，在第三章的第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是开区间！请再体会一下，根据我们定义变量的语意的不同，我们的逻辑以及边界的位置就会改变：）

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

加油！

• 提问者 慕沐9313579 #1

  老师，您的代码我理解了，我自己改了逻辑之后就不能理解了。。。
  能麻烦看下这种逻辑下怎么理解吗

• liuyubobobo 回复 提问者 慕沐9313579 #2

  没有理解你的问题。你的代码是不能运行的？那为什么要理解？你自己改写的基本逻辑是什么？简单叙述一下？

• 提问者 慕沐9313579 #3

  老师你的代码
  while(true){//1
     while(i <= r && arr[i] < v )//2
         i++;
     while(j >= l+1 && arr[j] > v)//3
         j--;
     if(i > j)//or >=
         break;
     swap( arr[i] ,arr[j]);
     i++;
     j--;
  }
  我的代码
  while(i <= j){
     while(i <= j && arr[i] < v )
         i++;
     while(i <= j && arr[j] > v)
         j--;
     if(i > j)//or >=
         break;
     swap( arr[i] ,arr[j]);
     i++;
     j--;
  }
  我对1，2，3的地方改了下，我的代码那三个地方主要是加<还是<=有点迷糊

点开查看后面3条评论

Answer 2

提问者 慕沐9313579 2018-06-16 11:01:15

老师你的代码 

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的地方改了下，我的代码那三个地方主要是加<还是<=有点迷糊