C ++中用于数组旋转的块交换算法
数组旋转的块交换算法是用于数组旋转的高效算法。它可以以O(n)的时间复杂度完成您的工作。
因此，在数组旋转中，我们得到了大小为n的数组arr[]和定义为no的数字k。旋转元素的数量。
让我们看一个数组旋转的例子-
输入 -
arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (number of rotations.)输出-
{1, 8, 9, 2, 4, 6}解释-旋转时，我们将一个元素移到最后一个位置，然后将下一个元素移到一个位置。
索引为0的元素将移至索引n-1。其余元素将移至上一个索引。
块交换算法
块交换算法用于完美执行数组旋转。
算法
步骤1-将数组除以k为分割点的两个子数组。令它们为X=arr[0...k-1]和Y=arr[k...n-1]。
步骤2-遵循以下步骤，直到X和Y的大小相同。
步骤2.1-如果X>Y的大小，将X分为X1和X2两部分，以使X1的大小等于Y的大小。然后交换子数组X1和Y。这将改变原始数组的形式X1X2Y至YX2X1。
步骤2.2-如果Y>X的大小，则将Y分为两个部分Y1和Y2，以使Y2的大小等于X的大小。然后交换子数组X和Y2。这会将原来的数组形式从XY1Y2更改为Y2Y1X。
步骤3-当X和Y的大小相同时，交换它们。
该算法需要重复调用相同的代码块。可以使用两种方法来实现此重复呼叫。它们是递归方法和迭代方法。我们将使用程序讨论该方法。
示例
程序来说明递归方法-
#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, intk){
int temp;
for(int i = 0; i < k; i++){
temp = arr[start + i];
arr[start + i] = arr[end + i];
arr[end + i] = temp;
}
}
void blockSwapAlgo(int arr[], int k, int n) {
if(k == 0 || k == n)
return;
if(k<(n-k)) {
swapSubArray(arr, 0, (n-k), k);
blockSwapAlgo(arr, k, (n-k));
}
else if(k>(n-k)){
swapSubArray(arr, 0, k, (n-k));
blockSwapAlgo((arr+n-k), (2*k-n), k);
}
else{
swapSubArray(arr, 0, (n-k), k);
return;
}
}
int main() {
int arr[] = {4, 6, 1, 8, 9, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"Array before rotations :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
blockSwapAlgo(arr, k, size);
cout<<"\nArray after rotating "<<k<<" times :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
return 0;
}输出结果
Array before rotations : 4 6 1 8 9 2 Array after rotating 3 times : 8 9 2 4 6 1
示例
程序来说明迭代方法-
#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, int k){
int temp;
for(int i = 0; i < k; i++){
temp = arr[start + i];
arr[start + i] = arr[end + i];
arr[end + i] = temp;
}
}
void blockSwapAlgoIt(int arr[], int k, int size) {
int i, j;
if(k == 0 || k == size)
return;
i = k;
j = size - k;
while (i != j) {
if(i < j){
swapSubArray(arr, k-i, k+j-i, i);
j -= i;
}
else{
swapSubArray(arr, k-i, k, j);
i -= j;
}
}
swapSubArray(arr, k-i, k, i);
}
int main() {
int arr[] = {4, 6, 1, 8, 9, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"Array before rotations :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
blockSwapAlgoIt(arr, k, size);
cout<<"\nArray after rotating "<<k<<" times :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
return 0;
}输出结果
Array before rotations : 4 6 1 8 9 2 Array after rotating 3 times : 8 9 2 4 6 1