为什么是 if( i > j ) break; 而不是if( i >=j ) break; ?

Question

按照前面的思路，只要 i 和 j 重合便可得到要返回的索引号，此时返回任意一个就行。

Answer 1

liuyubobobo 2017-03-05 21:25:48

恩恩，是的。赞。这里用 i >= j 就break掉是没问题的：）

• 易萧 #1

  但是如果i和j同时指向的元素刚好等于标定的键值，此时交换的键值一样，假设有很多重复键值，那么选中这个键值的可能性就很高，除了第一遍排序之外，后面每次选中同一元素实际上都只有大量重复键值在不断移动，剩下的都没变，最后一个元素仍然可能是相同键值，这样或许会导致不必要的重复排序吧，所以应该尽快让相同的键值靠拢。不知道这个想法有没有问题

• liuyubobobo 回复 易萧 #2

  我把对你的问题回答放在了这个问题的一级回答中，请参考。加油：）

• shanmufeng #3

  我觉得改成i>=j会有问题，比如当i和j刚好同时指向同一个元素时就break掉的话，其实并不确定这个元素与标定点v的大小关系吧？然而在外层函数还有一个操作swap(arr[l],arr[j])，即默认j最后指定的数归为<=v那一类。但是，我测试了下改成i>=j确实没有报错，没想通。。。
  int __partition2(T arr[], int l, int r){
      swap(arr[l], arr[rand()%(r-l+1)+l]);
      T v = arr[l];
      //arr[l+1...i)<=v;arr(j...r]>=v; make balance!
      int i = l+1,j=r;
      while(true){
          while(i<=j && arr[i]<v)
              i++;
          while(j>=i && arr[j]>v)
              j--;
  
          if(i>j)
              break;
  
          swap(arr[i],arr[j]);
          i++;
          j--;
      }
      swap(arr[l],arr[j]);
      return j;
  }

点开查看后面3条评论

Answer 2

liuyubobobo 2017-06-06 00:16:24

回复 @易萧：

你说的问题是双路快排中判断arr[i]和arr[j]与v的关系，而不是这个i和j的循环终止条件。请看课程代码的注释：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

事实上，双路快排的关键恰恰是要产生这些“重复键值的不断移动”，换来的结果是：让我们的partition尽量平分。在问答区，这个同学很好的解答了这个问题：http://coding.imooc.com/learn/questiondetail/4920.html

你也可以尝试生成一个有大量重复键值的数组，使用两种边界进行排序，比较两种写法代码运行率的不同。之后，再使用一个含有全部键值都是重复数字的小数组，比如[8,8,8,8,8,8,8,8]，跟踪一遍程序，看看两种方法partition结果的不同，你就理解了：）

加油！