快速排序变体中的比较次数
Number of comparisons in quick sort variation
快速排序中最后一个元素作为枢轴元素和快速排序中第一个元素作为枢轴元素比较的次数会不会不同？
不，不会。在快速排序中，我们选择了一个枢轴元素（比如 x）。然后将列表分成大于x和小于x的2部分。
因此，比较次数的变化与递归深度成正比。也就是说，递归函数越深入，将列表分成两部分的比较次数就越多。
递归深度不同-x的值越大，可以将列表分成相似长度的部分，递归深度越小。
因此，结论是，选择第一个元素还是最后一个元素作为基准并不重要，重要的是那个值是否可以将列表分成2个相似长度的列表。
编辑
枢轴越接近中位数，复杂性越小 (O(nlogn))。枢轴越接近列表的最大值或最小值，复杂度就会增加（最多为 O(n^2)）
When a first element or last element is chosen as pivot the number of comparisons remain same but it is the worst case as the array is either sorted or reverse sorted.
在每一步中，数字按照以下递归划分。
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`
快速排序中最后一个元素作为枢轴元素和快速排序中第一个元素作为枢轴元素比较的次数会不会不同？
不，不会。在快速排序中，我们选择了一个枢轴元素（比如 x）。然后将列表分成大于x和小于x的2部分。
因此，比较次数的变化与递归深度成正比。也就是说，递归函数越深入，将列表分成两部分的比较次数就越多。
递归深度不同-x的值越大，可以将列表分成相似长度的部分，递归深度越小。
因此，结论是，选择第一个元素还是最后一个元素作为基准并不重要，重要的是那个值是否可以将列表分成2个相似长度的列表。
编辑 枢轴越接近中位数，复杂性越小 (O(nlogn))。枢轴越接近列表的最大值或最小值，复杂度就会增加（最多为 O(n^2)）
When a first element or last element is chosen as pivot the number of comparisons remain same but it is the worst case as the array is either sorted or reverse sorted. 在每一步中，数字按照以下递归划分。
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`