最近做東西的時候出現(xiàn)這么一個問題，看起來很簡單的：
#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};
要求，根據(jù)repositon的內(nèi)容調(diào)整data的內(nèi)容，如上，把原來下標4的元素調(diào)到0，把原來下標2的元素調(diào)到1。
寫個算法，復雜度為O(n)，還要盡量節(jié)省空間，因為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;
但這不太符合節(jié)省空間的原則，有可能在一個嵌入式平臺中，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)了，但再仔細分析代碼后發(fā)覺：需要調(diào)整位置的元素，只需要移動一次，而整個遍歷過程并不會出現(xiàn)重復遍歷的情況。因此其實際復雜度應該為O(n)，已經(jīng)是最高效了，看看還有沒別的辦法。