快速排序的时间复杂度问题

Question

快速排序的复杂度不是应该跟初始化序列是否有序没有关系吗？关键看那个一分为2的标准的选取。即使初始有序，用随机选取的方式，怎么回成了O(n^2)呢，如果恰恰每次选的都是中间大小的，效果不是最好吗。即使是初始序列完全无须，老选到最大或者最小的，效果不是也是很差吗？怎么到处都在说初始有序的情况下快排的时间复杂度为O(n^2)，求大神解释

Answer 1

快排复杂度和序列是否有序是有关系的，除非每次选取基准元素时你都选取中间那个（比如使用std::nth_element）

 怎么到处都在说初始有序的情况下快排的时间复杂度为O(n^2)

常见的教材，一般选择数组的最后一个元素（也有选择第一个元素的）作为pivot，以此为基准将数组分为两部分，那么很显然，当数组有序的时候，
每次递归只是将一个含有n个元素的数组分成了一个只包含1个元素的数组和一个包含n-1个元素的数组，因此需要进行n次分组，而每次分组都要遍历数组(n次比较)以将其分成两部分，
因此这种情况下复杂度为O(n^2)。 因此对于快排，最好的情况也要nlog(n)，最坏则需要n^2，也即：很多时候快排并不快