算法课程笔记-快速排序时间复杂度分析
在本篇文章中，我们将重点分析快速排序算法的时间复杂度。
快排是一个非常常用的排序算法。它的核心思想是 “基于选定的枢轴对数据进行划分”。相比 归并排序，quicksort 主要的特点有:
- 不需要使用额外的空间；
- 算法的平均复杂度为 $O(nlogn)$;
- 在 大O(n) 表示法之外的常数值很小。
具体实现时，可以分为两个函数，quickSort() 函数和 partition() 函数，在 quickSort() 函数中，我们调用 partition() 函数让数组中的元素基于枢轴进行分块（小于枢轴元素的值放在数组前面，大于的放在数组后面）， 然后针对前半部分数组元素和 后半部分数组元素再分别调用 quickSort()， 实现代码可以参考 快排的Java代码实现。
在快排算法中，选择枢轴（pivot, 或者叫 中枢）是非常重要的，它决定了算法具体的时间复杂度。举两个例子，例子1，如果 长度为 n 的数组已经是按照从小到大的顺序排列的，我们每次从数组的最前面选取枢轴，则第 k 次 划分数组需要进行 n-k 个元素进行比较，从而总的时间复杂度为 $O(n^2)$。例子2，如果对于一个任意顺序的数组，每次我们都恰好取到了当前分块中位于中间的元素作为枢轴，则只需要进行 $log_2n$ 操作，就可以让数组有序，从而总的算法的时间复杂度为 $O(nlogn)$。
随机枢轴情况下的复杂度分析
为了提升算法的时间复杂度，对于快速排序算法，我们通常选取随机的枢轴元素进行 数组的划分。那么，在随机枢轴的情况下，算法的时间复杂度为多少呢？
这里我们可能首先想到使用主定理来分析该问题，但由于快排的分组是随机的，所以它的子问题一般并不具有相同的规模，因此不符合使用主定理的条件。
在课程中，老师在分析的时候定义了一个 随机变量，$Xij(\sigma)$, 表示 $z_i$ 和 $z_j$ 在 整个 快排 过程中需要比较的次数（$z_k$ 表示序列中第 k 小的元素）。通过分析，我们发现$Xij(\sigma)$ 的取值只可能是 0 或 1，也就是任何的两个数最多比较1次（解释：只有当 $z_i$ 或者 $z_j$ 其中一个被选为 枢轴，才会需要比较1次；并且，每次 枢轴 比较完毕之后，都会被移除出待比较的内容，所以最多只会比较1次）。
快排的总的时间 复杂度实际上就等于总的比较次数，我们定义总的比较次数的期望为 E[C], 有下面的公式：
$$E[C] = \Sigma_{i=1}^{n-1} \Sigma_{j=i+1}^{n} P_r[z_i, z_j \ get \ compared]$$
抽象一点看，这里实际上是 根据 期望的线性特性 将复杂的概率期望问题拆分成了许多的小问题，进行拆分后，我们可以根据 decomposition principle（分解原理），来求解具体的算法复杂度，步骤如下：
- 分析 我们所关注的 随机变量 Y；
- 将 Y 表示成一组 子的 随机变量 的组合；
- 根据期望的线性定理求解 总的期望。
回到原来的问题，通过 分解，原先的期望问题被分解为了许多的小的期望问题。我们需要分析 $P_r [z_i, z_j \ get \ compared]$ 的概率。我们知道，对于一组元素，他们进行比较的次数只能是 0 或者 1， 具体的，当选择 $z_i$ 或者 $z_j$ 作为 枢轴，则他们需要比较一次；而如果选择 (zi, zj) 即他们两个之间的某个元素作为 枢轴，则 $z_i$、$z_j$ 不需要进行比较，即比较 0 次。根据上述分析，我们可以得到 $P_r [z_i, z_j \ get \ compared]$ 的概率（或者说 $z_i$, $z_j$ 进行比较的次数的期望值）：
$$P_r [z_i, z_j \ get \ compared] = \frac{2}{j-i + 1}$$
所以总的比较次数的期望值为：
$$E[C] = \Sigma_{i=1}^{n-1} \Sigma_{j=i+1}^{n} \frac{2}{j-i + 1}$$
$$E[C] = 2 \times [(\frac{1}{2} + \frac{1}{3} … + \frac{1}{n}) + (\frac{1}{2} + \frac{1}{3} … + \frac{1}{n-1}) + (\frac{1}{2} + \frac{1}{3}… +\frac{1}{n-2}) + … ]$$
$$E[C] \leq 2\cdot n \Sigma_{k=2}^n \frac{1}{k} \leq 2\cdot n \cdot ln(n)$$
注释：f(x) = 1/x 的积分为 ln(x), 所以 $\Sigma_{k=2}^n \frac{1}{k} \leq \int_{2}^n \frac{1}{k} dk < ln(n)$.
因此，总的比较次数的期望值为 $nlogn$ 级别，也即 通过随机选择枢轴，快速排序的时间复杂度的均值为 $O(nlogn)$。