如何实现数组的高效移位算法
问题：编写一个能够支持数组快速移位的算法，时间复杂度在O(N)以内。
答：要实现在线性的时间内实现数组的快速移动，就要考虑如何使用逆序算法来达到移动的目的。例如，我要移动的数组元素称为A，剩余的部分称为B，那么原来次序为AB，如何变成BA呢？其实根据倒置的算法是可以实现移位操作的，我们先取A'为A的逆序序列，B'为B的逆序序列,进行(A'B')'操作即可得到BA序列。实现算法如下：
//// main.cpp// MyProjectForCPP//// Created by labuser on 11/2/11.// Copyright 2011 __MyCompanyName__. All rights reserved.//#include <iostream>using namespace std;void ReverseArray(int dataArray[],int start,int end){ int low=start,high=end; if(start>end){ cout<<"Index Error!"<<endl; cout<<"start:"<<start<<" end:"<<end; } while(low<high){ int tempDate = dataArray[low]; dataArray[low] = dataArray[high]; dataArray[high] = tempDate; ++low; --high; } }void QuickShift(int dataArray[],int shift,int n){ int len =n; ReverseArray(dataArray, 0, shift-1); ReverseArray(dataArray, shift, len-1); ReverseArray(dataArray, 0, len-1);}int main (int argc, const char * argv[]){ int dataArray[10]={1,2,3,4,5,6,7,8,9,10}; int n = sizeof(dataArray)/sizeof(int); QuickShift(dataArray, 4,n); for(int i=0;i<n;++i){ cout<<dataArray[i]<<" "; } cout<<endl; return 0;}