C语言将数组中的元素循环移动（以左移为例）

这里涉及到数据结构中顺序表的实现、删除、插入、查找等知识，请查看：数据结构 -> 线性表

问题描述：

设将n (n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p (0<p<n)个位置，即将R中的数据由 (X₀, X₁,…, X_n-1)变换为(X_p, X_p+1,…, X_n-1, X₀, X₁, …, X_p-1)。要求：

1) 给出算法的基本设计思想。

2) 根据设计思想，用C或C++或Java语言描述算法，关键之处给出注释。

3) 说明你所设计算法的时间复杂度和空间复杂度。

该题为2010年研究生考试计算机联考真题

问题解答：

(1)算法的基本设计思想：

可以将这个问题看做是把数组ab转换成数组ba (a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到a^-1b，再将b逆置得到a^-1b^-1，最后将整个a^-1b^-1逆置得到(a^-1b^-1)^-1=ba。设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3 (p=3)个位置的过程如下：

• Reverse(0, p-1)得到 cbadefgh;
• Reverse(p, n-1)得到 cbahgfed;
• Reverse(0, n-1)得到 defghabc;

注：Reverse中，两个参数分别表示数组中待转换元素的始末位置。

(2)使用C语言描述算法如下：

void Reverse(int R[], int from, int to) {
   int i, temp;
    for(i=0; i<(to-from+1)/2; i++){
        temp=R[from+i];
        R[from+i]=R[to-i];
        R[to-i]=temp;
    }
}  //Reverse
void Converse(int R[],int n,int p){
    Reverse(R,0,p-1);
    Reverse(R,p,n-1);
    Reverse(R,0,n-1);
}

(3)上述算法中三个Reverse函数的时间复杂度分别为O(p/2)、O((n-p)/2)和O(n/2)，故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。

另解，借助辅助数组来实现：

算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R 中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。

时间复杂度为O(h)，空间复杂度为O(p)。