归并排序法简介

归并排序法小插曲

归并排序法简介

归并排序法（Merge Sort，以下简称MS）是分治法思想运用的一个典范。其主要算法操作可以分为以下步骤：

Step 1：将n个元素分成两个含n/2元素的子序列

Step 2：用MS将两个子序列递归排序（最后可以将整个原序列分解成n个子序列）

Step 3：合并两个已排序好的序列

易知，MS的关键在于Merge过程。对于这一过程的理解，算法导论中给出了一个形象的模型。

即假设桌面上有两堆已排序好的的牌，且每一堆都正面朝下放置。然后我们分别从两堆牌中选取顶上的一张牌（选取之后，堆顶端又会露出新的顶牌），选取较小的一张，放入输出堆，另一张放回。

重复这一步骤，最后直到一堆牌为空。由于两堆牌都是已排序，所以可知，只要将剩下的那堆牌盖到输出堆即完成整个排序过程。

归并排序法小插曲

算法导论为了简化伪代码，在此处用了两张值为∞的哨兵牌。这样，除非两堆都露出哨兵牌，否则所取的两张牌中必有最小值。这一设想避免了检查每一个堆是否是空的，但是由于无法在程序中表示哨兵牌（或许可以，只是我不知道罢了），我们只能在实际算法中放弃这一设想。

对于A=<5，2，4，7，1，3，4，6>数组，MS的大致操作流程如下图：

[5] [2] [4] [7] [1] [3] [2] [6] \\ / \\ / \\ / \\ / [2 5] [4 7] [1 3] [2 6] \\ / \\ / [2 4 5 7] [1 2 3 6] \\ / [1 2 2 3 4 5 6 7]

在递归的合并过程中，我们需要动态的创建一个缓存区，作为上面较小牌的输出堆。一次合并完毕之后，用缓存区的数据覆盖原始相应数组的数据。

于是乎，我们可以上面的思路，写出下面的相应代码（注意边界成立的条件）

/*

输 入: a(int[]) - 数组地址

nLeft(int) - 左端下标

nRight(int) - 右端下标

输 出: -

功 能: 归并排序

*/

void CSort::MergeSort(int a[], int nLeft, int nRight)

{

if (nLeft < nRight)

{

// 刚开始的时候写了(nLeft + nRight) >> 1

// 结果导致无限递归- -,直接报Stack overflow

int nMid = (nLeft + nRight) >> 1;

// 递归分组

MergeSort(a, nLeft, nMid);

MergeSort(a, nMid + 1, nRight);

// 合并

Merge(a, nLeft, nMid + 1, nRight);

}

}

/*

输 入: a(int[]) - 数组地址

nLeft(int) - 左段数据数组的首下标

nMid(int) - 右段数据数组的首下标

nRight(int) - 右段数据数组的尾下标

输 出: -

功 能: 合并两段数据

*/

void CSort::Merge(int a[], int nLeft, int nMid, int nRight)

{

// 设置两个游标

int nLVer = nLeft;

int nMVer = nMid;

int nLen = nRight - nLeft + 1;

// 创建缓存区,用以保存排序完整的数据

int* pArr = new int [nLen];

int* pVernier = pArr;

// 依次从两堆数据堆中弹出一个数据

// 将较小者置入缓存区

// 这里注意下nMid表示的意义,理解下取等号的理由

while (nLVer < nMid && nMVer <= nRight)

{

if (a[nLVer] <= a[nMVer])

{

// 很多人都说这么写代码纯粹装B- -

// 我承认可读性很差,但是方便....

*pVernier++ = a[nLVer++];

}

else

{

*pVernier++ = a[nMVer++];

}

}

// 找到不为空的数据堆,将其粘贴到缓存区后

// 此时pVernier刚好指向缓存区尾数据向右

// 偏移一个单位的位置

while (nLVer < nMid)

{

*pVernier++ = a[nLVer++];

}

while (nMVer <= nRight)

{

*pVernier++ = a[nMVer++];

}

// 将缓存区数据复制回原数组

for (int i = nLeft, k = 0; i <= nRight;)

{

a[i++] = pArr[k++];

}

// 释放缓存资源

delete [] pArr;

}