快速排序中的三数中值例程
设我们实现三数中值例程如下：
找出 a[left]、a[center] 和 a[right] 的中值, 并将它与 a[right] 交换. 以通常的分割方法进行, 开始时 i 在 left 处且 j 在 right-1 处(而不是 left+1 和 right-2).
(1) 设输入为 $2,3,4,\ldots,N-1,N,1$. 对于该输入, 这种快速排序算法的运行时间是多少?
(2) 设输入数据呈反序排列, 对于该输入, 这种快速排序算法的运行时间又是多少?
Remark: 这里的运行时间是指时间复杂度.