数组元素循环移动
数组元素循环移动分为循环左移和循环右移。
由于两种情况类似。就以循环右移为例。
1. 目的
将数组中的元素循环向右移动。
2. 效果
右移一位时，数组最后一个元素跑到了数组第一个位置，数组其余元素统一向后挪动一个位置。
右移 m 位时，连续执行 m 次 “右移一位” 的操作。
3. 示例
现有整型数组
A=[1，2，3，4，5，6]\color{DeepPink}{A = [ 1，2，3，4，5，6 ]}A=[1，2，3，4，5，6]
循环向右移动两次，得到的结果应该是
A=[5，6，1，2，3，4]\color{DeepPink}{A = [ 5，6，1，2，3，4 ]}A=[5，6，1，2，3，4]
3.1 算法Ⅰ：循环单次右移一位
基本思想：将数组元素循环右移 m 次，每一次的操作如下图
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|---|
| 元素 |
1 |
2 |
3 |
4 |
5 |
6 |
|---|
一个整型变量 temp 保存最后一个位置的元素 temp=A[length−1]\color{DeepPink}{temp = A [length-1]}temp=A[length−1]；
然后将其余元素从下标 length-2 到下标 0 的元素右移一个位置；
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|---|
| 元素 |
1 |
1 |
2 |
3 |
4 |
5 |
|---|
将 temp中的值存放到数组下标 0 的位置；完成一次右移操作。
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|---|
| 元素 |
6 |
1 |
2 |
3 |
4 |
5 |
|---|
C代码如下：
void cyclicShiftRight(int n, int m)
{
int *testArray = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; ++i)
{
scanf_s("%d", testArray + i);
}
m = m % n;
if (0 == m)
{
}
else
{
for (int j = 1; j <= m; ++j)
{
int temp = testArray[n - 1];
for (int k = n - 2; k >= 0; --k)
{
testArray[k + 1] = testArray[k];
}
testArray[0] = temp;
}
}
for (int i = 0; i < n; ++i)
{
printf("%d", *(testArray + i));
if (i != n - 1)
{
printf(" ");
}
}
printf("\n");
free(testArray);
testArray = NULL;
}
int main()
{
int N = 0;
int M = 0;
scanf_s("%d %d", &N, &M);
cyclicShiftRight(N, M);
return 0;
}
3.2 算法Ⅱ：下标关系交换元素
假设循环右移 2 次（循环右移 8 次与其结果一致，因为 8%6 == 2），正确结果应该如下表
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|---|
| 元素 |
5 |
6 |
1 |
2 |
3 |
4 |
|---|
观察结果发现结果数组分为 2 个部分，一组有 2 个元素 “5” 和 “6” 保持有序，另一组 4 个元素 “1” 、“2”、“3” 和 “4” 保持有序。
于是将原数组看作两个部分，一组有 2 个元素保持有序，另一组 4 个元素保持有序，结果如下
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|---|
| 元素 |
1 |
2 |
3 |
4 |
5 |
6 |
|---|
将两个数组中的元素，每个部分数组第一个元素和自身最后一个元素交换，第二元素和倒数第二个元素交换，以此类推… …
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|---|
| 元素 |
4 |
3 |
2 |
1 |
5 |
6 |
|---|
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|---|
| 元素 |
4 |
3 |
2 |
1 |
6 |
5 |
|---|
然后整个数组看作一个整体，执行以上操作
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|---|
| 元素 |
5 |
6 |
1 |
2 |
3 |
4 |
|---|
此时得到了正确的结果。
C代码如下：
void swap(int testArray[], int firstIndex, int secondIndex)
{
if (firstIndex == secondIndex)
{
}
else
{
int temp = testArray[firstIndex];
testArray[firstIndex] = testArray[secondIndex];
testArray[secondIndex] = temp;
}
}
void ReverseArray(int testArray[], int leftIndex, int rightIndex)
{
int i = leftIndex;
int j = rightIndex;
while (i < j)
{
swap(testArray, i, j);
++i;
--j;
}
}
void cyclicShiftRight(int n, int m)
{
int *testArray = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; ++i)
{
scanf_s("%d", testArray + i);
}
m = m % n;
if (0 == m)
{
}
else
{
ReverseArray(testArray, 0, n - m - 1);
ReverseArray(testArray, n - m, n - 1);
ReverseArray(testArray, 0, n - 1);
}
for (int i = 0; i < n; ++i)
{
printf("%d", *(testArray + i));
if (i != n - 1)
{
printf(" ");
}
}
printf("\n");
free(testArray);
testArray = NULL;
}
int main()
{
int N = 0;
int M = 0;
scanf_s("%d %d", &N, &M);
cyclicShiftRight(N, M);
return 0;
}
以上两种代码在Microsoft Visual Studio 2015 以及 Microsoft Visual Studio 2017上运行成功。
4. 结论：
第一种算法由于要移动大量（数组很大的时候）的元素，效率不如第二种高。第二种算法更高效，时间复杂度低，优先考虑。
