对n个关键字的序列进行快速排序，平均情况下的时间复杂度为()

对n个关键字的序列进行快速排序，平均情况下的时间复杂度为()
A、O(nlog₂n)
B、O(log₂n)
C、O(n)
D、O(1)
【正确答案】：A
【题目解析】：快速排序的3个步骤：找到序列中用于划分序列的元素；用元素划分序列；对划分后的两个序列重复1，2两个步骤指导序列无法再划分。所以对于n个元素其排序时间为：T(n)=2*T(n／2)+n(表示将长度为n的序列划分为两个子序列，每个子序列需要T(n／2)的时间，而划分序列需要n的时间)；而T(1)=1(表示长度为1的序列无法划分子序列，只需要1的时间即可)；T(n)=2^log₂n+log₂n*n，n被不断二分最终只能二分logn次(最优的情况，每次选取的元素都均分序列))=n+nlog₂n。因此T(n)=O(nlog₂n)。