快排的恶化

为什么当存在大量重复元素时，快排的效率会出现明显的下降？

i用来遍历，j用来分割大于标记元素区间和小于标记元素区间；
升序快排在处理小于标记元素时，会将i与j+1下标的元素进行交换；当处理大于等于标记元素时，会直接让i++；
如果重复元素并非最大值，而是一个中间值，那么在某次排序中，中间值一定会被当做小于标记元素的元素，那么就会频繁的进行将i与j+1下标的元素进行交换的操作，如此频繁的操作，就是快排恶化的原因。

参考

快速排序 详解（快速排序 双路快排 三路快排）