arrays - 考虑一个快速排序版本，其中枢轴始终被选为相关子数组的第一个元素

Question

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

Answer 1

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