算法导论——归并排序

2013年9月30日 5点热度 0条评论 来源: Anger_Coder

     算法的设计有很多思想,之前的插入排序使用的是增量的方法,即在排好的子数组A中,将元素A[j]插入,形成新的子数组A。

这次将实现另一种排序——归并排序,归并排序采用了“分治法”(divide-and-conquer),本篇中包含

  • 分治法的一些定义
  • 归并排序的实现
  • 归并排序的算法分析
  • 参考资料

一、什么是分治法?

分治法,也可以称为分治策略:是将一个大规模的问题(原问题)划分成n个规模较小而结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解。

分治模式在每一层递归上都有三个步骤:

分解(divide):将原问题分解成一系列子问题
解决(conquer):递归地解决各子问题。若子问题足够小,则直接求解
合并(combine):将子问题的结果合并成原问题的解


合并排序(merge sort)即参照了上述的模式:

分解:将n个元素分成各含n/2个元素的子序列
解决:用合并排序法对两个子序列递归地排序
合并:合并两个已排序的子序列以得到排序结果
若对子序列排序时,其长度为1时递归结束。因为当数组中仅含有单个元素时,必定是有序的。

二、归并算法的实现

2.1 merge-sort的分析

归并排序主要分为递归与合并两个部分,下面的伪代码为合并部分,其中A是一个数组,p、q、r为下标,满足
p≤q<r,A[p...q]与A[q+1...r]都是已排序好的,并合并成一个已排序好的子数组代替当前子数组A[p...r]。
MERGE过程的时间代价为Ɵ(n)其中n = r - p + 1为待合并元素个数。



归并的递归过程,归并的临界点与数组元素为1,因为数组元素个数为1,代表数组元素已排序。否则进行数组一分为2的操作,下面为递归部分伪代码

利用merge-sort( A, p, r )对子数组A[p...r]进行排序。如果p≥r,则该子数组中至多只有一个元素,当然就是已排序的。否则,分解步骤就计算出一个下标q,将A[p...r]分解为A[p...q]和A[q+1...r],各含[n/2]个元素。

2.2 merge-sort的C语言实现

void merge ( int intArray[], int begin, int mid, int end )
{
	int n1 = mid - begin + 1;	
	int n2 = end - mid;
	int i, j, k;

	int *L = (int *) malloc ( sizeof ( int ) * n1 );
	int *R = (int *) malloc ( sizeof ( int ) * n2 );

	/*利用goto语句实现异常处理
	  当L或R未能正常分配时
	  将直接跳转至程序末尾,后续程序不再执行
	*/
	if ( L == NULL || R == NULL )
	{		
		goto error;			
	}
	
	for ( i = 0; i < n1; i++ )
		L[i] = intArray[begin + i];

	for ( j = 0; j < n2; j++ )
		R[j] = intArray[mid + 1 + j];

	i = j = 0;
	k = begin;

	while ( i < n1 && j < n2 )
	{
		if ( L[i] < R[j] )
		{
			intArray[k++] = L[i++];
		}
		else
		{
			intArray[k++] = R[j++];
		}
	}

	while ( i < n1 )
	{
		intArray[k++] = L[i++];
	}
	while ( j < n2 )
	{
		intArray[k++] = R[j++];
	}

	/*
		程序执行完毕后,在done处,进行资源释放
	*/
	goto done;

error:
	printf ( "malloc has benn failed!\n" );
done:
	if ( L != NULL && R != NULL )
	{
		free ( L );
		free ( R );
	}
}

void merge_sort ( int intArray[], int head, int tail )
{

	int mid;

	if ( head  < tail )
	{
		mid = ( head + tail ) / 2;
		printf ( "sort ( %d-%d %d-%d ) %d %d %d %d %d %d %d %d\n", head, mid, mid + 1, tail, intArray[0], intArray[1], intArray[2], intArray[3], intArray[4], intArray[5], intArray[6], intArray[7] );
		merge_sort ( intArray, head, mid );
		merge_sort ( intArray, mid + 1,  tail );
		merge ( intArray, head, mid, tail );
		printf ( "merge ( %d-%d %d-%d ) %d %d %d %d %d %d %d %d\n", head, mid, mid + 1, tail, intArray[0], intArray[1], intArray[2], intArray[3], intArray[4], intArray[5], intArray[6], intArray[7] );
	}
}

int main ( void )
{

	int a[8] = { 5, 2, 4, 7, 1, 3, 8, 6 };
	int i = 0;
	merge_sort ( a, 0, 7 );

	for ( i = 0; i < 8; i++ )
	{
		printf ( "%d ", a[i] );
	}

	while ( 1 );
}

三、排序算法分析


3.1 排序算法分析

这里有一个待排序的数组A= ( 5, 2, 4, 7, 1, 3, 2, 6 )

时间复杂度分析,设T(n)为一个规模为n的问题的运行时间。如果问题的规模足够小,如n≤c(c为常量),则得到它的直接解的时间为常量,写作Ɵ(1)。假设我们把原问题分解成a个子问题,每一个的大小是原问题的1/b(对于合并排序,a和b都是2,但在许多分治法中,a≠b)。如果分解该问题和合并解的时间各为D(n)和C(n),则递归式为

worst-case

分析T(n)最坏情况下,合并排序n个数的运行时间,合并排序一个元素的时间是个常量。当n>1时,将运行时间分解:

分解:这一步仅仅是计算出子数组的中间位置,需要常量时间,因而D(n)= Ɵ(1)

解决:递归地解两个规模为n/2的子问题,时间为2T(n/2)

合并:在一个含有n个元素的子数组上,MERGE过程的运行时间为Ɵ(n),则C(n) = Ɵ (n)

当我们再合并排序算法的分析中,将D(n)和C(n)相加时,我们是在将一个Ɵ(1)函数与另一个Ɵ(n)函数进行相加。相加的和是n的一个线性函数,即Ɵ(n)。将它与“解决”步骤中所得的2T(n/2)相加,即得到合并排序的最坏情况运行时间T(n)的递归表示

根据主定理(master theorem),它可以证明T(n)为Ɵ(nlgn)。

这里的lgn可以从树的深度测出,因为是取2的n此幂,因为,树的根节点为1,其他的分割是n/2;那么可以简单得出n = 1 * 2 * 2 * ... * 2,那么树的深度就是log_2 n,树的高度为log_2 n + 1。

3.2 排序算法与插入算法比较

因为对数函数的增长速度比任何线性函数增长的都要慢,因此,当输入规模足够大时,合并排序要比插入排序要好(worst-case下合并排序为Ɵ(nlgn),插入排序为Ɵ(n2))

四、参考资料

《算法导论》
《网易公开课》——算法导论

    原文作者:Anger_Coder
    原文地址: https://blog.csdn.net/anger_coder/article/details/12183815
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。