如何实现数组的高效移位算法_C/C++_编程开发_程序员俱乐部

问题：编写一个能够支持数组快速移位的算法，时间复杂度在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;
}

运行的结果为：
GNU gdb 6.3.50-20050815 (Apple version gdb-1705) (Fri Jul  1 10:44:54 UTC 2011)
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "x86_64-apple-darwin".tty /dev/ttys002
[Switching to process 17195 thread 0x0]
5 6 7 8 9 10 1 2 3 4
Program ended with exit code: 0