快速排序：旋转场景
Quicksort: pivoting scenarios
据我所知，如果您对接近排序的列表进行排序，则与前面的元素枢轴相比，中间元素枢轴会更好。在哪种情况下选择第一个元素作为枢轴比选择中间元素作为枢轴更有效？
我知道选择三个中位数通常是最好的方法，但是有没有例外，选择一个固定的枢轴（例如第一个或中间元素）会更有效？
如有任何帮助，我们将不胜感激。
From what I can gather the middle element pivot would be better in comparison to the front element pivot if you are sorting a near sorted list.
当为每个分区选择的基准恰好是整个分区的中值时，快速排序性能最佳。所以是的，如果输入已经接近排序，那么选择每个分区的位置中间元素作为基准将产生对最佳性能的良好近似。当然，在那种情况下，插入排序可能会做得更好。
In which scenario would picking the first element as the pivot be more efficient than picking the middle element as the pivot?
如果您假设输入是均匀随机的，那么没有任何仅基于索引的枢轴选择方法比任何其他方法更好或更差。但是对于任何具有已知的确定性分区方案的快速排序实现，都可以构建引发该方案最坏可能行为的输入。对于大多数此类分区方案，麦芽汁案例行为在元素数量上是二次方的。我不能随口描述一个会对中间元素枢轴快速排序产生这种影响的输入，* 但我向你保证有一些。任何其他枢轴选择方法都会对大多数此类输入进行改进。
I know picking Median of three is usually the best method
三中位数在很多情况下都是好的方法。至于最好，这在某种程度上取决于你追求什么。
but is there any exceptions to this that picking a fixed pivot such as the first or middle element would be more efficient?
我上面说的三中位数也不例外。可以构建所谓的“三个杀手的中值”序列，从 M3 快速排序中引出最坏情况的行为，并且最坏情况的行为是二次的。对于此类输入，几乎任何其他枢轴选择方法都更好。
另一方面，随机枢轴选择相对普遍。从概率上讲，它避免了二次行为，随着输入大小的增加二次收缩的可能性。并且或多或少不可能有意构建一个随机枢轴杀手序列（这样做需要枢轴选择依赖于确定性（伪）RNG 实现，其细节和初始状态为攻击者所知）。
另一方面，中位数的中位数实现起来更复杂，而且平均速度稍慢，但它的特点是将 O(n log n) 最坏情况的行为传递给其他精心实现的快速排序。
还有其他选择。
* 大多数元素相同的输入可以驱动许多快速排序实现二次，但这不是枢轴选择方案的特征，它可以独立于枢轴来解决选择方案.
据我所知，如果您对接近排序的列表进行排序，则与前面的元素枢轴相比，中间元素枢轴会更好。在哪种情况下选择第一个元素作为枢轴比选择中间元素作为枢轴更有效？
我知道选择三个中位数通常是最好的方法，但是有没有例外，选择一个固定的枢轴（例如第一个或中间元素）会更有效？
如有任何帮助，我们将不胜感激。
From what I can gather the middle element pivot would be better in comparison to the front element pivot if you are sorting a near sorted list.
当为每个分区选择的基准恰好是整个分区的中值时，快速排序性能最佳。所以是的，如果输入已经接近排序，那么选择每个分区的位置中间元素作为基准将产生对最佳性能的良好近似。当然，在那种情况下，插入排序可能会做得更好。
In which scenario would picking the first element as the pivot be more efficient than picking the middle element as the pivot?
如果您假设输入是均匀随机的，那么没有任何仅基于索引的枢轴选择方法比任何其他方法更好或更差。但是对于任何具有已知的确定性分区方案的快速排序实现，都可以构建引发该方案最坏可能行为的输入。对于大多数此类分区方案，麦芽汁案例行为在元素数量上是二次方的。我不能随口描述一个会对中间元素枢轴快速排序产生这种影响的输入，* 但我向你保证有一些。任何其他枢轴选择方法都会对大多数此类输入进行改进。
I know picking Median of three is usually the best method
三中位数在很多情况下都是好的方法。至于最好，这在某种程度上取决于你追求什么。
but is there any exceptions to this that picking a fixed pivot such as the first or middle element would be more efficient?
我上面说的三中位数也不例外。可以构建所谓的“三个杀手的中值”序列，从 M3 快速排序中引出最坏情况的行为，并且最坏情况的行为是二次的。对于此类输入，几乎任何其他枢轴选择方法都更好。
另一方面，随机枢轴选择相对普遍。从概率上讲，它避免了二次行为，随着输入大小的增加二次收缩的可能性。并且或多或少不可能有意构建一个随机枢轴杀手序列（这样做需要枢轴选择依赖于确定性（伪）RNG 实现，其细节和初始状态为攻击者所知）。
另一方面，中位数的中位数实现起来更复杂，而且平均速度稍慢，但它的特点是将 O(n log n) 最坏情况的行为传递给其他精心实现的快速排序。
还有其他选择。
* 大多数元素相同的输入可以驱动许多快速排序实现二次，但这不是枢轴选择方案的特征，它可以独立于枢轴来解决选择方案.