关于快速排序算法的问题

Question

我看的是Princeton 的Algorithms 4th，在快速排序这一章，partition部分的比较数到底是N-1还是N还是N+1啊？有人教教我怎么算吗？
或者有人帮忙证明一下快速排序的比较数为什么约等于2NlnN？

Answer 1

“Devil组”引证GPT后的撰写：

• 快速排序的比较次数取决于分割（partition）步骤中基准元素的选择方法和分割时元素的排列情况。在最坏情况下，分割过程将分割数组为两个不均衡的部分，并且每次分割只会将一个元素移动到其最终的位置，因此比较次数将达到N-1。在最好的情况下，每次分割都能将数组均分成两部分，比较次数为NlogN。平均情况下，我们可以预期比较次数约为2NlnN。

下面是快速排序平均比较次数约为2NlnN的证明概述：

• 对于快速排序的平均比较次数进行分析，我们需要考虑随机地选择基准元素的影响。我们可以考虑一个假想的排序过程，其中我们将基准元素选择为随机的，每个元素被选中的概率相等。在这种情况下，我们期望在进行分割操作时，选中的基准元素将数组分成两个大小大致相等的部分。

• 现在假设我们有一个大小为N的数组，我们要对其进行排序。为了方便，我们将N假定为2的幂，因此有N = 2^k。在第一轮分割之后，数组将被分成两个大小大致相等的子数组，每个大小为N/2。然后，我们需要对两个大小为N/2的子数组进行排序。

• 对于子数组的排序，我们仍然采用随机选择基准元素的方法。由于基准元素的选择是随机的，因此我们期望将每个子数组分成大小相等的两个子数组。在这种情况下，我们需要进行2次比较，以将基准元素与子数组的剩余元素进行比较。然后，我们需要对四个大小为N/4的子数组进行排序，每个子数组需要进行2次比较。以此类推，直到我们对大小为1的子数组进行排序。

因此，快速排序的比较次数可以表示为：

C(N) = 2NlogN + 2N + 2N + ... + 2 = 2NlnN + O(N)

• 其中，第一个项表示在主数组中进行的比较数，第二个项表示在子数组中进行的比较数，最后一项是一个小的修正项。因此，我们可以预期快速排序的比较次数约为2NlnN。这个证明仅仅是对快速排序的平均情况进行了分析，最坏情况下的比较次数可能达到N^2