1. 示例引出：
对 3，9，1，6，5，4，8，2，10，7 进行从小到大的快速排序
对于第一次遍历，如下图所示：
第一次遍历的过程
对应的二叉树结果是：
用二叉树表示第一次遍历的结果
那么经过后几次遍历比较可以得到如下二叉树：
用二叉树表示排序结果
这时我们可以计算一下我们的快速排序算法进行了多少次比较:
，即每个节点到根结点的距离之和。
2. 快排算法复杂性分析：
由上例可知，快排可视为一个二叉树构建的过程，那么这个二叉树构建的速度就决定了我们快排的效率。可以确定的是，对于同样的数据元素在不同的原始排列条件下，构建的二叉树越矮，则排序效率越高。
通过这一理论，我们可以更具体的分析其不同情况下的时间复杂度：
A. 对于最理想的状态，构建出的是一颗完全二叉树。
完全二叉树满足如下公式：
对于深度为h的完全二叉树，若为满二叉树，比较次数为：
这里的叶子数量m与深度h的关系：
深度一定时，完全二叉树叶子数的两种情况
那么叶子到根的距离d为：
即，，
由于为整数，即可认为
，
而对于完全二叉树来说，叶子数，与内点（带有叶子节点的顶点）数
的关系为
，则顶点数
那么由上述公式可得：
即，，时间复杂度为：
。
B. 对于最糟糕的状态，构建出的是一张线性表。
那么若节点数为n，则：
，即时间复杂度为：
。
结果为线性表时的情况
C. 对于平均情况而言，我们将
作为对
个对象进行快速分类时平均比较次数，在取得排序结果后，选取第
个元素为分割标准，平均比较次数为：%2BT_%7Bk-1%7D%2BT_%7Bn-k%7D)
。
由于分割标准的选取概率完全相同，那么可以得到平均比较次数为：
由于这里的，以及
由，以及
，得：
令，得：
令，得：
令，得：
整理得：
由，故
则：
即，
综合来看，快排的时间复杂度最理想状态与最糟糕状态分别为、
，但是对于一般随机情况而言时间复杂度仍为
。
