歸并算法理解起來還是比較簡單的，基本原理是將兩個已排序的數列歸并成一個排序的數列。那么要將一個無序的數列利用歸并算法排序，首先生成短的有序序列，利用歸并算法，逐漸合成長的有序序列。最直接的歸并方法為：對于兩個有序序列p1, p2，從p2中逐個選擇元素插入到p1中，這種方法簡單，但是效率不高，如果采用二分法查找并且分段插入，將能提高歸并效率。
分段歸并算法的原理是：對于有序序列p1和p2，建立三元結構（b, e, p），b為begin，代表p2序列中要插入到p1中的片段頭標識; e為end，代表p2序列要插入到p1中的片段的尾標識，p為point，代表p2要插入到p1中的位置。遍歷p2序列，找到所有的三元結構，然后利用三元結構將p2序列歸并到p1序列。
可以通過一個例子來說明如何使用三元結構：
有序序列：p1: 10, 18, 30, 41; p2: 3, 6, 12, 52
從p2序列第一個元素開始：p1: 10, 18, 30, 41; p2: 3, 6, 12, 52 —— (0, e, p)，begin = 0
可以看到p2第一個元素的插入點為0：p1: 10, 18, 30, 41; p2:?3, 6, 12, 52 —— (0, e, 0)，point = 0, 因為p2(0) = 3小于p1(0) = 10
然后通過快速查找算法搜索10在p2中的位置：p1:?10, 18, 30, 41; p2:?3, 6, 12, 52 —— (0, 2, 0)，end = 2，這樣就找到了一個三元體；
類似的有：p1:?10, 18, 30, 41; p2:?3,?6,?12, 52 —— (2, 3, 1)
? ? ? ? ? ? ? ? ? ? p1:?10,?18, 30, 41; p2:?3,?6,?12,?52?—— (3, 4, 4)
利用生成的所有三元體結構，將p2數據插入到p1中得到：3, 6, 10, 12, 18, 30, 41, 52
C++代碼實現：
#include
#include
#define LOG2(x) ((log(x)/log(2)))
using namespace std;
template
void MergeSort(vector &vec);
int main()
{
int att[] = { 10, 4, 23, 46, 20, 5, 3, 88, 8, 44, 53, 25, 86, 32, 16, 11};
vector vec(&att[0], &att[sizeof(att)/sizeof(int)]);
MergeSort(vec);
return 0;
}
template
void MergeSort(vector &vec)
{
int VSize = vec.size();
if (VSize <= 1)
return;
double Kf = LOG2(VSize);
int K = ((int)floor(Kf) == (int)ceil(Kf)) ? (int)floor(Kf) : (int)ceil(Kf);
T maxV = vec[0];
for (int vIdx = 0; vIdx < VSize; vIdx++)
{
if ((0 == (vIdx % 2)) && (vIdx + 1 < VSize) && (vec[vIdx] > vec[vIdx + 1]))
{
vec[vIdx] ^= vec[vIdx + 1];
vec[vIdx + 1] ^= vec[vIdx];
vec[vIdx] ^= vec[vIdx + 1];
}
maxV = (maxV > vec[vIdx]) ? maxV : vec[vIdx];
}
// insert max value at the end of vector to make up of vector length to pow(2, K)
if ((int)pow(2, K) > VSize)
vec.insert(vec.end(), pow(2, K) - VSize, maxV);
int newVSize = vec.size();
int Km = 2;
typedef struct
{
int begin;
int end;
int point;
} TripleStruct;
for (int kIdx = 2; kIdx <= K; kIdx++)
{
for (int kmIdx = 0; kmIdx < newVSize/(Km*2); kmIdx++)
{
vector vecTMP1(&vec[kmIdx * Km * 2], &vec[kmIdx * Km * 2 + Km]);
vector vecTMP2(vec.begin() + kmIdx * Km * 2 + Km, vec.begin() + kmIdx * Km * 2 + Km * 2);
vector tripleList;
if (vecTMP2[0] > vecTMP1[Km - 1])
continue;
for (int pIdx = 0; pIdx < Km; pIdx++)
{
int left = pIdx;
int right = Km - 1;
if (vecTMP2[Km - 1] < vecTMP1[0]) // vecTMP2 the whole element locates at the front of vecTMP1
{
TripleStruct triple = { 0, Km, 0 };
tripleList.push_back(triple);
break;
}
if (vecTMP2[pIdx] > vecTMP1[Km - 1])
{
TripleStruct triple = { pIdx, Km, Km };
tripleList.push_back(triple);
break;
}
// get insert point
TripleStruct triple;
triple.begin = pIdx;
if (vecTMP2[pIdx] < vecTMP1[left])
triple.point = left;
else
{
while (left != right)
{
int avg = (left + right) / 2;
if (vecTMP2[pIdx] > vecTMP1[avg])
left = avg;
else
right = avg;
if (left + 1 == right)
left = right;
}
triple.point = left;
}
// get insert end
int l_left = pIdx + 1;
int l_right = Km - 1;
if (pIdx == Km - 1)
{
triple.end = Km;
}
else if (vecTMP1[left] < vecTMP2[l_left])
triple.end = l_left;
else
{
while (l_left != l_right)
{
int avg = (l_left + l_right) / 2;
if (vecTMP1[left] < vecTMP2[avg])
l_right = avg;
else
l_left = avg;
if (l_left + 1 == l_right)
l_left = l_right;
}
triple.end = l_left;
}
pIdx = l_left - 1;
tripleList.push_back(triple);
}
// Process Inserting
int insertLength = 0;
int tripleSize = tripleList.size();
for (int tIdx = 0; tIdx < tripleSize; tIdx++)
{
vecTMP1.insert(vecTMP1.begin() + insertLength + tripleList[tIdx].point, vecTMP2.begin() + tripleList[tIdx].begin, vecTMP2.begin() + tripleList[tIdx].end);
insertLength += tripleList[tIdx].end - tripleList[tIdx].begin;
}
memcpy((char*)&vec[kmIdx * Km * 2], (char*)&vecTMP1[0], sizeof(T)*vecTMP1.size());
}
Km *= 2;
}
if ((int)pow(2, K) > VSize)
{
vector tmpvec(&vec[0], &vec[VSize]);
vec.assign(tmpvec.begin(), tmpvec.end());
}
for (int vIdx = 0; vIdx < VSize; vIdx++)
{
cout << "indx " << vIdx << " value " << vec[vIdx] << endl;
}
return;
} 
下載文檔
