> 	//计算逆序数
> 	private static int solve(int[] array,int n) {
> 		int[] temp = new int[n];			
> 		return mergeSort(array,temp,0,n);
> 	}
> 	// 包括low,不包括high.
> 	private static int mergeSort(int[] src, int[] dest, int low, int high) {		
> 		int length = high - low;		
> 		if (length==1) return 0;		
> 		int mid = (low + high) >> 1;
> 		int c1 = mergeSort(src, dest, low, mid);
> 		int c2 = mergeSort(src, dest, mid, high);
> 		if (src[mid-1]<=src[mid]) {			
> 			return c1+c2;
> 		}
> 		int c3 = 0;		
> 		int i=low, p = low, q = mid;
> 		while(p<mid&&q<high) {
> 			if (src[p]<=src[q]) {
> 				dest[i++] = src[p++];
> 				c3 += (q-mid); 
> 			}				
> 			else {
> 				dest[i++] = src[q++];	
> 				//c3 += (mid-p); 
> 			}
> 		}
> 		while(p<mid) {
> 			dest[i++] = src[p++];
> 			c3 += (q-mid); 			
> 		}
> 		while(q<high) {
> 			dest[i++] = src[q++];			
> 		}
> 		System.arraycopy(dest, low, src, low, length);
> 		
> 		return c1+c2+c3;
> 	}

• Re:int64 (54) liuyuyangfoam 2005-12-24 01:31:05
  • Re:int64 (63) lastone 2006-07-25 12:02:53