向量旋转操作之分段递归交换

开篇

这是对于之前一维向量左旋操作问题的最后一个解法，也是关于这个问题的最后一篇文章。在之前的文章中，我们分别用求逆法、取模置换法对该问题进行了解答，今天，使用的是分段递归的方式。

问题概要

将一个n元一维向量向左旋转i个位置。例如，当n = 8且i=3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。你能否仅使用数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转。

思路分析

思路分析图片

单纯看上面的讲解，有点抽象，我们来讲个例子说明，图片中的br,bl，我们下面以b1,b2来代替。
有字符串: abcdefgh, 我们要旋转的数量为3
此时，a为abc, b为defgh

abc / defgh

第1步，我们b分为b1,和b2,其中，b1:de, b2: fgh

abc / de / fgh

第2步，交换a和b2

fgh / de / abc

接下来，我们要交换的就是fgh和de这两个，abc我们先用括号包起来，避免干扰。当前字符串为

fgh / de (abc)

当前的a为fgh,b为de, 然后我们把a分为a1:fg, a2:h

fg / h / de (abc)

交换a1和b, 得到当前字符串

de / h / fg (abc)

现在左边部分还剩一个h没有交换过，我们还是把已经交换过的用括号包起来

(de) h / fg (abc)

此时a为h,b为fg,把b分为b1:f, b2: g, 此时字符串为

(de) h / f/g (abc)

交换a和b2，得到字符串

(de) g f h (abc)

这个时候，右边只剩一个f没有交换了，而左边是g，也就是说a:g,b:f,交换之

defghabc

至此，交换完毕

代码实现

#include <stdio.h>
#include <string.h>void swapArr(char arr[], int a, int b, int offset) {char temp;int i;for (i = 0; i < offset; i++) {temp = arr[a + i];arr[a + i] = arr[b + i];arr[b + i] = temp;}
}void rotateLeft(char *arr, int n, int rotdist) {if (rotdist == 0 || rotdist == n) return;int p = rotdist;int i = p;  //左边这一段字符串的长度 int j = n - p; // 右边这段字符串的长度 while (i != j) {if (i > j) {swapArr(arr, p - i, p, j);i -= j;} else {swapArr(arr, p - i, p + j - i, i);j -= i;}}swapArr(arr, p - i, p, i);
}int main() {char vector[256];int n, i;printf("请输入一个字符串: ");scanf("%s", vector);n = strlen(vector);printf("请输入旋转的位数: ");scanf("%d", &i);printf("原始字符串: %s\n", vector);rotateLeft(vector, n, i);printf("旋转后字符串: %s\n", vector);return 0;
}