Question

结合二叉树的快速排序算法分析

Answer 1

对 3，9，1，6，5，4，8，2，10，7 进行从小到大的快速排序

对于第一次遍历，如下图所示：

对应的二叉树结果是：

那么经过后几次遍历比较可以得到如下二叉树：

这时我们可以计算一下我们的快速排序算法进行了多少次比较:

，即每个节点到根结点的距离之和。

由上例可知，快排可视为一个二叉树构建的过程，那么这个二叉树构建的速度就决定了我们快排的效率。可以确定的是，对于同样的数据元素在不同的原始排列条件下，构建的二叉树越矮，则排序效率越高。

通过这一理论，我们可以更具体的分析其不同情况下的时间复杂度：

完全二叉树满足如下公式：

对于深度为h的完全二叉树，若为满二叉树，比较次数为：

这里的叶子数量m与深度h的关系：

那么叶子到根的距离d为：

即， ，

由于 为整数，即可认为 ，

而对于完全二叉树来说，叶子数 ，与内点（带有叶子节点的顶点）数 的关系为 ，则顶点数

那么由上述公式可得：

即， ，时间复杂度为： 。

那么若节点数为n，则：

，即时间复杂度为： 。

由于分割标准的选取概率完全相同，那么可以得到平均比较次数为：

由于这里的 ，以及

由 ，以及 ，得：

令 ，得：

令 ，得：

令 ，得：

整理得：

由 ，故

则：

即，

综合来看，快排的时间复杂度最理想状态与最糟糕状态分别为 、 ，但是对于一般随机情况而言时间复杂度仍为 。