arrays - 特定类型数组的快速排序算法时间复杂度

Question

我正在学习算法课程，希望对以下问题有所帮助：

[k+1, ..., n, 1, ..., k]数组where的快速排序算法的时间复杂度是多少k > n/2，并且枢轴总是被选为子数组的最右边的单元格？

会是O(n²)还是O(n log n)？

从过去一个学期的扫描算法测试中，学生说O(n²)（经过几次模拟后我同意了），但是那个学生没有解释就得到了错误的答案。当我们三个人自己得出相同的结论时，我和其他几个学生对为什么答案被标记为错误感到困惑。

标签： arraysalgorithmsortingtime-complexityquicksort

Answer 1

O(n²) 是正确的。

第一次运行将选择最右边的元素k作为枢轴，将数组的其余部分划分为[1, ..., k-1]左侧和[k+1, ..., n]右侧。由于这两个子数组都是按排序顺序排列的，因此它们的形式是快速排序选择最右边的元素作为枢轴需要二次时间。

因此，对分区的左侧进行排序将花费 O(k²) 时间，而对右侧进行排序将花费 O((nk)²) 时间。因为我们有n/2 < k <= n，所以我们也有 O(k²) = O(n²)。