2回答

liuyubobobo

2017-03-05

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

1

6

liuyubobobo

回复

shanmufeng

：）赞思考！

2017-07-01

共6条回复

liuyubobobo

2017-06-06

回复 @易萧：

你说的问题是双路快排中判断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结果的不同，你就理解了：）

加油！

0

0