1.概述

高效的排序算法在降低问题的复杂性方面起着重要的作用。在计算机科学中的各种问题中使用了排序算法，以按升序或降序重新排列输入数组或列表中的元素。

Quicksort是一种基于分而治之方法的高效排序。

在本教程中，我们将详细讨论Quicksort算法的最坏情况。

2.什么时候发生Quicksort最坏的情况？

Quicksort算法的效率在很大程度上取决于中心元素的选择。假设Quicksort的输入是一个排序数组，我们选择最左边的元素作为数据透视元素。在这种情况下，我们将有两个极端不平衡的阵列。一个数组将具有一个元素，而另一个数组将具有(N-1)个元素。

类似地，当给定的输入数组被反向排序并且我们选择最右边的元素作为中心元素时，最坏的情况就会发生。同样，在这种情况下，中心元素会将输入数组拆分为两个不平衡的数组。

除以上两种情况外，在给定输入数组中的所有元素都相同的情况下还有一种特殊情况。在这种情况下，中心元素无法将输入数组分为两部分，并且Quicksort的时间复杂度会大大增加。

3.最坏情况下的时间复杂度分析

假设我们选择一种中心元素，以使其尽可能提供最不平衡的分区：

框中的所有数字表示数组或子数组的大小。

让我们考虑一个输入个数为N数组。第一次分区调用需要花费N时间才能在输入数组上执行分区步骤。

每个分区步骤均从上一个步骤递归调用。鉴于此，我们可以将每个分区调用的复杂度进行汇总，以得出Quicksort算法的总复杂度。

因此，最坏情况下Quicksort算法的时间复杂度为

另外，我们可以创建一个递归关系进行计算。

在最坏的情况下，在第一个分区之后，一个数组将具有1个元素 ，另一个数组将具有(N-1)个元素。假设T(N)表示N

在最坏的情况下对元素进行排序的时间复杂度：

N=0和1的时候，我们不需要任何排序。因此，分选时间是0和T(0)=T(1)=0

现在，我们准备解决我们先前导出的递归关系：

因此，

4.避免最坏的情况

通过选择适当的中心元素，我们可以避免Quicksort中的最坏情况。在本文，我们将讨论选择中心元素的不同方法。

选择中心元素的第一种方法是从数组的中间拾取它。这样，我们可以将输入数组分为两个子数组，其中两个元素的数量几乎相等。

在某些情况下，选择随机中心元素是一个不错的选择。Quicksort的这种变体被称为随机Quicksort算法。

选择中心元素的另一种方法是取三个候选中心的中间值**。在这种情况下，我们将首先从输入数组中选择最左边，中间和最右边的元素。然后，将它们排列到左分区，数据透视图元素和右分区。

5.优缺点

就效率而言，Quicksort被认为是最好的排序算法之一。Quicksort的平均案例时间复杂度O(NlogN)

即使输入数组很大，它的性能也很好。它提供了高性能，并且比较容易编码。它不需要任何额外的内存。

快速排序的主要缺点是对中心元素的选择不当会降低算法的时间复杂度O(N²)。另外，它也不是稳定的排序算法。

参考

Quicksort Worst Case Time Complexity