#include <iostream>
using namespace std; 

long Unsort[500010] , done[500010] ;
long count ;


void Merge( long left , long mid , long right )
{
	long i = left , j = mid+1 , k = left ;
	while (  i <= mid &&  j <= right )
	{
		if ( Unsort[i] > Unsort[j]  )
		{  done[k++] = Unsort[j++] ; }
		else
		{
			done[k++] = Unsort[i++] ;
		}
	}
	if ( i > mid )
		for ( long q = j ; q <= right ; q ++  )
			done[k++] = Unsort[q] ;
	else
		for ( long q = i ; q <= mid ; q ++ )
			done[k++] = Unsort[q] ;
	for ( long m = mid+1 ;m <= right ; m ++ )
	for ( long  n = mid ; n >= left ; n -- )
			if ( Unsort[m] < Unsort[n] )
				count ++ ;
}

void Copy( long left , long right )
{
	for ( long i = left ; i <= right ; i ++ )
		Unsort[i] = done[i] ;
}

void Megersort( long left , long right )
{
	if ( left < right )
	{
		long i = (left+right)/2 ;
		Megersort( left , i ) ;
		Megersort(  i+1 , right ) ;
		Merge( left , i , right ) ;
		Copy( left , right ) ;
	}
}

int main()
{
	long n ;
	while ( cin >> n , n )
	{
		count = 0 ;
		for ( long i = 0 ; i < n ; i ++ )
			cin >> Unsort[i] ;
		Megersort( 0 , n-1 ) ;
		cout << count <<endl ;
	}
	
	return 0 ;
}

• 哪位用非递归归并AC了的发代码给我学习一下好吗？？？? (0) Isun 2008-03-16 20:31:14