关于第一版和双路快速排序的差异
老师关于第一版的快速排序算法和双路快速排序在时间性能的差异主要就是在于针对数组中元素都相同的情况，双路快速排序更加高效，其他情况两者差距不是很大是吗？
双路快速排序的优化是不是就是主要在于针对元素相同的情况，我们同时交换并移动了指针，从而平均分配了下一次迭代的空间，进而优化了时间？如果像下面这种写法，这种性能优化是不是就没有了?
相关代码：
while (left <= right) {
if (array[left] < pivot) {
left++;
} else if (array[right] >= pivot) {
right--;
} else {
swap(array, left++, right--);
}
}正在回答
1)
是的，双路快速排序的思路主要是为了避免在存在大量相同元素的情况下，第一版排序（我称之为单路快排：））的退化。
如果你确定你处理的数据不包含大量重复数据，甚至没有重复数据，使用单路快速排序足够（甚至更优，因为单路快速排序内部无论是变量的数量，还是 if 判断的数量，都更少，常数级开销更小。）
2）
非常非常赞！是的。一旦比较里有了等号，双路快排也会退化。
印象里这一点在课程中提及过。但我强烈建议大家具体实验一下，课程代码中：https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/12-More-about-QuickSort/03-QuickSort-2-Ways/src/QuickSort.java
66 行和 69 行的 arr[i].compareTo(arr[l]) < 0 和 arr[j].compareTo(arr[l]) > 0 如果改成 <= 和 >=，会发生什么？
也正因为如此，双路快排虽然看起来思想简单，但其实实现起来非常容易出错，乃至甚至很多教科书根本不介绍这个思路。因为，在实践中，可以使用双路快排的地方，也就可以使用三路快排。如果要避免所有的快排过程中可能发生的退化情况，三路快排更常用：）（三路快排课程后续会介绍。）
继续加油！：）
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧
0 星