题目解析

本题一共给出了 22 种算法：

第一种是开一个临时数组，将后 n - pn−p 个数和前 pp 个数依次拷贝到临时数组中，再把临时数组复制给当前数组。这一朴素的算法时间和空间复杂度均为 \mathcal{O}(n)O(n)。

第二种是每次把整个数组往左移一位(最左边的移到最后)，这样左移 pp 次即是最终的数组。省去了 \mathcal{O}(n)O(n) 的临时空间，但是时间复杂度上升至 \mathcal{O}(n2)O(n2)。

事实上还存在第三种算法，在时间和空间上结合了前两个算法的优点，具体做法是：取 pp 和 n - pn−p 之间的较小值，设为 qq，对调前 qq 个和后 qq 个元素，然后递归处理剩下长度为 n -2qn−2q 的子序列。具体代码实现读者可以参看提高组试题和解答。