sorting - 对 1/3 排序的数组进行正常与随机快速排序

Question

我正在尝试计算在具有这些属性
的数组上应用快速排序（随机或正常）的时间复杂度：数组在前 2/3 中未排序，最大元素是 t
下一个 1/3 已排序，所有这里的元素大于 t\

我知道在正常的快速排序中，选择这两个部分之间的障碍导致不必对下一个 1/3 进行排序，但我找不到一种正式的（数学）方法来计算时间复杂度的渐近界限。
提前致谢

Answer 1

随机快速排序相当于先对数组进行洗牌，然后再应用朴素快速排序。洗牌需要线性时间，因此无论部分排序的输入如何，您都可以获得快速排序的平均时间复杂度，即 O(n log n)。

朴素的快速排序将在这些输入上具有二次时间复杂度，因为最终元素 t 将被选为枢轴，并且 t 出现在排序区域之前，因此该区域将被选为整个分区。天真的快速排序将在此分区上花费 (n/3) 的二次时间，这是 n 的二次时间。