排序算法：归并算法
扫描二维码
随时随地手机看文章
归并算法理解起来还是比较简单的，基本原理是将两个已排序的数列归并成一个排序的数列。那么要将一个无序的数列利用归并算法排序，首先生成短的有序序列，利用归并算法，逐渐合成长的有序序列。最直接的归并方法为：对于两个有序序列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;
} 
下载文档
