分成三块了,再递归子块迭代,直到right>left. 这里放一个全过程慢镜头动图，帮助理解：
T(n) = θ(n) + T(i) + T(n-i-1) = cn+ T(i) + T(n-i-1)
其中，i是分区后第一个子块的大小，将T(0)=T(1)= 1作为初始条件。
如果这种情况在每个分区中都重复发生，那么每个递归调用处理一个比前一个列表小1的列表。因此需要在达到大小为1的列表之前进行n - 1次嵌套调用。这意味着调用树是n - 1个嵌套调用的线性链。第i次调用需要做O(n-i)复杂度来进行分区，则
如前所说，如每次执行分区时，都能将列表分成两个几乎相等的两个子块。这意味着每次递归调用都要处理一个只有一半大小的列表。因此，在到达大小为1的列表之前，我们只能进行嵌套调用。这意味着调用树的深度为，但是在调用树的同一级别上没有两个调用处理原始列表的相同部分;因此，每个级别的调用总共只需要O(n)个时间(每个调用都有一些固定的开销，但是由于每个级别上只有O(n)个调用，所以这被包含在O(n)因子中)。结果是，该算法只使用c(n log n)的时间。故时间复杂度为O(n log n)。
图片来自wikipedia:
注：快排不需要额外的缓冲区开销，但是需要栈开销，其空间复杂度为O(log n).
这里对上表其中几个效率相对较高的做个简要介绍，后面如有机会在深入学习总结：
算法应用
说到排序算法复杂度，请一定要与应用场景结合。主要需要考虑待排数据的集的尺寸，如果数据量小的时候放而是插入排序算法应用最为广泛；而对于海量数据场合，则应使用渐近有效排序策略。这是什么意思呢？说白了就是常使用混合算法！主要策略是利用快速排序、堆排序或归并排序将整体快速分治排序，同时对递归底部的小列表采用插入排序。 事实上，在实际应用中有更复杂的变体，例如在Android，Java和Python中使用的Timsort（合并排序，插入排序和其他逻辑），以及在某些C++中用的introsort（快速排序和堆排序） 在.NET中排序实现。
再说白一点，在海量数据场景，利用快速排序、堆排序或归并排序将海量数据快速迭代成收敛的小块，而在小块中采用最为常见的插入排序尽快完成小块排序，小块中采用插入排序则可以更大程度减少递归深度。
在信息时代，有海量信息需要处理，即便有非常强劲的处理器，但如没有很好的算法，仍然无法满足对这些信息的处理。在处理过程中，免不了要进行信息进行排序，快排在时空两个维度的开销都比较均衡，大量的应用软件、开发工具以及软件包都基于快排做了大量的应用。所以说快速排序改变世界，个人认为并不为过。同时对于求职面试，快速排序算法也是高频面试主题，值得深入研究掌握。