返回信息流这个是算法那本书第303页的练习2.3.11。
> Suppose that we scan over items with keys equal to the partitioning item’s key
instead of stopping the scans when we encounter them. Show that the running time
of this version of quicksort is quadratic for all arrays with just a constant number of
distinct keys.
快速排序的算法复杂度应该是取决于每次那个切分元素对原数组的切分情况，如果切分的情况不理想，比如数组本身是已经排序的或者倒序的话，则会导致该算法的复杂度变为二次方，所以在排序之前对输入的数组进行随机的排列有助于避免这种情况的发生。但我不明白为什么跳过相等元素会导致算法在排序含有重复元素的数组时，复杂度也变为quadratic。
书上对应的代码：
```java
public class Quick {
public static void sort(Comparable[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
}
public static int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi+1;
Comparable v = a[lo];
while (true) {
while (less(a[++i], v)) if (i == hi) break;
while (less(v, a[--j])) if (j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
}
```
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #96194同步于 2018/7/13
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】快速排序一个实现细节对算法复杂度的影响
youdianer
2018/7/13镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
楼主可以假设所有元素都相等，比如全为1，
然后如果将partition中上比较运算less改为lessequal，
在第一次进入while(true)循环时，那么由于所有元素都相等，所以while(lessequal(a[++i],v))的判断条件一直成立，最后i==hi跳出while循环，因此i变成了hi，
同理j变成了lo而跳出while循环，那么i>=j成立，所以最后跳出整个while(true)循环，return lo。
也就是说每次找到的划分位置是lo，
也就是每次划分都是左边0个元素，右边hi-lo+2个元素，因此退化为o(n^2)的时间复杂度了。
知道了，谢谢。之前把循环看恍了。[ema3]
【 在 latstars 的大作中提到: 】
: 楼主可以假设所有元素都相等，比如全为1，
: 然后如果将partition中上比较运算less改为lessequal，
: 在第一次进入while(true)循环时，那么由于所有元素都相等，所以while(lessequal(a[++i],v))的判断条件一直成立，最后i==hi跳出while循环，因此i变成了hi，
: ...................