将最后一个元素作为快速排序的枢轴元素和将第一个元素作为快速排序的枢轴元素,比较的次数会不同吗??
不会。在快速排序中,我们选择一个主元素(比如x),然后将列表分成大于x和小于x的两部分。
因此,比较次数的变化与递归深度成正比。也就是说,递归函数越深入,将列表分成两部分所需要进行的比较次数就越多。
递归深度不同——x的值越能将列表分成相似长度的部分,递归深度越小。
因此,结论是,选择第一个元素还是最后一个元素作为枢轴并不重要,重要的是该值是否可以将列表划分为2个相似长度的列表。
编辑主节点越接近中位数,复杂度就越小(O(nlogn))。枢轴越接近列表的最大值或最小值,复杂度就越高(直到O(n^2))
当选择第一个元素或最后一个元素作为枢轴时,比较的次数保持不变,但这是最坏的情况,因为数组要么排序,要么反向排序。在每一步中,数字都按照以下递归式进行划分。
T(n) = T(n-1) + O(n) and if you solve this relation it will give you the complexity of theta(n^2)
当你选择中值元素作为枢轴时它会给出一个递归关系
T(n) = 2T(n/2) + theta(n) which is the best case as it gives complexity of `nlogn`