数据结构学习笔记——归并排序

一、排序思想

归并排序是将两个或两个以上的有序表组合成一个新的有序表，它采用的是分治法，例如将两个有序表合并成一个有序表，即二路归并排序，二路归并排序的步骤如下：
①将含n个元素的序列分为由n个长度为1的有序子表；
②相邻的两个有序子表归并为一个有序子表（两两相邻归并）；
③重复以上步骤，最终归并成一个长度为n的有序表。

对于N个元素进行k路归并排序，其排序的趟数m满足k^m=N，即m=⌈log_kN⌉（⌈⌉表示向上取整，取比自己大的最小整数）。

例如，对于序列{34，15，13，93，65，74，20，17}，对其进行归并排序，基本过程如下：

1、将初始序列分为8个只含有1个元素的子序列：

2、第一趟归并。两两归并，形成若干个由两个元素组成的子序列：

3、第二趟归并。继续两两归并，形成两个由四个元素组成的子序列：

4、第三趟归并。继续两两归并，即可形成一个完整的有序序列：

归并排序的是一个递归的过程，分别对划分后的左右子序列进行处理，Merge()函数中借助到了一个辅助数组r1，首先将划分的子序列放在该数组相邻位置，每次从该数组的两段子序列中取出元素进行比较，较小者放回原本的数组r[]中，代码如下，：

/*归并*/
void Merge(int r[],int low,int mid,int high) {
	int *r1=(int *)malloc((high-low+1)*sizeof(int));	//辅助数组r1 
	for(int k=low; k<=high; k++)
		r1[k]=r[k];	//将r中的所有元素复制到r1中 
	for(i=low,j=mid+1,k=i; i<mid&&j<=high; k++) {//low指向为第一个有序表的第一个元素，j指向第二个有序表的第一个元素
		if(r1[i]<=r1[j])	//比较r1的左右两段中的元素 
			r[k]=r1[i++];	//将较小值复制到r1中 
		else
			r[k]=r[j++];
	}
	while(i<=mid)
		r[k++]=r1[i++];	//若第一个表没有归并完的部分复制到尾部 
	while(i<=high)
		r[k++]=r1[j++];	//若第二个表没有归并完的部分复制到尾部 
}

/*归并排序*/
void MergeSort(int r[],int low,int high) {
	if(low<high) {
		int mid=(low+high)/2;	//划分 
		MergeSort(r,low,mid);	//对左有序子表递归 
		MergeSort(r,mid+1,high);	//对右有序子表递归 
		Merge(r,low,mid,high);	//归并
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

二、算法分析

以二路归并排序为例，进行相关分析。

（一）适用性和稳定性

归并排序是一种常用的外部排序（Out-place），且是一种稳定的排序算法，可适用于顺序存储和链式存储的线性表。

（二）时间复杂度

每趟归并排序的时间复杂度为O(n)，整个归并排序共有⌈log₂n⌉趟，所以该排序算法的时间复杂度为O(nlog₂n)。

（三）空间复杂度

由于算法中用到了递归工作栈，递归工作栈的空间复杂度为O(log₂n)，另外还需用到辅助数组，其空间复杂度为O(n)，所以该排序算法的空间复杂度为O(n)。

（四）比较次数

（1）归并排序过程中，比较次数与初始序列无关；
（2）二路归并排序中，每选出一个较小的元素需对比元素1次，可推出：在n路归并排序中，每选出一个较小的元素需对比元素的次数为m-1次；
（3）二路归并排序过程，类似于一棵倒立的二叉树，其性质符合二叉树的性质。

三、排序算法总结