快速排序算法的核心思想：找到基准值的位置
第一步，选择一个值作为基准值
第二步，就是将小于基准值的元素放在基准值的前面，将大于基准值的元素放在基准值的后面
第三步，是对基准值的左右两侧，递归地进行第一步和第二步
分析快速排序的时间复杂度
首先，我们要确定总体时间复杂度的公式。我们用 T(n)表示对 n个元素的数组进行快速排序所用的时间，那么 T(n) 中应该包括了单次的 partition 操作用时，以及 parition 操作以后，我们对左右两个子数组分别做快速排序所用的时间，也就是 T(n) = n + T(L) + T(R)。其中 n是单次 partition 操作的用时，T(L)和 T(R)分别是对左右区间进行快速排序的用时，L 和 R分别代表左区间和右区间中元素的数量。
接着，我们借助二叉树的结构来求一下 T(n) 。首先，我们可以将基准值看成是由 n 个元素组成的二叉树的根节点，那么 partition 操作就是找到这个根节点的正确位置，总用时就是 n。如果我们将这个用时 n 当做二叉树根节点的独立用时，那么左子树根节点的独立用时就是 L，右子树根节点的独立用时就是 R。这样，我们就得到了这个二叉树第二层上所有节点的独立用时：L + R = n - 1。我们可以将这个值大致看成是 n。依照此方法，你会得到接下来各层二叉树节点的独立用时，关系如图所示：
此文章为3月Day2学习笔记，内容来源于极客时间《常用算法25讲》，强烈推荐该课程！
