不知道你的数学基础如何，我简单描述一下。
前提定义
待数组的元素个数为n
背景介绍
何为快速排序？是否写过快速排序的代码？至少这个你需要事先有所知道，要不然也仅仅是停留在记忆的层面，而不理解它为n*lgn的原因。
快速排序算法：
主要分为以下三个部分
1，partittion
2，quickSort前一部分
3，quickSort后一部分
简单说来就是，partition从要排序的数组中选取一个枢纽，例如即为pivot，然后将数组中比pivot小的元素放到它的左边，将比pivot大的元素放到它的右边（如果是递增排序的话）。因此根据时间复杂度的概念，这个partition的时间复杂度为n，这里的n就是你partition方法处理的数据长度。
为何partition的时间复杂度为n？
看你的问题，既然问到了n，我就解释一下partition为什么会是n的时间复杂度。paritition方法选取枢纽，这个一般拿数组元素的第一个即可，这个不需要任何的循环操作，直接取值即可，换句话说这个时间复杂度是1，然后需要遍历数组，将比pivot大的元素放到右边，比pivot小的元素放到左边，这个至少要遍历整个数组，然后对每一个元素进行操作决定是否移动，处理一个元素的时间复杂度为1，现在有n个元素要处理，故而parition方法的时间复杂度为n。
为何快速排序的时间复杂度为n*lgn?
根据背景介绍中的算法描述，可以写出如下的递推公式：
F(n) = 2 * F(n/2) + n
对上述函数进行解释如下：
F(n)代表对n个元素进行排序处理所花费的时间（当然只是一个抽象的时间概念）
根据算法描述的三步，第一步partition就是等式右边的n，第二步和第三步中的quickSort就是等式右边的2 * F(n/2)。为什么是n/2 ? 这个应该很容易理解，partition将数组分成两部分，下面的quickSort分别排序前一部分和后一部分，此处我们假设这个拆分是完全等分的，也就是说前一部分和后一部分都是n/2。
对上述等式进行时间复杂度的运算如下：
F(n) = 2 * F(n/2) + n = 2 * ( 2 * F(n/4) + n/2 ) + n
= 4 * F(n/4) + 2 * n
希望你能看出这个推导，就是直接的代入而已，下面我不再继续展开了，可以看出每展开一次它等式右边就多出了一个n， 由于每次展开操作是进行除以2的操作，故而最多进行lgn，也就是说最终的运算结果： F(n) = k* F(1) + lgn*n。
好了，啰啰嗦嗦.
追问谢谢，说的很明白
本回答被提问者和网友采纳