前言
不出意外，这是一个“智障T”式的标题，屁大点事能给说成是天大的事情，但是我既然这么说，自然是有关系的。故事的起因是这样的，我几个月前在脉脉上读到一道题，内容大致是说给定一个数组，将其中所有正数移动到负数之前，并且保持正数和负数内部的顺序不变，要求空间消耗为常数。事情的结果不出意外，虽然我给出了基于数组旋转+并归的 $nlogn$ 解法，依然被淹没在了一堆 $n^2$ 的解法之中。
我虽然因为这件事有些郁闷，但是在这种事上较劲并不是我的风格。比较让我在意的是，尽管我直接写出了线性复杂度的数组旋转算法（也就是所谓的 Juggling Algorithm），但是对其中原理尚有些一知半解。这一疑惑直到我有一天读到维基百科上对费马小定理的一条证明时才恍然大悟。我们今天就来稍微聊一聊其中原理。至于数组旋转的算法，我向你强烈推荐 Reversal Algorithm，他相比起 Juggling Algorithm，尽管复杂度一致，但是更简洁易懂，而且对缓存使用也更加有效，但这不是我们今天的话题。
实现
数组旋转的概念非常简单，就是将数组内的内容在顺序不变的情况下移动。举个例子，将 [1, 2, 3, 4, 5] 向前移动两位，我们就可以获得 [3, 4, 5, 1, 2]。对于这个问题，Jugging Algorithm 给出了一个略有些炫技的思路：我们从任何一位开始，将其进行移动，再对其目标位置上的元素重复同样的操作，直至发生重复。对于前面的例子，我们可以将 1 移动到第 4 位，将 4 移动到第 2 位，将 2 移动到第 5 位，将 5 移动到第 3 位，最后将 3 移动到第 1 位，如图所示。
如果数组长度和移动位数并不互质，那么情况就会复杂一些。举个例子，将 [1, 2, 3, 4] 向前移动两位。我们将 1 移动到第 3 位，3 移动到第 1 位，此时即发生重复。然后我们再重复这一过程，将 2 移动到第 4 位，将 4 移动到第二位，即完成旋转，如图所示。
如你所见，当数组长度和移动距离都很长时，我们的数据将会在一个巨大的内存范围内均匀跳动，这对于缓存利用是不利的，所以在实际环境中我并不会推荐这个算法。但是从另一个方面讲，这个算法又很有趣：我们为什么能保证数组长度和移动距离互质时数据会在反复跳动后回到原点并无一遗漏，又为什么能在不互质时使用偏移覆盖整个数组，并且不发生重叠。这些性质都可以用模数学证明。
假设移动距离为 a，数组长度为 p，$gcd(a, p) = 1$。对于 k 次移动，所经过的长度为 ka (k 为整数)，最终到达的索引位置为 $ka \mod p$。对于任意不同的 $k_1 < k_2 \in [1, p]$，令 $k_0 = k_2 - k_1$。因为 $k_0 < p$ 且 $gcd(a, p) = 1$，可得 $gcd(k_0a, p) = 1$，这也就意味着 $k_1a \mod p$ 和 $k_2a \mod p$ 的值必然不同。如前文所述，$ka \mod p$ 即代表每次跳动之后的索引位置，这也就证明了在 p 次跳转以内，到达的索引位置不可能重复。
当 a 和 p 不互质时，证明同样简单：我们先令 $a’ = a / gcd(a, p)$，$p’ = p / gcd(a, p)$，得到 $gcd(a’, b’) = 1$，即可重复上一段的证明内容。因此，我们可以得到结论，对于不互质的 a 和 p，我们可以得到一个容量为 $p / gcd(a, b)$，间隔为 $gcd(a, b)$ 的循环。如果我们对起始位置加上任意的相位 $0 \leq \varphi < gcd(a, b)$，即可获得一组覆盖整个范围，并且互不重叠的循环。
通过模数学，我们实际上将数轴转化成了一个数环，对于任何 k，$kp + b$，均指代着数环上的同一个点。因此，数组层面上的位移就成为了数环层面上的旋转。基于这一解释，把这一问题称作“数组旋转”就显得十分直观了。这里给出 Java 的实现，有需要的可以作为参考：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void swap(int[] ints, int offset) {
offset %= ints.length;
int count = 0;
int begin = 0;
while (count != ints.length) {
int nxt;
int idx = begin;
int tmp = ints[idx];
while (true) {
nxt = (idx + offset);
count++;
if (nxt >= ints.length) nxt -= ints.length;
if (nxt == begin) break;
ints[idx] = ints[nxt];
idx = nxt;
}
ints[idx] = tmp;
begin++;
}
}
说到这里，我们今天的内容就结束了。我本身算法功底就相当有限，所以也别对这破站上的算法内容有太多期待，这篇文章或多或少也是作为学习笔记存在的。对了，说起文章开头的那个算法题，这里 给出了一个粗糙但是可用的实现，有兴趣的也可以研究一下。祝好。
若非特殊注明，文章均为博主原创，通过 CC 4.0 BY License 授权转载
