快速排序中以最后一个元素为基准元素和以第一个元素为基准元素进行快速排序时,比较的次数会不会不同?
最佳答案
不,不会。在快速排序中,我们选择了一个枢轴元素(比如 x)。然后将列表分成大于 x 和小于 x 的 2 部分。
因此,比较次数的变化与递归深度成正比。也就是说,递归函数越深入,将列表分成两部分的比较次数就越多。
递归深度 不同 - x 的值越大,可以将列表划分为相似长度的部分,递归深度越小。
因此,结论是,选择第一个还是最后一个元素作为基准并不重要,重要的是那个值能否将列表分成2个长度相似的列表。
编辑 枢轴越接近中位数,复杂性越小 (O(nlogn))。枢轴越接近列表的最大值或最小值,复杂度就会增加(最多为 O(n^2))
关于algorithm - 快速排序变体中的比较次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38041151/