最近做东西的时候出现这么一个问题，看起来很简单的：
#define LARGE_SIZE 1024
#define ELEMENT_NUM 5
class CItem
{
public:
TCHAR cID;
BYTE data[LARGE_SIZE];
};
CItem data[ELEMENT_NUM];
INT reposition[ELEMENT_NUM] = {4,2,0,3,1};
要求，根据repositon的内容调整data的内容，如上，把原来下标4的元素调到0，把原来下标2的元素调到1。
写个算法，复杂度为O(n)，还要尽量节省空间，因为LARGE_SIZE可以很大，并且ELEMENT_NUM可能远远不止5个元素。
马上能想到的方法就是：
INT i;
CItem *pToHandle = new CItem[ELEMENT_NUM];
memcpy(pToHandle, data, sizeof(data));
for(i=0; i<ELEMENT_NUM; i++)
{
data[i] = pToHandle[reposition[i]];
}
delete[] pToHandle;
但这不太符合节省空间的原则，有可能在一个嵌入式平台中，new操作就会失败。
问题看起来是简单，但却耗费了我不少时间，才写出这么一个算法，我直接贴上全部代码：
#include "stdafx.h"
#include <Windows.h>
#define LARGE_SIZE 1024
class CItem
{
public:
TCHAR cID;
BYTE data[LARGE_SIZE];
};
#define ELEMENT_NUM 10
int _tmain(int argc, _TCHAR* argv[])
{
//Data to test
CItem allData[ELEMENT_NUM];
INT i;
for (i=0; i<ELEMENT_NUM; i++)
{
allData[i].cID = 'A' + i;
}
INT position[ELEMENT_NUM] = {5, 1, 4, 3, 6, 9, 7, 2, 0, 8};
//The result be F B E D G J H C A I
for (i=0; i<ELEMENT_NUM; i++)
{
CItem swapItem;
if (position[i]==i)
continue;
swapItem = allData[i];
INT iSeek = i;
do
{
INT iToSeekNext = position[iSeek];
allData[iSeek] = allData[iToSeekNext];
position[iSeek] = iSeek;
iSeek = iToSeekNext;
} while (position[iSeek]!=i);
allData[iSeek] = swapItem;
position[iSeek] = iSeek;
}
for (i=0; i<ELEMENT_NUM; i++)
{
_tprintf(TEXT("%c "), allData[i].cID);
}
_tprintf(TEXT("\n"));
return 0;
}
看起来写得稍微有些乱，而且明显用了两层迭代，按道理说算法复杂度应该为O(n2)了，但再仔细分析代码后发觉：需要调整位置的元素，只需要移动一次，而整个遍历过程并不会出现重复遍历的情况。因此其实际复杂度应该为O(n)，已经是最高效了，看看还有没别的办法。