常见排序的JAVA实现

还有好多其他排序而且每种排序都有优化，之后会不断添加.

/**
 * 文件名：SortTest.java
 * 时间：2014年11月5日下午6:05:13
 * 作者：修维康
 */
package chapter7;

import java.util.Arrays;

/**
 * 类名：SortTest 说明：各类排序分析详解
 */
public class SortTest {

	/**
	 * 方法名：insertionSort 说明：插入排序 时间复杂度O(N^2)
	 */
	public static <AnyType extends Comparable<? super AnyType>> void insertionSort(
			AnyType[] a) {
		for (int i = 1; i < a.length; i++) {
			AnyType temp = a[i];
			int j = i - 1;
			while (j >= 0 && temp.compareTo(a[j]) < 0) {
				a[j + 1] = a[j];
				j--;
			}
			a[j + 1] = temp;
		}
	}

	/**
	 * 方法名：BInsertSort 说明：二分插入排序 时间复杂度O(N^2) 因为插入排序的前i - 1个元素是排好序的
	 * 所有将第i个元素插入到前面查到元素的时候 可以用二分查找
	 */
	public static <AnyType extends Comparable<? super AnyType>> void BInsertSort(
			AnyType[] a) {
		for (int i = 1; i < a.length; i++) {
			int low = 0;
			AnyType temp = a[i];
			int high = i - 1;
			int position = 0;
			// 二分找不到时 low 的位置是大于key的最小元素，high是小于key的最大元素
			while (low <= high) {
				int mid = (low + high) / 2;
				if (a[mid].compareTo(temp) < 0)
					low = mid + 1;
				else
					high = mid - 1;
			}
			position = high;
			for (int j = i; j > position && j > 0; j--)
				a[j] = a[j - 1];
			a[position + 1] = temp;
		}
	}

	/**
	 * 方法名：shellSort 说明：希尔排序 时间复杂度(N^2) 利用增量序列 对用增量分组得到的序列进行插入排序。
	 */
	public static <AnyType extends Comparable<? super AnyType>> void shellSort(
			AnyType[] a) {
		for (int gap = a.length / 2; gap > 0; gap /= 2) {
			for (int i = 0; i < gap; i++) {
				for (int j = i + gap; j < a.length; j += gap) {
					AnyType temp = a[j];
					if (temp.compareTo(a[j - gap]) < 0) {
						int k = j - gap;
						while (k >= 0 && a[k].compareTo(temp) > 0) {
							a[k + gap] = a[k];
							k -= gap;
						}
						a[k + gap] = temp;
					}
				}
			}
		}
	}

	/**
	 * 方法名：bubbleSort 说明：冒泡排序 时间复杂度O(N^2)
	 */
	public static <AnyType extends Comparable<? super AnyType>> void bubbleSort(
			AnyType[] a) {
		for (int i = 0; i < a.length; i++)
			for (int j = i + 1; j < a.length; j++) {
				if (a[i].compareTo(a[j]) > 0) {
					AnyType temp = a[i];
					a[i] = a[j];
					a[j] = temp;
				}
			}

	}

	/************ 堆排序 ***********************************/

	public static <AnyType extends Comparable<? super AnyType>> void buildHeap(
			AnyType[] array) {

		for (int i = array.length / 2; i >= 0; i--)
			shifDown(array, i, array.length);
	}

	/**
	 * 方法名：shifUp 说明：上滤，其实只用下滤就可以完成建堆，排序
	 */

	public static <AnyType extends Comparable<? super AnyType>> void shifUp(
			AnyType[] array, int valPos) {
		AnyType temp = array[valPos];
		while (valPos > 0 && array[(valPos - 1) / 2].compareTo(temp) < 0) {
			array[valPos] = array[(valPos - 1) / 2];
			valPos = (valPos - 1) / 2;
		}
		array[valPos] = temp;
	}

	/**
	 * 方法名：shifDown 说明：下滤 注意数组越界
	 */
	public static <AnyType extends Comparable<? super AnyType>> void shifDown(
			AnyType[] array, int valPos, int n) {

		AnyType temp = array[valPos];
		while (valPos * 2 + 1 < n) {
			int child = valPos * 2 + 1;// 左儿子
			if (child != n - 1 && array[child].compareTo(array[child + 1]) < 0)
				child++;
			if (temp.compareTo(array[child]) < 0)
				array[valPos] = array[child];
			else
				break;
			valPos = child;
		}
		array[valPos] = temp;

	}

