题解

思路

相邻位置的编号本来就奇偶交替，所以一个数一旦从某个符合要求的位置开始连续向右移动，后面的交换也会自然满足操作奇偶性。

做法

我们从大到小固定 $N,N-1,\ldots,4$：先找到当前数的位置；若它和下一次操作要求的奇偶性不同，就在尚未固定的前缀中用位置 $1$ 或 $2$ 做至多三次调整，再把这个数一路交换到目标位置。这样已经固定的后缀不会再被碰到。

最后只剩前三个数时，合法交换位置只能按 $1,2,1,2,\ldots$ 出现，这个序列会依次经过三个元素的全部六种排列，因此至多再做五次就能排好。

复杂度

整个过程中每次交换都立即修改排列并记录位置，操作总数不超过 $N^2$；寻找位置和移动元素的总时间复杂度为 $O(N^2)$，额外空间为 $O(N)$（不计输出序列）。