(十一)数据结构之归并排序算法实现

「爱情、让人受尽委屈。」 2022-06-08 06:29 159阅读 0赞

## 1、递归归并排序 ##

具体实现如下：

/* 递归排序 */
    void Merge_sort_r( ElementType A[], int N )
    { 
    	ElementType *TmpA;
    	TmpA = malloc( N * sizeof( ElementType ) );
    	if ( TmpA != NULL ) 
    	{
    		MSort_r( A, TmpA, 0, N-1 );
    		free( TmpA );
    	}
    	else printf("Merge_sort_r malloc error!\n");
    }

它会调用MSort\_r函数进行子序列的归并：

/* 递归进行子序列的归并 */
    static void MSort_r( ElementType A[], ElementType TmpA[], int L, int RightEnd )
    { 
    	int Center;
    	if ( L < RightEnd ) 
    	{
    		Center = ( L + RightEnd ) / 2;
    		MSort_r( A, TmpA, L, Center );
    		MSort_r( A, TmpA, Center+1, RightEnd );
    		Merge_r( A, TmpA, L, Center+1, RightEnd );
    	}
    }

它会调用Merge\_r进行有序子列的归并：

/* 有序子列的归并 */
    static void Merge_r( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
    { 
    	int LeftEnd;
    	int Tmp;
    	int NumElements;
    	int i;
    	
    	LeftEnd = R - 1; 		/* 左边终点位置。假设左右两列挨着*/
    	Tmp = L; 				/* 存放结果的数组的初始位置*/
    	NumElements = RightEnd - L + 1;
    	while( L <= LeftEnd && R <= RightEnd ) 
    	{
    		if ( A[L] <= A[R] ) TmpA[Tmp++] = A[L++];
    		else TmpA[Tmp++] = A[R++];
    	}
    	
    	while( L <= LeftEnd ) /* 直接复制左边剩下的*/
    		TmpA[Tmp++] = A[L++];
    	while( R <= RightEnd ) /*直接复制右边剩下的*/
    		TmpA[Tmp++] = A[R++];
    
    	/* 将数据复制回原数组 */
    	for( i = 0; i < NumElements; i++, RightEnd -- )
    		A[RightEnd] = TmpA[RightEnd];
    }

## 2、非递归归并排序 ##

具体实现如下：

/* 非递归归并排序 */
    void Merge_sort( ElementType A[], int N )
    { 
    	int length = 1; 		/* 初始化子序列长度*/
    	ElementType *TmpA;
    	
    	TmpA = malloc( N * sizeof( ElementType ) );
    	if ( TmpA != NULL ) 
    	{
    		while( length < N ) 
    		{
    			Merge_pass( A, TmpA, N, length );
    			length *= 2;
    			Merge_pass( TmpA, A, N, length );
    			length *= 2;
    		}
    		free( TmpA );
    	}
    	else printf("Merge_sort malloc error!\n");
    }

它会调用Merge\_pass对指定长度子序列进行归并：

/* 对指定长度子序列进行归并, length表示有序之列的长度 */
    static void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length ) 
    { 
    	int i, j;
    	for ( i=0; i <= N-2*length; i+=2*length )
    		Merge( A, TmpA, i, i+length, i+2*length-1 );
    	
    	if ( i+length < N ) 	/* 归并最后2个子列*/
    		Merge( A, TmpA, i, i+length, N-1);
    	else 					/* 最后只剩1个子列*/
    		for ( j = i; j < N; j++ ) TmpA[j] = A[j];
    }

它会调用Merge进行有序子列的归并：

/* 有序子列的归并 */
    static void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
    { 
    	int LeftEnd;
    	int Tmp;
    	int NumElements;
    	int i;
    	
    	LeftEnd = R - 1; 		/* 左边终点位置。假设左右两列挨着*/
    	Tmp = L; 				/* 存放结果的数组的初始位置*/
    	NumElements = RightEnd - L + 1;
    	while( L <= LeftEnd && R <= RightEnd ) 
    	{
    		if ( A[L] <= A[R] ) TmpA[Tmp++] = A[L++];
    		else TmpA[Tmp++] = A[R++];
    	}
    	
    	while( L <= LeftEnd ) /* 直接复制左边剩下的*/
    		TmpA[Tmp++] = A[L++];
    	while( R <= RightEnd ) /*直接复制右边剩下的*/
    		TmpA[Tmp++] = A[R++];
    }

## 3、完整示例代码 ##

