数组循环移位

比如1 2 3 4 5
             循环移位1位 5 1 2 3 4
             循环移位2位 4 5 1 2 3
             循环移位3位 3 4 5 1 2
             循环移位4位 2 3 4 5 1
             循环移位5位 1 2 3 4 5  
可以看出，当移动n位时还原了，数据没有变化。 所以当移动k位>n时，只需移动k%n即可 

最简单的方法就是1位1位的移动，如果移动k位，移动k次，但是这样的效率很低，每个数都要移动k次，一共要移动k*n次。

在编程之美上有一种做法，是将前n-k位逆序，在将后k位逆序，4然后将全部n位逆序，这种方法简单，但是每个数要移动两次，一共要移动2n次。

我的方法是每个数只移动一次，但是需要k个存储空间，也就是时间换空间的做法。

就是将前k个数{0，(k)%n,(2k)%n,....}{1,(k+1)%n,(2k+1)%n...}....{ (k-1)%n,(k+k-1)%n...}
有k个子序列，每个子序列分别移动移位，对于第一个子序列也就是说第0位移动到第k位，第k位移动到2k位...对于第二子序列 第1位移动到第k+1位，第k+1位移动到第2k+1位....
按照相同的方法处理。只需要重复k次子序列的移位就可以了

注意：
     因为是模运算，子序列可能相交，所以需要记录子序列的移位情况，当该子序列已经移位过了，就要从未移位的子序列中找到一个子序列重新开始。

     注意每个子序列的循环移动

package www.viking.com.algorithm;

public class RightShift {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		char a[] = { 'a', 'b', 'c', 'd', '1', '2', '3', '4' };
		rightshift(a, 4);
		for (char i : a) {
			System.out.print(i + " ");
		}
	}

	/**
	 * 
	 * @param a
	 * @param steps
	 */
	public static void rightshift(char a[], int steps) {
		// 如果移动a.length位，结果是一样的
		steps = steps % a.length;
		if (steps <= 0) {
			return;
		}
		// 子序列下标
		int subSequenceNum = 0;
		// 起始子序列的下标
		int startSequenceNum = 0;
		// 记录前一个子序列
		int preSubSequence = subSequenceNum;
		// 标示 k个子序列的移位情况
		int[] subSequenceShift = new int[steps];
		// 从第subSequenceNum元素开始循环右移
		// 记录子序列的第一个元素
		char moveValue = a[subSequenceNum];
		// 子序列的个数
		for (int f = 0; f < steps; f++) {
			// 当前subSequenceNum被移动了
			subSequenceShift[subSequenceNum] = 1;
			// 记录当前位置的值
			int j = subSequenceNum;
			// 右移
			for (; j < a.length; j += steps) {
				char curValue = a[j];
				a[j] = moveValue;
				moveValue = curValue;
			}
			// 新的子序列
			subSequenceNum = j - a.length;
			// 判断当前子序列是否被移位过
			if (subSequenceShift[subSequenceNum] == 1) {
				for (; startSequenceNum < subSequenceShift.length; startSequenceNum++) {
					if (subSequenceShift[startSequenceNum] == 0) {
						// 子序列循环移位完成，关闭子序列
						a[preSubSequence] = moveValue;
						// 重新设置新的子序列
						subSequenceNum = startSequenceNum;
						// 保存当前的子序列
						preSubSequence = subSequenceNum;
						break;
					}
				}
			}
		}
		// 子序列循环移位完成，关闭子序列
		a[subSequenceNum] = moveValue;
	}
}