双路排序法疑问

Question

如果数组是{100,100,100,…100,99,98,97,96,95,94…1}还是无法将等于v元素分散到左右两部分，

Answer 1

liuyubobobo 2018-12-15 03:16:41

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

加油！：）