/* 归并排序的递归和非递归实现 */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 定义一些辅助数据结构或者类型 */
    typedef int ElementType;
    
    /******************************************递归排序******************************************/
    
    /* 有序子列的归并 */
    static void Merge_r( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
    { 
    	int LeftEnd;
    	int Tmp;
    	int NumElements;
    	int i;
    	
    	LeftEnd = R - 1; 		/* 左边终点位置。假设左右两列挨着*/
    	Tmp = L; 				/* 存放结果的数组的初始位置*/
    	NumElements = RightEnd - L + 1;
    	while( L <= LeftEnd && R <= RightEnd ) 
    	{
    		if ( A[L] <= A[R] ) TmpA[Tmp++] = A[L++];
    		else TmpA[Tmp++] = A[R++];
    	}
    	
    	while( L <= LeftEnd ) /* 直接复制左边剩下的*/
    		TmpA[Tmp++] = A[L++];
    	while( R <= RightEnd ) /*直接复制右边剩下的*/
    		TmpA[Tmp++] = A[R++];
    
    	/* 将数据复制回原数组 */
    	for( i = 0; i < NumElements; i++, RightEnd -- )
    		A[RightEnd] = TmpA[RightEnd];
    }
    
    
    /* 递归进行子序列的归并 */
    static void MSort_r( ElementType A[], ElementType TmpA[], int L, int RightEnd )
    { 
    	int Center;
    	if ( L < RightEnd ) 
    	{
    		Center = ( L + RightEnd ) / 2;
    		MSort_r( A, TmpA, L, Center );
    		MSort_r( A, TmpA, Center+1, RightEnd );
    		Merge_r( A, TmpA, L, Center+1, RightEnd );
    	}
    }
    
    /* 递归排序 */
    void Merge_sort_r( ElementType A[], int N )
    { 
    	ElementType *TmpA;
    	TmpA = malloc( N * sizeof( ElementType ) );
    	if ( TmpA != NULL ) 
    	{
    		MSort_r( A, TmpA, 0, N-1 );
    		free( TmpA );
    	}
    	else printf("Merge_sort_r malloc error!\n");
    }
    
    
    /*****************************************非递归排序*****************************************/
    
    /* 有序子列的归并 */
    static void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
    { 
    	int LeftEnd;
    	int Tmp;
    	int NumElements;
    	int i;
    	
    	LeftEnd = R - 1; 		/* 左边终点位置。假设左右两列挨着*/
    	Tmp = L; 				/* 存放结果的数组的初始位置*/
    	NumElements = RightEnd - L + 1;
    	while( L <= LeftEnd && R <= RightEnd ) 
    	{
    		if ( A[L] <= A[R] ) TmpA[Tmp++] = A[L++];
    		else TmpA[Tmp++] = A[R++];
    	}
    	
    	while( L <= LeftEnd ) /* 直接复制左边剩下的*/
    		TmpA[Tmp++] = A[L++];
    	while( R <= RightEnd ) /*直接复制右边剩下的*/
    		TmpA[Tmp++] = A[R++];
    }
    
    
    /* 对指定长度子序列进行归并, length表示有序之列的长度 */
    static void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length ) 
    { 
    	int i, j;
    	for ( i=0; i <= N-2*length; i+=2*length )
    		Merge( A, TmpA, i, i+length, i+2*length-1 );
    	
    	if ( i+length < N ) 	/* 归并最后2个子列*/
    		Merge( A, TmpA, i, i+length, N-1);
    	else 					/* 最后只剩1个子列*/
    		for ( j = i; j < N; j++ ) TmpA[j] = A[j];
    }
    
    /* 非递归归并排序 */
    void Merge_sort( ElementType A[], int N )
    { 
    	int length = 1; 		/* 初始化子序列长度*/
    	ElementType *TmpA;
    	
    	TmpA = malloc( N * sizeof( ElementType ) );
    	if ( TmpA != NULL ) 
    	{
    		while( length < N ) 
    		{
    			Merge_pass( A, TmpA, N, length );
    			length *= 2;
    			Merge_pass( TmpA, A, N, length );
    			length *= 2;
    		}
    		free( TmpA );
    	}
    	else printf("Merge_sort malloc error!\n");
    }
    
    
    /* 程序入口 */
    int main()
    {
    	int i;
    	ElementType temp;
    	ElementType array[10];
    
    	printf("Input 10 numbers : ");
    	for(i = 0; i < 10; i++)
    	{
    		scanf("%d", &temp);
    		array[i] = temp;
    	}
    
    	/* 原始数据输出 */
    	printf("***********************************Origin************************************\n");
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	/* 选择排序后输出 */
    	printf("***********************************Merge_r*********************************\n");
    	Merge_sort_r(array, sizeof(array)/sizeof(array[0]));
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	printf("Input 10 numbers : ");
    	for(i = 0; i < 10; i++)
    	{
    		scanf("%d", &temp);
    		array[i] = temp;
    	}
    
    	/* 原始数据输出 */
    	printf("***********************************Origin************************************\n");
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	/* 选择排序后输出 */
    	printf("***********************************Merge***********************************\n");
    	Merge_sort(array, sizeof(array)/sizeof(array[0]));
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    	
    	return 0;
    }