循环移动数组元素

大家好，又见面了，我是你们的朋友全栈君。

// 循环移动数组元素 // 一种大部分数据只移动一次的算法 // 方法: // 将数据循环移动, 可以直接计算出每个数据的最终位置, 直接移动即可 // 分析: // 这种算法基本可看做每个数据只需要移动一次 // 但是每个数据移动的位置需要计算, 算法理解起来比较难, 实现也比较复杂 // 另外,由于总是间隔较远存取数据,在数据数量较大的时候会导致比较频繁缓存命中失败 // 常用的两次翻转算法,每个数据需要swap两次(平均每个移动3次),而且很容易理解,实现也简单

#include “stdafx.h” #include <algorithm> #include <iostream>

// 最大公约数 size_t gcd(size_t n, size_t m) { if(n==0 || m == 0) return 0;

while(true) { n %= m; if(n == 0) return m; std::swap(n, m); } }

// 循环左移 template<typename T> void CycleMove(T* data, size_t nLen, size_t nMov) { if(data == 0 || nLen <= 1) return;

nMov %= nLen; if(nMov == 0) return;

// 分组处理 size_t nGroup = gcd(nLen, nMov); // 每组数据数量 size_t nGroupSize = nLen / nGroup;

for(size_t i=0; i<nGroup; ++i) { // 保存第一个数 T d0 = data[i]; size_t iPosD = 0; size_t iPosS = i;

// 先移动nGroupSize-1个 for(size_t j=1; j<nGroupSize; ++j) { // 数据位置 iPosD = iPosS; iPosS += nMov; iPosS %= nLen;

// 将数据左移 data[iPosD] = data[iPosS]; } // 将第一个放到最后 data[iPosS] = d0; } }

int _tmain(int argc, _TCHAR* argv[]) { char data[] = {-52, 83, 111, 103, 46, 115, 82, -111}; size_t nNum = sizeof(data)/sizeof(data[0]);

CycleMove(data, nNum, 3);

for(size_t i=0; i<nNum; ++i) { std::cout << (int)data[i]; if(i != nNum-1) std::cout << ” , “; else std::cout << std::endl; }

return 0; }

// 输出 // 103 , 46 , 115 , 82 , -111 , -52 , 83 , 111

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/159963.html原文链接：https://javaforall.cn