在分区时两个子分区最平衡时。 因为两个子分区大小不可能同时大于n/2，所以一个分区大小为n/2的下界，另一个分区大小为n/2的上界加1时，快速排序的运行速度最快。 这时，表达其运行时间的递归式为 T(n) <= 2T(n/2) + O(n) 根据定理 T(n) = if n = 1 , then O(n) if n > 1, then 2T(n/2) + O(n) 的解为T(n) = O(nlgn) 由于在每一层递归上，划分的两边都是对称的。所以，从渐进意义上来看，算法运行得最快。本回答被提问者采纳