本文共 5223 字，大约阅读时间需要 17 分钟。

上一篇日志讲到了自己对堆排序的学习，堆排序时间复杂度能达到O(NlogN)，且不需要额外的空间来存储排序过程中的有序序列，优点明显，不过堆排序不是稳定的，也就是说排序后相等数据之间的相对位置可能会发生改变。上一周的学习学到了一个同样时间复杂度为O（NlogN）的且是稳定的排序方法！那就是归并排序。

归并操作其实更多用在外部排序中- -、，是外部存储器最常用的排序方法，用分而治之的思想，下面会说。归并排序的核心是归并操作，归并操作是把有序子列做归并。下面看看归并操作的过程：

借用一道例题，上面我们看到两个已经按升序排好的序列，然后我们要把这两个序列归并成一个序列，归并后的序列仍是按升序排列。很简单我们可以想到用两个指针指示两个有序序列中元素的位置，从头开始每次比较两个指针指向的元素，较小的元素就先复制到那个额外空间里去，然后指针指向的元素往后挪一位，直到最后某一个有序序列的所有元素都复制到额外空间里去后，把另外一个序列的所有元素都跟着全放进去就可以了（因为序列本来有序嘛，直接往里仍）。

比较16比25小，就把16放下来，指针往后挪一位。

25比38小，就25挪下来。

一直做下去，直到某一个子序列元素为空，就把剩下的序列中所有元素放下来。

上面就是归并操作的过程，是归并操作不是归并排序哦！！就归并操作而言，时间复杂度是O（N），也就是说两个子序列中总共N个元素都被扫描了一遍。

那么归并操作的代码要怎么写？思路就是先开一个大小为两个子序列大小之和的额外空间，然后用两个指针分别指向两个序列的首元结点，开始两两互相比较，然后插入到额外空间中去就可以了：

