自然归并排序（数组）.cpp

this package contains two .c files.One file implements the merge of two int arrays.The other one imp

#include<stdio.h>
#include<stdlib.h>

void print_array( int* a,int l )			// 打印数组
{
	int i;
	for( i=0;i<l;i++ )
		printf( "%3d",a[i] );	
	printf( "\n" );
}
void init_array( int* a,int l )				// 初始化数组
{
	int i;
	for( i=0;i<l;i++ )
		a[i] = 0;
}
int tab = 0;
void print_tab( int tab )					// 用于根据递归深度（tab）打印推进效果
{
	for(int i=0;i<tab;i++)
		printf("－－");
}
////////////////////////////////////////////////////////////////////////////////////////
void merge( int* array,int start,int mid,int end,int* faltagepp )            // 合并两个 升序排列.......
{	
	int start1 = faltagepp[start];
	int mid1 = faltagepp[mid+1]-1;
	int end1 = faltagepp[end+1]-1;

	printf("\n");
	int tmp_length = end1 - start1+1;				
	int* tmp = new int[tmp_length];	
	for( int i=start1;i<=end1;i++ )
		tmp[i-start1] = array[i];

	int indicator_left = start1;							// 创建三个数组指示器
	int indicator_right = mid1+1;
	int indicator_tmp = 0;

	while( true )
	{
		if( ( indicator_left == mid1+1 )&&( indicator_right == end1+1 ) )
			break ;

		else if( indicator_left == mid1+1 )
		{
			tmp[indicator_tmp] = array[indicator_right];
			indicator_tmp ++;
			indicator_right++;
		}
		else if( indicator_right == end1+1 )
		{
			tmp[indicator_tmp] = array[indicator_left];	
			indicator_tmp ++;
			indicator_left ++;	
		}

		else
		{
			if( array[indicator_left] <= array[indicator_right])
			{
				tmp[indicator_tmp] = array[indicator_left];	
				indicator_tmp++;
				indicator_left++;
			}
			else
			{
				tmp[indicator_tmp] = array[indicator_right];
				indicator_tmp++;
				indicator_right++;
			}
		}
	}
	printf( "这是部分排序后" );
	for( i=start1;i<=end1;i++ )
	{
		array[i] = tmp[i-start1] ;
		printf( "\narray[%2d] = %4d",i,array[i] );
	}
	printf( "\n" );
}	
////////////////////////////////////////////////////////////////////////////////////////

void merge_nature( int* arrayx,int start,int mid,int end,int* faltagep )
{	
		int tab_backup = tab;
		tab ++;
		print_tab( tab_backup );printf( "merge_nature %d 部分到第 %d 部分.....S.T.A.R.T......\n",start,end );
		if( start != mid )                 
		{
			int mid1 = (start + mid)/2;
			merge_nature( arrayx,start,mid1,mid,faltagep ); 	// 分治前一部分
		}
		if( mid+1 != end )
		{
			int mid2 = (mid+1 + end)/2;
			merge_nature( arrayx,mid+1,mid2,end,faltagep ); 	// 分治后一部分
		}

		merge( arrayx,start,mid,end,faltagep );								    // 合并
		printf("\n");print_tab( tab_backup );printf( "merge_nature第 %d 部分到第 %d 部分.....E.N.D..........\n",start,end );
}
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
	int array[] = {42,12,63,84,23,74,12,98,65,76,2,5,74,23,64,34,16,45,36};
	int length = sizeof( array ) / sizeof( int );

	printf( "数组长度是: %d\n",length );

	int* faltage = new int[length];
	init_array( faltage,length );

	int faltage_i = 1;	

	faltage[0] = 0;
	for( int i=0;i<length;i++ )			    			// 扫描断层位置.....
	{
		if( array[i] > array[i+1] )
		{
			faltage[faltage_i++] = i+1;
		}
	}	
	if( faltage_i == 1 )
	{
		printf( "\n已经为升序排列\n" );					// 若已经升序，则直接推出
		getchar();
		return 0;
	}
	faltage[faltage_i] = length;

	printf( "\n排序前数组:" );
	print_array( array,length );

	printf( "\n扫描到断层:" );
	print_array( faltage,length );

	printf( "\n存在 %d 个自然升序排列\n\n",faltage_i );                      //	共分为 faltage_i 个自然升序部分
	merge_nature( array, 0, (faltage_i-1)/2, faltage_i-1 ,faltage);			// merge_nature （部分0 - 部分faltage_i/2 ） AND （部分faltage_i/2 +1 - 部分faltage_i）

	printf( "\n排序后数组:" );
	print_array( array,length );

	printf( "\n" );
	getchar();
	return 0;
}