	public static <AnyType extends Comparable<? super AnyType>> void heapSort(
			AnyType[] a) {
		buildHeap(a);
		for (int i = a.length - 1; i > 0; i--) {
			AnyType temp = a[0];
			a[0] = a[i];
			a[i] = temp;
			shifDown(a, 0, i);
		}
	}

	/**
	 * 方法名：mergeSort 说明：归并排序，JAVA中对泛型的排序用该排序，对基本类型的排序用快排
	 * 因为归并排序是比较次数最少的，java中对两个对象的比较 代价是昂贵的
	 */
	public static <AnyType extends Comparable<? super AnyType>> void mergeSort(
			AnyType[] a) {
		AnyType[] tempArray = (AnyType[]) new Comparable[a.length];
		mergeSort(a, tempArray, 0, a.length - 1);
	}

	private static <AnyType extends Comparable<? super AnyType>> void mergeSort(
			AnyType[] a, AnyType[] tempArray, int low, int high) {
		if (low < high) {
			int mid = (low + high) / 2;
			mergeSort(a, tempArray, low, mid);
			mergeSort(a, tempArray, mid + 1, high);
			merge(a, tempArray, low, mid + 1, high);
		}

	}

	private static <AnyType extends Comparable<? super AnyType>> void merge(
			AnyType[] a, AnyType[] tempArray, int lowPos, int highPos,
			int highEnd) {
		int leftEnd = highPos - 1;
		int temPos = lowPos;
		int numElements = highEnd - lowPos + 1;
		while (lowPos <= leftEnd && highPos <= highEnd) {
			if (a[lowPos].compareTo(a[highPos]) <= 0)
				tempArray[temPos++] = a[lowPos++];
			else
				tempArray[temPos++] = a[highPos++];
		}
		while (lowPos <= leftEnd)
			tempArray[temPos++] = a[lowPos++];
		while (highPos <= highEnd)
			tempArray[temPos++] = a[highPos++];
		for (int q = 0; q < numElements; q++, highEnd--)
			a[highEnd] = tempArray[highEnd];

	}

	/**
	 * 方法名：QuickSort 说明：快排
	 */

	public static <AnyType extends Comparable<? super AnyType>> void quickSort(
			AnyType[] a) {
		quickSort(a, 0, a.length - 1);
	}

	private static <AnyType extends Comparable<? super AnyType>> void quickSort(
			AnyType[] a, int low, int high) {
		if (low < high) {
			int keyPos = partition(a, low, high);
			quickSort(a, low, keyPos - 1);
			quickSort(a, keyPos + 1, high);
		}

	}

	private static <AnyType extends Comparable<? super AnyType>> int partition(
			AnyType[] a, int low, int high) {
		AnyType key = a[low];
		while (low < high) {
			while (low < high && a[high].compareTo(key) >= 0)
				high--;
			a[low] = a[high];
			while (low < high && a[low].compareTo(key) <= 0)
				low++;
			a[high] = a[low];
		}
		a[low] = key;
		return low;
	}

	/**
	 * 方法名：selectSort 说明：选择排序O(N^2)的算法
	 */
	public static <AnyType extends Comparable<? super AnyType>> void selectSort(
			AnyType[] a) {
		for (int i = 0; i < a.length; i++) {
			int j = selectMin(a, i);
			if (i != j) {
				AnyType temp = a[j];
				a[j] = a[i];
				a[i] = temp;
			}
		}

	}

	private static <AnyType extends Comparable<? super AnyType>> int selectMin(
			AnyType[] a, int n) {
		AnyType min = a[n];
		int minPos = n;
		;
		for (int i = n + 1; i < a.length; i++)
			if (a[i].compareTo(min) < 0) {
				min = a[i];
				minPos = i;
			}
		return minPos;

	}

	/**
	 * 方法名：main 说明：测试
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Integer[] a = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		Integer[] b = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		Integer[] c = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		Integer[] d = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		Integer[] e = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		Integer[] f = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		Integer[] g = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		insertionSort(a);
		BInsertSort(b);
		shellSort(c);
		selectSort(d);
		heapSort(e);
		quickSort(f);
		mergeSort(g);
		System.out.println(Arrays.toString(a));
		System.out.println(Arrays.toString(b));
		System.out.println(Arrays.toString(c));
		System.out.println(Arrays.toString(d));
		System.out.println(Arrays.toString(e));
		System.out.println(Arrays.toString(f));
		System.out.println(Arrays.toString(g));

	}

}

常见排序的JAVA实现

原文：http://blog.csdn.net/xiuweikang/article/details/40868959