我正在实现一种算法，该算法使用最左边的pivot选择执行快速排序，直到一定的限制，当数组列表几乎排序时，我将使用插入排序对这些元素进行排序。
对于最左边的枢轴选择，我知道快速排序的平均情况复杂度为O(nlogn)，最坏情况复杂度为:当列表几乎排好序时，是O(n^2)另一方面，插入排序对于复杂度为O(n)的几乎排序的元素列表非常有效。所以我认为这个混合算法的复杂度应该是O(n)。我说的对吗?
对于qsort的性能来说，最重要的是选择一个好的枢轴。这意味着选择一个尽可能接近你要排序的元素的平均值的元素。
在qsort中O(n2)的最坏情况是每次分区通过时始终选择"坏"的枢轴。这将导致分区极度不平衡，而不是平衡。1: n-1元素划分比。
我不明白你所描述的添加插入排序将如何帮助或缓解这个问题。