什么情况下快速排序最慢?

158 2月之前 算法

答案

这个得看pivot基准元素枢轴)的选择策略。

如果选择最左面最右面的元素作为基准元素,那最坏的情况就会在:

  1. 数组已经是正序排过序的。
  2. 数组已经是倒序排过序的。
  3. 所有的元素都相同(1、2的特殊情况)。

因为这些案例在用例中十分常见,所以这个问题可以通过要么选择一个随机的基准元素,或者选择一个分区中间的下标作为基准元素,或者(特别是对于相比更长的分区)选择分区的第一个、中间、最后一个元素的中值作为基准元素

有了这些修改,那快排的最差的情况就不那么容易出现了,但是如果输入的数组最大(或者最小元素)被选为基准元素,那最坏的情况就又来了。

答案解析

*