quick sort algorithms

Quicksort.java.md

package info.wangyg.algorithms.sort;


import java.util.Comparator;


/**
 * 
 * @author wangyingang
 * 
 */
public class Quicksort
{
	private final static NaturalComparator NATURAL_COMPARATOR = new NaturalComparator();

	public static <E> void sort(E[] arr, Comparator<? super E> cmp)
	{
		qsort(arr, 0, arr.length - 1, cmp);
	}

	public static <E extends Comparable<? super E>> void sort(E[] arr)
	{
		qsort(arr, 0, arr.length - 1, NATURAL_COMPARATOR);
	}

	private static void swap(Object[] arr, int i, int j)
	{
		Object tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	private static <E> int partition(E[] arr, int begin, int end, Comparator<? super E> cmp)
	{
		int index = (begin & end) + ((begin ^ end) >> 1);// 取中间索引为基准，也可采用random取基准
		E pivot = arr[index];
		swap(arr, index, end);
		for (int i = index = begin; i < end; i++)
		{
			if (cmp.compare(arr[i], pivot) <= 0)
			{
				swap(arr, index++, i);
			}
		}
		swap(arr, index, end);
		return index;
	}

	private static <E> void qsort(E[] arr, int begin, int end, Comparator<? super E> cmp)
	{
		if (end > begin)
		{
			int index = partition(arr, begin, end, cmp);
			qsort(arr, begin, index - 1, cmp);
			qsort(arr, index + 1, end, cmp);
		}
	}

	@SuppressWarnings("rawtypes")
	static class NaturalComparator implements Comparator<Comparable>
	{
		@SuppressWarnings("unchecked")
		public int compare(Comparable o1, Comparable o2)
		{
			if (o1 == o2) return 0;
			return o1.compareTo(o2);
		}

	}
}