考虑一个快速排序的版本，其中枢轴总是被选择为相关子数组的第一个元素

Question

我的问题是：考虑一个版本的快速排序，其中始终选择主元作为相关子数组的第一个元素，并且该算法将其输入数组从最小到最大排序。是否没有输入数组导致算法进行的比较次数多于它对已排序数组进行的比较次数？

Answer 1

QuickSort 的最坏情况是在每次迭代时它会将大小为 n 的数组分成大小为 0 和 n-1 的两个数组。由于这正是您的情况（枢轴将始终是剩余数组中的最小元素），因此我相信没有输入数组会导致比已经排序的数组更多的比较是正确的。