我正在学习算法课程，并且希望对以下问题有所帮助：
数组
[k+1, ..., n, 1, ..., k]上的k > n/2上的快速排序算法的时间复杂度是多少，并且始终选择枢轴作为子数组的最右边的单元格？是
O(n²)还是O(n log n)？
[根据过去一个学期的扫描算法测试，该学生说O(n²)（我在进行了几次模拟后同意），但是那个学生没有给出解释就得到了错误的答案。当我们三个人自己得出相同的结论时，我和其他几个学生感到困惑，为什么答案被标记为错误。
O（n²）是正确的。
[第一次运行将选择最右边的元素k作为枢轴，将数组的其余部分分成左侧的[1, ..., k-1]和右侧的[k+1, ..., n]。由于这两个子数组都按排序顺序排列，因此它们的形式是快速排序选择最右边的元素作为枢轴需要二次时间。
因此，对分区的左侧进行排序将花费O（k²）时间，对右侧进行排序将花费O（（n-k）²）时间。由于我们有n/2 < k <= n，所以我们也有O（k²）= O（n²）。