quicksort.java

快速排序！ 经典的算法。 provides methods to sort a set of objects with quicksort algorithm.

/*******************************************************************************
quick sort
File name       : QuickSort.java
Author          : Edward Li 
Creation        : 07/27/2004
*******************************************************************************/


import java.lang.String;

/**
 * QuickSort provides methods to sort a set of objects.
 * 
 * @version 1.0  07/27/2004
 * @author  Edward Li 
 */
public final class QuickSort {
	/**
	 * A convienence method for sorting strings
	 */
	public static void sort(Object a[]) {
		if (a == null || a.length == 0) {
			return;
		}

        quicksort(a, 0, a.length - 1, new DefaultCompare());
	}

 	/**
	 * Generalized sort executive, call this to compare anything
	 * just provide the comparer interface.
	 */
	public static void sort(Object a[], Compare comparer) {
		if (a == null || a.length == 0) {
			return;
		}

      	quicksort(a, 0, a.length - 1, comparer);
	}

	/**
	 * This sort program uses the quicksort algorithm,
	 * see just about any Computer book on the subject
	 * of sorting algorithms, Knuth. 
	 */
	private static void quicksort(
		Object a[], int left, int right, Compare c) {
		if (left >= right) {	/* do nothing if array contains */
			return;				/* fewer than two elements */
		}

		int i;
		int last;
		
		// TBD: can choose the middlest one among a[left], a[right] 
		// 	and a[(left + right)/2] as the partition element
		//if (c.compareTo(a[left], a[right] < 0) {
		//	if (c.compareTo(a[left], a[(left + right)/2]) < 0) {
		//		if (c.compareTo(a[right], a[(left + right)/2]) < 0) {
		//			last = right;
		//		} else {
		//			last = (left + right)/2;
		//		}
		//	} else {
		//		last = left;
		//	}
		//} else {
		//	if (c.compareTo(a[left], a[(left + right)/2]) > 0) {
		//		if (c.compareTo(a[right], a[(left + right)/2]) > 0) {
		//			last = right;
		//		} else {
		//			last = (left + right)/2;
		//		}
		//	} else {
		//		last = left;
		//	}
		//}
		//swap(a, left, last);				/* move partition elem to a[0] */
		
		swap(a, left, (left + right)/2);	/* move partition elem to a[0] */
		last = left;
		for (i = left + 1; i <= right; i++) {	/* partition */
			if (c.compareTo(a[i], a[left]) < 0) {
				swap(a, ++last, i);
			}
		}

		swap(a, left, last);	/* restore partition element */
		quicksort(a, left, last - 1, c);
		quicksort(a, last + 1, right, c);
	}

	/**
	 * swap two elements in an array.
	 */
	private static void swap(Object a[], int i, int j) {
		Object temp;
		
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

class DefaultCompare implements Compare {
    
    /**
     * String Comparison routine, uses the comapreTo in the
     * String class.
     */
    public int compareTo(Object a, Object b) {
        String sa = (String)a;
        String sb = (String)b;
        
        return sa.compareTo(sb);
    }    
}