常用排序算法小结

离开课堂后，排序算法写的比较少了，当有排序的要求时，一般用的比较多的是直接采用Arrays.sort以及Collections.sort结合比较器来实现。

Arrays工具类包含了对各种类型数组的排序，以下是Arrays中包括的sort方法：


以下是Collections中的sort方法，该sort方法中结合了Arrays.sort来实现的。

/**
     * Sorts the specified list into ascending order, according to the
     * <i>natural ordering</i> of its elements.  All elements in the list must
     * implement the <tt>Comparable</tt> interface.  Furthermore, all elements
     * in the list must be <i>mutually comparable</i> (that is,
     * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
     * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
     *
     * This sort is guaranteed to be <i>stable</i>:  equal elements will
     * not be reordered as a result of the sort.<p>
     *
     * The specified list must be modifiable, but need not be resizable.<p>
     *
     * The sorting algorithm is a modified mergesort (in which the merge is
     * omitted if the highest element in the low sublist is less than the
     * lowest element in the high sublist).  This algorithm offers guaranteed
     * n log(n) performance. 
     *
     * This implementation dumps the specified list into an array, sorts
     * the array, and iterates over the list resetting each element
     * from the corresponding position in the array.  This avoids the
     * n<sup>2</sup> log(n) performance that would result from attempting
     * to sort a linked list in place.
     *
     * @param  list the list to be sorted.
     * @throws ClassCastException if the list contains elements that are not
     *	       <i>mutually comparable</i> (for example, strings and integers).
     * @throws UnsupportedOperationException if the specified list's
     *	       list-iterator does not support the <tt>set</tt> operation.
     * @see Comparable
     */
    public static <T extends Comparable<? super T>> void sort(List<T> list) {
	Object[] a = list.toArray();
	Arrays.sort(a);
	ListIterator<T> i = list.listIterator();
	for (int j=0; j<a.length; j++) {
	    i.next();
	    i.set((T)a[j]);
	}
    }

    /**
     * Sorts the specified list according to the order induced by the
     * specified comparator.  All elements in the list must be <i>mutually
     * comparable</i> using the specified comparator (that is,
     * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
     * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
     *
     * This sort is guaranteed to be <i>stable</i>:  equal elements will
     * not be reordered as a result of the sort.<p>
     *
     * The sorting algorithm is a modified mergesort (in which the merge is
     * omitted if the highest element in the low sublist is less than the
     * lowest element in the high sublist).  This algorithm offers guaranteed
     * n log(n) performance. 
     *
     * The specified list must be modifiable, but need not be resizable.
     * This implementation dumps the specified list into an array, sorts
     * the array, and iterates over the list resetting each element
     * from the corresponding position in the array.  This avoids the
     * n<sup>2</sup> log(n) performance that would result from attempting
     * to sort a linked list in place.
     *
     * @param  list the list to be sorted.
     * @param  c the comparator to determine the order of the list.  A
     *        <tt>null</tt> value indicates that the elements' <i>natural
     *        ordering</i> should be used.
     * @throws ClassCastException if the list contains elements that are not
     *	       <i>mutually comparable</i> using the specified comparator.
     * @throws UnsupportedOperationException if the specified list's
     *	       list-iterator does not support the <tt>set</tt> operation.
     * @see Comparator
     */
    public static <T> void sort(List<T> list, Comparator<? super T> c) {
	Object[] a = list.toArray();
	Arrays.sort(a, (Comparator)c);
	ListIterator i = list.listIterator();
	for (int j=0; j<a.length; j++) {
	    i.next();
	    i.set(a[j]);
	}
}

本文将用JAVA实现七个常用排序，包括：冒泡排序，插入排序，选择排序，希尔排序，快速排序，归并排序和堆排序。


代码类图如下：


一个抽象类BsseSort中包含了排序用到的一些公共操作，比如比较等。

package my.sort;

public abstract class BaseSort<T> {

	@SuppressWarnings("hiding")
	protected abstract <T extends Comparable<T>> void sort(T[] array);

	@SuppressWarnings({ "hiding" })
	protected <T extends Comparable<T>> boolean lessThan(T t1, T t2) {
		return t1.compareTo(t2) < 0;
	}

	@SuppressWarnings({ "hiding" })
	protected <T extends Comparable<T>> boolean greatThan(T t1, T t2) {
		return t1.compareTo(t2) > 0;
	}

	@SuppressWarnings("hiding")
	protected <T extends Comparable<T>> boolean equalTo(T t1, T t2) {
		return t1.compareTo(t2) == 0;
	}

	@SuppressWarnings("hiding")
	protected <T extends Comparable<T>> void swap(T[] array, int i, int j) {
		T t = array[i];
		array[i] = array[j];
		array[j] = t;
	}

	@SuppressWarnings("hiding")
	protected <T extends Comparable<T>> void printArray(T[] array) {
		for (T t : array) {
			System.out.print(t);
			System.out.print(" ");
		}
		System.out.println();
	}

}

冒泡排序

package my.sort;

public class BubbleSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		int length = array.length;
		for (int i = 0; i < length; i++) {
			for (int j = 1; j < length - i; j++) {
				if (greatThan(array[j - 1], array[j])) {
					swap(array, j - 1, j);
				}
			}
		}
	}
}

