又见 “归并” 算法

àì夳堔傛蜴生んèń 2022-03-20 01:26 183阅读 0赞

归并算法： 同样，也是回忆篇：[http://blog.csdn.net/shanshanpt/article/details/8680224][http_blog.csdn.net_shanshanpt_article_details_8680224]

也不想多解释什么，主要是自己做到九度OJ的题目时候想到又要整理一下了，开始看到题目还真没思路，哎，笨啊

~ 不过此题使用归并确实是好办法( 我的代码在九度Oj已经通过 )

题目：[http://ac.jobdu.com/problem.php?cid=1039&pid=19][http_ac.jobdu.com_problem.php_cid_1039_pid_19]

下面回忆回忆：说到归并其实是很简单的算法，但是思想很好！要灵活使用才是王道！

其本质就是“ 分治 ”：

我们知道两个有序的数组进行排序的时候，增加一个辅助数组就OK，然后扫描进辅助数组，时间复杂度O( m + n )，是线性时间，很快哦~呵呵~

那么对于两个不是有序的数组，我们怎么办，对，我们知道一个元素肯定是有序的，那么分治就可以很好的解决问题，一个变两个，两个变四个。。。。。

代码：

#include <stdio.h>
    #include <stdlib.h>
    
    int *tmp;    // 全局的中间缓冲数组
    
    void merge_two(int data[], int low, int mid, int high )
    {
    	int i = low;
    	int j = mid + 1;
    	int x = 0;
    	
    	while ( i <= mid && j <= high )
    	{
    		if ( data[i] <= data[j] )
    		{
    			tmp[x++] = data[i++];
    		}
    		else
    		{
    			tmp[x++] = data[j++];
    		}
    	}
    	
    	while (i <= mid)	// 下面是收尾工作，呵呵！
    	{                   // 注意下面的；两个while只会执行一个！
    		tmp[x++] = data[i++];
    	}
    	
    	while (j <= high)
    	{
    		tmp[x++] = data[j++];
    	}
    	
    	for ( i = 0; i < x; i++ )  // 再归还给数组data
    	{
    		data[low + i] = tmp[i];
    	}
    }
    
    // 使用分治来处理！
    // 
    void merge( int data[], int low, int high )
    {
    	int mid;
    
    	if ( low < high )
    	{
    		mid = (low + high) / 2;
    		merge(data, low, mid);			// 左边一半 
    		merge(data, mid + 1, high);		// 右边一半
    		merge_two(data, low, mid, high);// 合并
    	}
    }
    
    
    int main()
    {
    	int *data, n, i;
    
    	while( scanf("%d", &n) != EOF )
    	{
    		data = ( int* )malloc( sizeof( int ) * n );
    		
    		for( i = 0; i < n; i++ )
    		{
    			scanf("%d", &data[i]);
    		}
    
    		tmp = ( int* )malloc( sizeof( int ) * n );  // 缓冲区
    
    		merge(data, 0, n - 1);      // 处理开始
    
     		for( i = 0; i < n; i++ )
    		{
    			printf("%d ", data[i]);
    		}
    		printf("\n");
    		
    		free( data );
    		free( tmp  );
    	}
    
    	return 0;
    }

下面关于九度上那题，其实也就easy了，例如：现在只有两个有序的数 A：( 2， 4 ) 和 B：( 1，3 ) ，当我们归并的时候，遇到 data\[i\] < data\[j\] ，那么我们知道1肯定小于数组A中2及2以后所有的数，所以all\_count += A中2以后的数的个数！YES~， 再扫描到3时候，同样是这样的处理！当然我们也可以使用前面的数组，只不过改一个符号而已！下面

代码：( 已经AC到九度OJ )

#include <stdio.h>
    #include <stdlib.h>
    
    int *tmp = NULL;  // 全局的中间缓冲数组
    long int all_count = 0;  // 计算逆序数对
    
    void merge_two(int data[], long int low, long int mid, long int high )
    {
    	long int i = low;
    	long int j = mid + 1;
    	long int x = 0;
    	
    	while ( i <= mid && j <= high )
    	{
    		if ( data[i] <= data[j] )       // 此处我们有两种处理：即使用前半个数组或者后半个数组都是可以的，呵呵~
    		{
    			tmp[x++] = data[i++];
    			//all_count += ( high - j + 1 );  // 此处使用前半个数组
    		}
    		else
    		{
    			tmp[x++] = data[j++];
    			all_count += ( mid - i + 1 );	 // 此处使用后半个数组 
    		}
    	}
    	
    	while (i <= mid)	// 下面是收尾工作，呵呵！
    	{                   // 注意下面的；两个while只会执行一个！
    		tmp[x++] = data[i++];
    	}
    	
    	while (j <= high)
    	{
    		tmp[x++] = data[j++];
    	}
    	
    	for ( i = 0; i < x; i++ )  // 再归还给数组data
    	{
    		data[low + i] = tmp[i];
    	}
    }
    
    // 使用分治来处理！
    // 
    void merge( int data[], long int low, long int high )
    {
    	int mid;
    
    	if ( low < high )
    	{
    		mid = (low + high) / 2;
    		merge(data, low, mid);			// 左边一半 
    		merge(data, mid + 1, high);		// 右边一半
    		merge_two(data, low, mid, high);// 合并
    	}
    }
    
    
    int main()
    {
    	int *data;
    	long int n, i;
    
    	while( scanf("%ld", &n) != EOF )
    	{
    		data = ( int* )malloc( sizeof( int ) * n );
    		
    		for( i = 0; i < n; i++ )
    		{
    			scanf("%d", &data[i]);
    		}
    
    		tmp = ( int* )malloc( sizeof( int ) * n );  // 缓冲区
    
    		all_count = 0;
    
    		merge(data, 0, n - 1);      // 处理开始
    
    		printf("%ld\n", all_count);
    		
    		free( data );
    		free( tmp  );
    	}
    
    	return 0;
    }

呵呵，歇一下~

[http_blog.csdn.net_shanshanpt_article_details_8680224]: http://blog.csdn.net/shanshanpt/article/details/8680224
[http_ac.jobdu.com_problem.php_cid_1039_pid_19]: http://ac.jobdu.com/problem.php?cid=1039&pid=19