1回答

liuyubobobo

2018-12-15

可以做这样的一个数据测试一下试试看？你会发现双路快排依然是很快的。（注意边界，一定是课程中的代码。具体参考：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）

这个数据本质就是有大量重复元素的数据。一开始的划分点大概率是一个100，之后会将近乎一半其他100分到这个100的右侧；1-99和另一半100分到左侧。两边递归。其实每一部分还是有大量重复元素的数组。双路快排保证了对大量重复元素数组的有效性，这也是我们引入双路快排，讲解双路快排的原因！

如果不理解为什么双路快拍能对这样的数据有效，可以使用一个小的数据用力调试跟踪试试看？比如：

[10, 10, 10, 10, 10, 10, 10, 3, 2, 1]

加油！：）

0

0