fastqsortalgorithm.java

自己写的search engine, 有 boolean search, fuzzy search

package searchingEngine.utilites.sorting;

import java.util.LinkedList;

import searchingEngine.dataPreprocessing.rawData.PostNode;

/*
 * @(#)QSortAlgorithm.java	1.3   29 Feb 1996 James Gosling
 *
 * Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved.
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and
 * without fee is hereby granted. 
 * Please refer to the file http://www.javasoft.com/copy_trademarks.html
 * for further important copyright and trademark information and to
 * http://www.javasoft.com/licensing.html for further important
 * licensing information for the Java (tm) Technology.
 * 
 * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 * 
 * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
 * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
 * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
 * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
 * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
 * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
 * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES").  SUN
 * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
 * HIGH RISK ACTIVITIES.
 */

/**
 * A quick sort demonstration algorithm
 * SortAlgorithm.java
 *
 * @author James Gosling
 * @author Kevin A. Smith
 * @version 	@(#)QSortAlgorithm.java	1.3, 29 Feb 1996
 * extended with TriMedian and InsertionSort by Denis Ahrens
 * with all the tips from Robert Sedgewick (Algorithms in C++).
 * It uses TriMedian and InsertionSort for lists shorts than 4.
 * <[e-mail]>
 */
public class FastQSortAlgorithm
{
	/** This is a generic version of C.A.R Hoare's Quick Sort 
	* algorithm.  This will handle arrays that are already
	* sorted, and arrays with duplicate keys.<BR>
	*
	* If you think of a one dimensional array as going from
	* the lowest index on the left to the highest index on the right
	* then the parameters to this function are lowest index or
	* left and highest index or right.  The first time you call
	* this function it will be with the parameters 0, a.length - 1.
	*
	* @param a	   an integer array
	* @param lo0	 left boundary of array partition
	* @param hi0	 right boundary of array partition
	*/
	private void QuickSort(LinkedList<PostNode> a, int l, int r) throws Exception
   {
	int M = 4;
	int i;
	int j;
	PostNode v;

	if ((r-l)>M)
	{
		i = (r+l)/2;
		if (a.get(l).compareTo(a.get(i))>0) swap(a,l,i);	// Tri-Median Methode!
		if (a.get(l).compareTo(a.get(r))>0) swap(a,l,r);
		if (a.get(i).compareTo(a.get(r))>0) swap(a,i,r);

		j = r-1;
		swap(a,i,j);
		i = l;
		v = a.get(j);
		for(;;)
		{
			while(a.get(++i).compareTo(v)<0);
			while(a.get(--j).compareTo(v)>0);
			if (j<i) break;
			swap (a,i,j);
		}
		swap(a,i,r-1);
		QuickSort(a,l,j);
		QuickSort(a,i+1,r);
	}
}

	private void swap(LinkedList<PostNode> a, int i, int j)
	{
		PostNode T;
		T = a.get(i); 
		a.set(i,a.get(j));
		a.set(j,T);
	}

	private void InsertionSort(LinkedList<PostNode> a, int lo0, int hi0) throws Exception
	{
		int i;
		int j;
		PostNode v;

		for (i=lo0+1;i<=hi0;i++)
		{
			v = a.get(i);
			j=i;
			while ((j>lo0) && (a.get(j-1).compareTo(v)>0))
			{
				a.set(j,a.get(j-1));
				j--;
			}
			a.set(j,v);
	 	}
	}

	public void sort(LinkedList<PostNode> a) throws Exception
	{
		QuickSort(a, 0, a.size() - 1);
		InsertionSort(a,0,a.size()-1);
	}
}