插入排序

package my.sort;

public class InsertionSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		int length = array.length;
		for (int i = 1; i < length; i++) {
			for (int j = i; j > 0 && lessThan(array[j], array[j - 1]); j--) {
				swap(array, j, j - 1);
			}
		}
	}
}

选择排序

package my.sort;

public class SelectionSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		int length = array.length;
		for (int i = 0; i < length; i++) {
			int min = i;
			for (int j = i + 1; j < length; j++) {
				if (lessThan(array[j], array[min])) {
					min = j;
				}
			}
			swap(array, i, min);
		}
	}

}

希尔排序

package my.sort;

public class ShellSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		int length = array.length;
		int h = 1;
		while (h < length / 3) {
			h = 3 * h + 1;
		}
		while (h >= 1) {
			for (int i = h; i < length; i++) {
				for (int j = i; j >= h && lessThan(array[j], array[j - h]); j -= h) {
					swap(array, j, j - h);
				}
			}
			h /= 3;
		}

	}

}

快速排序

package my.sort;

public class QuickSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		sort(array, 0, array.length - 1);
	}

	@SuppressWarnings("hiding")
	private <T extends Comparable<T>> void sort(T[] array, int low, int high) {
		if (high <= low)
			return;
		int j = partition(array, low, high);
		sort(array, low, j - 1);
		sort(array, j + 1, high);
	}

	@SuppressWarnings("hiding")
	private <T extends Comparable<T>> int partition(T[] array, int low, int high) {
		int i = low;
		int j = high + 1;

		T v = array[low];

		while (true) {
			while (lessThan(array[++i], v)) {
				if (i == high)
					break;
			}

			while (lessThan(v, array[--j])) {
				if (j == low)
					break;
			}

			if (i >= j)
				break;

			swap(array, i, j);
		}

		swap(array, low, j);

		return j;

	}
}

归并排序

package my.sort;

/**
 * 自顶向下的归并排序
 * 
 * @author Eric
 * @param <T>
 */
public class MergeSort<T> extends BaseSort<T> {

	@SuppressWarnings("unchecked")
	private Comparable[] aux = null; // 归并所需的辅助数组

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {
		int length = array.length;
		aux = new Comparable[length];
		doSort(array, 0, length - 1);

	}

	@SuppressWarnings("hiding")
	private <T extends Comparable<T>> void doSort(T[] array, int low, int high) {
		if (low < high) {

			// 找出中间索引
			int mid = low + (high - low) / 2;

			// 对左边数组进行递归
			doSort(array, low, mid);

			// 对右边数组进行递归
			doSort(array, mid + 1, high);

			// 合并
			doMerge(array, low, mid, high);
		}

	}

	@SuppressWarnings( { "hiding", "unchecked" })
	private <T extends Comparable<T>> void doMerge(T[] array, int low, int mid,
			int high) {
		// 将array[low...mid]和[mid+1...high]归并
		int i = low;
		int j = mid + 1;

		/* 将array[low...high]复制到aux[low...high] */
		for (int k = low; k <= high; k++) {
			aux[k] = array[k];
		}

		for (int k = low; k <= high; k++) {
			if (i > mid) {
				array[k] = (T) aux[j++];
			} else if (j > high) {
				array[k] = (T) aux[i++];
			} else if (lessThan(aux[j], aux[i])) {
				array[k] = (T) aux[j++];
			} else {
				array[k] = (T) aux[i++];
			}
		}
	}

/*	public static void main(String[] args) {

		String[] array = { "Hello", "World", "Eric", "Allen" };
		MergeSort<String> sort = new MergeSort<String>();
		sort.printArray(array);
		sort.sort(array);
		sort.printArray(array);
	}*/

}

堆排序

package my.sort;

public class HeapSort<T> extends BaseSort<T> {

	@SuppressWarnings("hiding")
	@Override
	protected <T extends Comparable<T>> void sort(T[] array) {

		int length = array.length;

		buildHeap(array, length);

		while (length > 1) {
			length--;
			swap(array, 0, length);
			downHeap(array, length, 0);
		}

	}

	@SuppressWarnings("hiding")
	private <T extends Comparable<T>> void buildHeap(T[] array, int length) {
		for (int v = length / 2 - 1; v >= 0; v--) {
			downHeap(array, length, v);
		}
	}

	@SuppressWarnings("hiding")
	private <T extends Comparable<T>> void downHeap(T[] array, int length, int v) {

		int w = 2 * v + 1;
		while (w < length) {

			if ((w + 1 < length) && greatThan(array[w + 1], array[w])) {
				w++;
			}

			if (!lessThan(array[v], array[w])) {
				return;
			}
			swap(array, v, w);
			v = w;
			w = 2 * v + 1;

		}
	}

}

测试代码比如：   

  public static void main(String[] args) {

	 String[] array = { "Hello", "World", "Eric", "Allen" };
	 HeapSort<String> sort = new HeapSort<String>();
	 sort.printArray(array);
	 sort.sort(array);
	 sort.printArray(array);
     }

下面是几个算法的一些比较。