数组元素前移、后移

本文首发于公众号:水很大
将一个长度为N的数组依次前移K位。
取数组长度为9,前移5位并通过表格来解释。
第一次找到一个标志位(这个标志位是为了解释方便而特意取的一个),通过标志位将表格分成了两部分,分别对这两部分进行逆置

1	2	3	4	5		6	7	8	9

通过逆置得到结果

5	4	3	2	1		9	8	7	6

第二次对整个表格逆置

6	7	8	9	1		2	3	4	5

这样就得到了元素依次前移五位后的数组。

void swap(int array[N],int m,int n){
  int temp;
  for(int i = m;i<=((n-m)/2+m);i++){
    temp = array[n-i+m];
    array[n-i+m] = array[i];
    array[i] = temp;
  }
}

数组前移已经知道怎么处理了，但是数组后移又该怎么处理?
还是通过一个表格解释
第一次:对整个表格逆置

1	2	3	4	5		6	7	8	9

得到结果:

9	8	7	6	5		4	3	2	1

第二次:分别对表格两个部分逆置

5	6	7	8	9		1	2	3	4

其实数组元素前移、后移本质上是一样的。其区别仅仅在于前移是先将数组的两个部分分别逆置然后整体逆置,而数组后移是先对数组进行整体逆置然后再部分逆置。
看到这里可能有一个疑问:标志位(即表格中的空格)是怎么选取的？

1	2	3	4	5	6	7	8	9

表格元素前移五位的结果是:

6	7	8	9	1	2	3	4	5

分割一下:

6	7	8	9		1	2	3	4	5

可以看见1-5整体在空格后面,6-9整体在空格前面。所以需要考虑的问题是怎样将这两部分分别放到空格的两边。

1	2	3	4	5

逆置

5	4	3	2	1

对于

6	7	8	9

逆置

9	8	7	6

再合并

5	4	3	2	1	9	8	7	6

逆置

6	7	8	9	1	2	3	4	5

最终代码:

#include<stdio.h>
#define N 9 //数组大小
#define K 5 //前移位数

void swap(int array[N],int m,int n){
  int temp;
  for(int i = m;i<=((n-m)/2+m);i++){
    temp = array[n-i+m];
    array[n-i+m] = array[i];
    array[i] = temp;
  }
}
int main(void){
  int array[N];
  for(int i=0;i<N;i++){//初始化 
    array[i] = i+1;
  }
  //前移
  swap(array,0,N-1);
  swap(array,0,K-1);
  swap(array,K,N-1);
  //后移
  /*
  swap(array,K,N-1);
  swap(array,0,N-1);
  swap(array,0,K-1);
  */
  //输出
  for(int i=0;i<N;i++){
    printf("%d ",array[i]);
  } 
}