/* * Copyright (C) 2000-2007 Wang Pengcheng <wpc0000@gmail.com> * Licensed to the Wang Pengcheng under one or more * contributor license agreements.  See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The LGPL licenses this file to You under the GNU Lesser General Public * Licence, Version 2.0  (the "License"); you may not use this file except in * compliance with the License.  You may obtain a copy of the License at * *     http://www.gnu.org/licenses/lgpl.txt * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */package cn.edu.whu.iss.algorithm.unit02;import mypackage.tools.print.P;public class Inversion {		private static int tot;		/**	 *InsertionSort	 *The time limit of this sort is O(n^2)	 *<strong>O(n^2)</strong>	 *@param  element will be sorted	 */	private static <Type extends Comparable> void insertionSort(Type element[]){		for(int j=1;j<element.length;j++){			Type	key	=	element[j];			int i	=	j-1;						while( (i>=0)&&(element[i].compareTo(key)>0)){				element[i+1]	=	element[i];				tot++;				i--;			}			element[i+1]	=	key;		}	}	/**	 *Merge used in the mergeSort	 *<strong>O(n)</strong>	 *@param element Type[] the elements to be merged	 *@param p int the begin of the  first elements	 *@param q int the end of the first elements	 *@param r int the end of the second elements	 */	private static <Type extends Comparable> void merge(Type element[],int p,int q,int r){		int nl	=	q-p+1;		int nr	=	r-q;				Type[] lElement,rElement;		lElement	=	(Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nl);		rElement	=	(Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nr);						for(int i=0;i<nl;i++){			lElement[i]	=	element[p+i];		}		for(int i=0;i<nr;i++){			rElement[i]	=	element[q+i+1];		}				int i=0,j=0;		int k	=	p;		while((i<nl)&&(j<nr)){			if(lElement[i].compareTo(rElement[j])<=0){				element[k]	=	lElement[i];				i++;			}else{				element[k]	=	rElement[j];				j++;				tot+=nl-i;			}			k++;		}				while(i<nl){			element[k]	=	lElement[i];			i++;			k++;		}		while(j<nr){			element[k]	=	rElement[j];			j++;			k++;		}	}		/**	 *mergeSort	 *Sort the elements by the compareTo method	 *<strong>O(nlgn)</strong>	 *@param  element Type[] that will be sorted	 *@param p the begin of the list will be sorted	 *@param r the end of the list will be sorted	 */	private static <Type extends Comparable> void mergeSort(Type element[],int p,int r){		if(p<r){			int q	=	(p+r)/2;			mergeSort(element,p,q);			mergeSort(element,q+1,r);			merge(element,p,q,r);		}	}	private static <Type extends Comparable> void mergeSort(Type element[]){		mergeSort(element,0,element.length-1);	}		/**	 * Count the inversion number by O(nlgn)	 * @param <Type> inversion number type	 * @param element inversion number list	 * @return count number of inversion	 */	public static <Type extends Comparable>  int countMerge(Type element[]){		tot=0;		mergeSort(element.clone());		return tot;	}	/**	 * Count the inversion number by O(n^2)	 * @param <Type> inversion number type	 * @param element inversion number list	 * @return count number of inversion	 */	public static <Type extends Comparable> int countInsertion(Type element[]){		tot=0;		insertionSort(element.clone());		return tot;	}	/**	 * @param args	 */	public static void main(String[] args) {		// TODO Auto-generated method stub		Integer[] a = {4,6,5,1,3,2,7};		P.rintln(Inversion.countInsertion(a));		P.rintln(Inversion.countMerge(a));		//System.out.println(Inversion.countMerge(a));	}}