C++程序用于数组旋转的反转算法

编写一个函数rotate(arr[],d,n)，该函数将大小为n的arr[]数组旋转d个元素。
示例：

输入 : arr[] = [1, 2, 3, 4, 5, 6, 7]
d = 2
输出 : arr[] = [3, 4, 5, 6, 7, 1, 2]

C++程序用于数组旋转的反转算法

将上述数组旋转2个元素

C++程序用于数组旋转的反转算法

方法4（反转算法）：

算法：

rotate(arr[],d,n)
  反转(arr[],1,d) ;
  反转(arr[],d+1,n);
  反转(arr[],1,n);

让AB是输入数组的两个部分，其中A=arr[0..d-1]，B=arr[d..n-1]。该算法的思想是：

将A反转以获得ArB，其中Ar是A的反转。
将B反转以获得ArBr，其中Br是B的反转。
反转所有到（ArBr）r=BA。

示例：

让数组arr[]=[1,2,3,4,5,6,7]，d=2，n=7

A=[1,2]，B=[3,4,5,6,7]

反转A，我们得到ArB=[2,1,3,4,5,6,7]
反转B，我们得到ArBr=[2,1,7,6,5,4,3]
反转所有，我们得到（ArBr）r=[3,4,5,6,7,1,2]

下面是实现上述方法的代码：

// C++程序用于数组旋转的反转算法
#include <bits/stdc++.h>
using namespace std;
 
/*将数组arr[]从索引start到end反转*/
void 反转数组(int arr[],int start,int end)
{
    while(start<end){
        int temp=arr[start];
        arr[start]=arr[end];
        arr[end]=temp;
        start++;
        end--;
    }
}
 
/*将大小为n的数组arr[]向左旋转d个元素*/
void 向左旋转(int arr[],int d,int n)
{
    if(d==0)
        return;
    //如果旋转因子大于数组长度
    d=d%n;
 
    反转数组(arr,0,d-1);
    反转数组(arr,d,n-1);
    反转数组(arr,0,n-1);
}
 
//打印一个数组
void 打印数组(int arr[],int size)
{
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
}
 
/* 测试上述函数的驱动程序 */
int main()
{
    int arr[]={1,2,3,4,5,6,7};
    int n=sizeof(arr)/sizeof(arr[0]);
    int d=2;
 
    //函数调用
    向左旋转(arr,d,n);
    打印数组(arr,n);
 
    return 0;
}