快速排序的最坏情况何时发生？

答案取决于选择pivot的策略。在快速排序的早期版本中，选择最左边（或最右边）的元素作为轴心，最糟糕的情况出现在以下情况中。

1） 数组已按相同顺序排序。 2） 数组已按相反顺序排序。 3） 所有元素都相同（情况1和2的特例）

由于这些情况在用例中非常常见，所以通过为轴心选择随机索引、选择分区的中间索引，或者（尤其是对于较长的分区）为轴心选择分区的第一个、中间和最后一个元素的中间值，问题很容易解决。通过这些修改，快速排序的最坏情况发生的几率会降低，但如果输入数组始终选择最大（或最小）元素作为轴心，则仍然可能发生最坏情况。

参考资料： http://en.wikipedia.org/wiki/Quicksort