移位算法：面试和做项目必会

最近在项目里需要对采样数据做移位操作，研究了下几个移位操作算法，今天通过本文分享给大家。我们知道位运算中有循环左移和右移运算，但是，对于数组，链表，Vecter容器等数据结构，就需要自己实现移位算法了，本文以数组作为例子，和大家一起学习几种移位算法的实现。希望给大家在平时项目中能起到抛砖引玉的作用。

我们先设有一个数组data，数组data的大小为5，其值分别为{0，1，2，3，4}，需要分别对数组data循环右移3个元素和循环向左移动3个元素。

第一种方法

首先，我们来看第一种方法，对于循环右移3个元素，我们可以分解成：先对每个元素都向右移动一个元素，其中最后一个元素需要放到数组的开头位置，会得到一个新的数组，然后，用新的数组再做同样的操作，如此循环3次，即可实现循环右移3个元素。

同样的对于循环左移3个元素，也可这样分解，只不过需要将每个元素需要先向左移动，其中开头的元素就要放到末尾，得到的新数组。然后，再做同样的操作3次。

下面是C++代码实现，函数中参数data是需要循环操作的数组，参数size是数据的大小，参数moveStep是移动元素的个数，大于0表示向右移，小于0表示向左移。

void cycleShift1(int data[], int size, int moveStep){

auto rightMoveOnce = [&](int data[], int size)
{
int temp = data[size-1];
for(int i=size-1; i>0; i--)
{
data[i]=data[i-1];
}
data[0] = temp;
};

auto leftMoveOnce = [&](int data[], int size)
{
int temp = data[0];
for(int i=1; i<size; i++)
{
data[i-1]=data[i];
}
data[size-1] = temp;
};

moveStep %= size;
if(moveStep>0)
{
while(moveStep--)
{
rightMoveOnce(data, size);
}
}
else
{
while(moveStep++)
{
leftMoveOnce(data, size);
}
}
}

第二种方法

上面的第一种方法是最直观的的一种方法，不过，它的时间复杂度相对高一些。我们可以通过使用空间换取时间的方法对其进行优化。

这种方法需要创建一个新的数组作为临时辅助，以右移为例：

第一步，需要将结尾的三个数据{2,3,4}存放到这个新的辅助数组中。

第二步，将开头的两个数据{0,1}向右移动3个元素位置。

第三步，将辅助数组的数据{2,3,4}放到开头。

经过上面三步之后，即可得到最终的结果。

类似的，对于循环左移，就需要将开头的三个数据{0,1,2}存放到辅助数组中，结尾的两个数据{3,4}，向左移动3个元素位置。最后，再将辅助数组中的3个数据放到结尾。

下面是代码实现：

void cycleShift2(int data[], int size, int moveStep)
{
moveStep %= size;
if(moveStep>0)
{
int temp[moveStep] = {0};
for(int i = 0; i < moveStep; i++)
{
temp[i] = data[size - moveStep + i];
}

for(int i = 0; i < size - moveStep; i++)
{
data[size - i - 1] = data[size - moveStep - 1 - i];
}

for(int i = 0; i < moveStep; i++)
{
data[i] = temp[i];
}
}
else
{
moveStep *= -1;
int temp[moveStep] = {0};

for(int i = 0; i < moveStep; i++)
{
temp[i] = data[i];
}

for(int i = 0; i < size - moveStep; i++)
{
data[i] = data[moveStep + i];
}

for(int i=0; i < moveStep; i++)
{
data[size - moveStep + i] = temp[i];
}
}
}

第三种方法

我们还可以通过一个小技巧来实现循环移动的功能。

先看循环右移，首先，我们需要将数组分成两部分，第一部分是{0，1}，第二部分是{2，3，4}。

第一步，将{0,1}做个翻转，得到{1,0}

第二步，将{2,3,4}做个翻转，得到{4,3,2}

第三步，将{1,0,4,3,2}当作一个整体，再次翻转，得到{2,3,4,0,1}。

三次翻转之后，就可得到我们想要的结果。

同样的对于循环左移，就需要将数组分成{0,1,2}和{3,4}两部分。经过三步的翻转，可以得到循环左移的结果。

下面是三次翻转的代码实现：

void cycleShift3(int data[], int size, int moveStep)
{

auto reverse = [&](int data[], int startIndex, int endIndex)
{
for (; startIndex < endIndex; startIndex++, endIndex--)
{
double temp = data[endIndex];
data[endIndex] = data[startIndex];
data[startIndex] = temp;
}
};

moveStep %= size;

if(moveStep > 0) //Right shift
{
reverse(data, 0, size - moveStep - 1);
reverse(data, size - moveStep, size - 1);
}
else //Left shift
{
reverse(data, 0, 0 - moveStep - 1);
reverse(data, 0 - moveStep, size - 1);
}

reverse(data, 0, size - 1);
}

最后

上面和大家一起学习了三种移位算法的实现，最后我们写个小程序验证一下三种算法的结果。

void printData(int data[], int size)
{
for(int i=0; i < size; i++)
{
std::cout << data[i] << " ";
}
std::cout << std::endl;
}

int main()
{

int data1_1[] = {0,1,2,3,4};
int data1_2[] = {0,1,2,3,4};
int data2_1[] = {0,1,2,3,4};
int data2_2[] = {0,1,2,3,4};
int data3_1[] = {0,1,2,3,4};
int data3_2[] = {0,1,2,3,4};
int size = 5;
int moveStep = 3;

std::cout << "-------------" << std::endl;
cycleShift1(data1_1, size, moveStep);
cycleShift1(data1_2, size, -1*moveStep);
printData(data1_1,size);
printData(data1_2,size);

std::cout << "-------------" << std::endl;
cycleShift2(data2_1, size, moveStep);
cycleShift2(data2_2, size, -1*moveStep);
printData(data2_1, size);
printData(data2_2, size);

std::cout << "-------------" << std::endl;
cycleShift3(data3_1, size, moveStep);
cycleShift3(data3_2, size, -1*moveStep);
printData(data3_1, size);
printData(data3_2, size);

}

感谢大家的阅读，以上就是移位算法的全部内容，希望大家从中能有所收获，看完可以收藏以便查看，也记得转发、点赞和点亮再看哈！感谢支持！