/*归并操作*/void Merge(PtrlSqList P, PtrlSqList M, int L, int R, int RightEnd) {	/*L是左边序列的起始位置,R是右边序列的起始位置,RightEnd是右边序列的终点位置.*/	/*L和R是指向两个序列的指针*/	int LeftEnd, ElementNum, Tmp, i;		LeftEnd=R-1; /*左序列的终点位置是右边序列起始位置-1*/ 	Tmp=L; /*Tmp记录第一次序列的左开始位置,即等于1,下面用来给临时额外空间做插入用.*/	ElementNum=RightEnd-L+1; /*!!!!*/	printf("ElementNum=%d L=%d LeftEnd=%d R=%d RightEnd=%d\t", ElementNum, L, LeftEnd, R, RightEnd);			/*当左边序列没到最后一个元素 && 右边序列也没到最后一个元素时,继续归并操作*/ 	while (L<=LeftEnd && R<=RightEnd) {		/*从左右序列的第一个元素开始亮两两比较*/		if (P->arr[L]<=P->arr[R]) {			M->arr[Tmp++]=P->arr[L++]; 		} else {			M->arr[Tmp++]=P->arr[R++];		} 	}		/*当其中一个元素插入完后,把另一个序列的剩余元素全部插入到额外空间中*/	while (L<=LeftEnd) {		M->arr[Tmp++]=P->arr[L++];	} 	while (R<=RightEnd) {		M->arr[Tmp++]=P->arr[R++];	}	/*把额外空间中排好序的序列复制回用户的序列中*/	for (i=0; i
   
    0; i++, RightEnd--) {		P->arr[RightEnd]=M->arr[RightEnd];	}  	PrintList(P, 0);	printf("\n\n"); //美观用}
   

参数L和R就是上图中的两个指针了，RightEnd是右边子序列的结束为止，为什么不用传进去左边子序列的结束位置？因为我们用右序列的开始位置-1就当作左序列的结束位置，这样就能把一个序列分成两个序列了（第149行）。至于Tmp一开始是等于左序列的开始位置也就是等于1，刚好用来做额外空间的指针。第151行的ElementNum记录的是当前要做归并的子序列的元素总个数，为什么是等于RightEnd-L+1也就是说等于右序列结束位置下标-左序列开始位置下标后，还要加1？因为我们的序列是从下标为1开始存储！！第152行只是我用来输出各个数据看看而已，方便调试，大家不用看。

然后归并操作时第155行开始，当两个序列中都还有元素时，就比较左右指针指向的元素，这里用升序排序，所以较小的先放进去。直到有其中一个序列中元素没有了，也就是指针越界了，L大于LeftEnd或者R大于RightEnd，第164行开始就把剩下的序列中的所有元素都放进额外空间M里就可以了。

接下来还有重要的一步，就是把额外空间里的所有元素复制回用户的序列中去，返回给用户，这一步很重要，因为复制回去我们不是从下标为L开始复制到下标为RightEnd，我们看上面的代码，L和R都是指针，随着插入操作L和R都不是原来的值了，当然你可以一开始又用一个变量来保存L的值，其实我们不需要，因为我们的RightEnd是从始至终没有变化的，所以我们可以倒过来从RightEnd的位置开始复制数据回去，第172行就是这样的方法，这样就省了又新建一个变量啦！

归并操作没问题，接着到归并排序了，对于一个无序的序列，上面的方法可以把序列一分为二，那么排序要怎么做？序列初始是无序的啊。

上面说到归并排序用到分而治之的思想，分而治之的思想就是先把无序序列一分为二，然后递归地把左边序列，然后再递归地把右边序列排序，最后就会得到两个有序的序列，且两个序列相连着，最后来一个归并操作就可以了。这个递归代码是这样：

/*递归归并排序*/void Msort(PtrlSqList P, PtrlSqList M, int L, int RightEnd) {	int Mid; /*取中间值,当作把序列平分的边界*/		/*如果左边序列开头位置小于右边序列结束位置,即整体序列中还有元素*/	if (L

参数中传进去待排序列P和额外空间M，M的大小和P一样。L是待排序列P的开始位置也就是 1，RightEnd是待排序列P的终点位置，也就是序列长度P->length。排序代码中要把待排序列P一分为二嘛。所以定义一个变量Mid做平分序列的中间值，也就是（0L+RightEnd）/2。接着把Mid当作左序列的终点位置，Mid+1当作右序列的开始位置继续传进去递归，先递归左序列，左边序列排序好后再递归处理右边序列，最后做归并操作即可，第138行的归并操作中参数L是左序列的起始位置，Mid+1是右序列的起始位置也就是两个指针。

最后最后，我们再给这个排序包装一下，包装成之前我熟悉的统一接口形式，也就是归并排序传进去的是用户的待排序列和要排序的个数：

/*归并排序*/void Merge_Sort(PtrlSqList P, int length) {	int i=0;	/*创建一个额外空间存放有序序列*/	PtrlSqList M=CreatList();	for (i=0; i<=MaxSize; i++) {		M->arr[i]=-1;	}	if (M->length!=MaxSize) {		/*开始递归归并排序*/		/*传进去的参数:待排序列P,存放有序序列M,最开始左边位置1,结束位置length*/		Msort(P, M, 1, length); /*递归归并排序*/ 		/*排序完后释放掉临时额外空间M*/		free(M); 	} else {		/*如果归并排序没做完,M就没空间了*/ 		printf("空间不足");	}}

在这个归并排序代码里初始化一个额外空间M，用来传进去做排序用，然后第116行，把待排序列P和额外空间M传进去，1是我们最开始的左边序列的开始位置，右边序列的终点位置就是要排序的个数了，这里传进去P的长度就是把整个序列P都做排序，最后做完归并排序后就把额外空间M释放掉就ok。

上面这个是递归方法实现归并排序的，但是我们知道递归其实内部很复杂，很容易出错！所以，归并排序有非递归的方法，也就是用循环来实现，我学这部分时，主要是那些位置关系花了时间去看明白，其他我相信难不倒大家，接下来我也来分享下学习非递归也就是循环方式的归并排序怎么做。

循环方式的归并排序思路就是递归归并排序的思路反过来，也就是分而治之的从下往上。递归归并排序就是先把一整个待排序列一分为二，然后递归的继续分，从左边开始分，分到只剩一个元素后就表示分完了，再递归把右边的序列也一分为二，一直做下去….而循环方式就是倒过来，一开始先把整个长度为N的待排序列分成N个长度为1的有序序列，因为长度为1，所以我们把它看作是N个元素每个元素都是有序的。然后把相邻的两个子序列做两两归并，就变成了有N/2个有序序列了，此时每个有序序列的长度都乘了2。接下来继续重复上面步骤，得到N/4个有序序列，每个有序序列的长度又增长了一倍。一直到分母等于N/2后，也就是最后只剩下两个序列了，就把两个序列做一次归并操作，也有可能在某次归并过程中会多出一个序列来（例如有三个子序列，前两个子序列做了归并后，剩下一个没做归并操作的子序列就和前面那个序列不等长了）。这种情况，就把不等长的那个序列全部接到前面序列的尾部去。

上面说了一大堆，加上自己表述的可能不是很好，大家可能会听不懂我说的话- -、，下面我们边看代码，我边解释循环方式的归并排序要怎么做吧！

/*循环归并排序*/void CircleMsort(PtrlSqList P, PtrlSqList M, int N, int length) {	/*参数N是整个待排序列的长度,length是当前有序序列的长度*/	int i, j;		for (i=1; i<=N-2*length; i+=2*length) {		Merge(P, M, i, i+length, i+2*length-1); //!!		/*i+length
   
    arr[j]=P->arr[j];			}		}	}}
   

传进去的参数和递归方法有点不同，N是整个待排序列的长度，length是当前看作是有序序列的长度（例如一开始是1，把每一个元素都看作是有序的）。接下来思路是，从第一个位置开始，把两个有序序列归并，然后再把下一段的两个有序序列也归并，直到所有有序序列都两两归并。看代码第138行的归并操作，i是左序列的开始位置，i+length是左序列的终点位置，i+2*length-1是右序列的终点位置，把这两个序列做归并后，我们要判断，当前是否还有没做归并的子序列，第140行，如果i（i就是当前左序列的开始位置）+     length小于当前整个待排序列的长度N的话，证明还有两个等长的子序列，所以再把它们做一次归并，如果i+length<N的话，证明最后那个序列是不等长的，是在这一轮归并过程中没有做归并操作的，所以直接把这个不等长的没做归并操作的序列接上去前面那个序列就可以了。

最后的最后就是回到接口函数那里，我们看下接口函数：

/*归并排序接口函数*/void Merge_Sort(PtrlSqList P, int length) {	int i=0;	int ListLength=1; /*初始化有序序列长度为1,也就是说每一个元素都看成是有序的*/	/*创建一个额外空间存放有序序列*/	PtrlSqList M=CreatList();	for (i=0; i<=MaxSize; i++) {		M->arr[i]=-1;	}	if (M->length!=MaxSize) {		/*开始循环归并排序*/		/*传进去的参数:待排序列P,存放有序序列M,最开始左边位置1,结束位置length*/		while (ListLength

先初始化有序序列的长度为1，也就是一开始把用户的长度为N的待排序列分成N个有序的序列，接着开始调用循环归并函数。当有序序列的长度小于用户的待排序列长度N时，就一直做归并，每一轮归并排序后有序序列的长度增加了一倍，因为是两个等长的序列归并嘛，所以ListLength*2。为什么while循环里要调用两次归并排序函数？因为这样能保证最后排完序后的有序序列是存在用户的序列P中的，哪怕在上一个Msort中已经排好序了，最后我们要的是保证有序序列回到用户的序列P中。

上面可能表述的不好，大家见谅。

完整代码已上传个人代码云：

转载地址：http://rvtm.baihongyu.com/