举个例子来说明一下，例如对于m=3,n=4的情况，
1、我们得到的序列：即通过上述式子求出来的k序列，是0, 3, 2, 1。
2、然后，你只要只需按这个顺序赋值一遍就达到左旋3的目的了：
ch[0]->temp, ch[3]->ch[0], ch[2]->ch[3], ch[1]->ch[2], temp->ch[1]; （*）
ok，这是不是就是按上面（*）式子的顺序所依次赋值的序列阿?哈哈，很巧妙吧。当然，以上只是特例，作为一个循环链，相当于rotate算法的一次内循环。
2、对于正整数m、n不是互为质数的情况（因为不可能所有的m，n都是互质整数对），那么我们把它分成一个个互不影响的循环链，正如flyinghearts所言，所有序号为 (j + i * m) % n（j为0到gcd(n, m)-1之间的某一整数，i = 0:n-1）会构成一个循环链，一共有gcd(n, m)个循环链，对每个循环链分别进行一次内循环就行了。
综合上述两种情况，可简单编写代码如下：
后来有网友针对上述的思路④，给出了下述的证明：
1、首先，直观的看肯定是有循环链，关键是有几条以及每条有多长，根据(i+j *m) % n这个表达式可以推出一些东东，一个j对应一条循环链，现在要证明(i+j *m) % n有n/gcd(n,m)个不同的数。
2、假设j和k对应的数字是相同的， 即(i+j*m)%n = (i+k*m)%n， 可以推出n|(j-k)*m，m=m’*gcd(n.m), n=n’*gcd(n,m), 可以推出n’|(j-k)*m’，而m’和n’互素，于是n’|(j-k)，即(n/gcd(n,m))|(j-k)，
3、所以(i+j*m) % n有n/gcd(n,m)个不同的数。则总共有gcd(n，m)个循环链。符号“|”是整除的意思。
以上的3点关于为什么一共有gcd(n, m)个循环链的证明，应该是来自qq3128739xx的，非常感谢这位朋友。
3.2、以下，便是摘自sgi stl v3.3版中的stl_algo_h文件里，有关rotate的实现的代码：
由于上述stl rotate源码中，方案④ 的代码，较复杂，难以阅读，下面是对上述第④ 方案的简单改写：
对上述程序的解释：关于第二个for循环中，j初始化为（i+）%n，程序注释中已经说了，i+k为i右移k的位置，%n是当i+k>n时从左重新开始。为什么要这么做呢?很简单，n个数的数组不管循环左移多少位，用上述程序的方法一共需要交换n次。当i+k>=n时i+k表示的位置在数组中不存在了，所以又从左边开始的(i+k)%n是下一个交换的位置。
好比5个学生,，编号从0开始，即0 1 2 3 4，老师说报数，规则是从第一个学生开始，中间隔一个学生报数。报数的学生编号肯定是0 2 4 1 3。这里就相当于i为0，k为2，n为5
然后老师又说，编号为0的学生出列，其他学生到在他前一个报数的学生位置上去，那么学生从0 1 2 3 4=》2 3 4 _ 1，最后老师说，编号0到剩余空位去，得到最终排位2 3 4 0 1。此时的结果，实际上就是相当于上述程序中左移k=2个位置了。而至于为什么让 编号为0 的学生 出列。实际是这句：int last = i; 因为要达到这样的效果0 1 2 3 4 => 2 3 4 0 1，那么2 3 4 必须要移到前面去。怎么样，明白了么?。
关于本题，不少网友也给出了他们的意见，具体请参见此帖子微软100题，维护地址。
第五节、总结
如nossiac所说，对于这个数组循环移位的问题，真正最靠谱的其实只有俩种：一种是上文的思路一，前后部分逆置翻转法，第二种是思路三，即stl 里的rotate算法，其它的思路或方法，都是或多或少在向这俩种方法靠拢。
下期更新：程序员面试题狂想曲：第二章。时间：本周周日04.24晚。非常感谢各位朋友的，支持与关注。本人宣告：本程序员面试题狂想曲系列，永久更新。
本章完。
版权声明：转载本BLOG内任何文章和内容，务必以超链接形式注明出处。