inversion.java

<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关 2. 数据结构 2.1 基本数据结构 2.2 散列表 2.3 二叉查找树 2.4 红黑树 2.5 数据结构

/*
 * Copyright (C) 2000-2007 Wang Pengcheng <[e-mail]>
 * 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));
	}

}