选择排序

	/**
	 * 选择排序
	 * @author zzk
	 *
	 */
	public class Selection {
		
		public static void sort(Comparable[] a) {
			int N = a.length;
			for(int i = 0; i < N; i++) {
				int min = i;
				//循环查找最小的值
				for(int j = i+1; j < N; j++) {
					if(a[i].compareTo(a[j]) > 0) {
						min = j;
					}
				}
				//交换位置
				Comparable t = a[i];
				a[i] = a[min];
				a[min] = t;
			}
		}
	}

插入排序

	/**
	 * 插入排序
	 * @author zzk
	 *
	 */
	public class Insertion {
		
		/**
		 * 每一次与前面的元素进行比较，如果小于就进行交换
		 */
		public static void sort(Comparable[] a) {
			int N = a.length;
			Comparable t;
			for(int i = 0; i < N; i++) {
				for(int j = i; j > 0 && a[j].compareTo(a[j-1]) > 0; j--) {
					t = a[j];
					a[j] = a[j-1];
					a[j-1] = a[j];
				}
				
			}
		}
		/**
		 * 对sort()的进行改进，对于较大的元素向右移动，不进行交换操作
		 * 每一次进行a[i]与最前面的元素进行比较，如果找到大于a[i]的元素向右移动，
		 * 直到找到小于或者等于a[i]的元素停止
		 */
		public static void sort2(Comparable[] a) {
			int N = a.length;
			Comparable t ;
			int j;
			for(int i = 0; i < N; i++) {
				t = a[i];
				for(j = i; j > 0 && t.compareTo(a[j-1]) < 0; j--) {
					a[j] = a[j-1];
				}
				a[j] = t;
			}
		}
	}

希尔排序

	/**
	 * 希尔排序
	 * @author zzk
	 *
	 */
	public class Shell {
		public static void sort(Comparable[] a) {
			int N = a.length;
			int h = 1;
			Comparable t;
			while( h < N/3 ) {
				h = 3*h + 1;
			}
			while( h >= 1) {
				for(int i = h; i < N; i++) {
					for(int j = i; j > 0 && a[j].compareTo(a[j-h]) < 0; j-=h) {
						t = a[j-h];
						a[j-h] = a[j];
						a[j] = t;
					}
				}
				h = h / 3;
			}
		}
	}

归并排序

	/**
	 * 归并排序
	 * 自顶向下的归并排序
	 * @author zzk
	 *
	 */
	public class Merge {
		
		private static Comparable[] aux;
		
		public static void sort(Comparable[] a) {
			aux = new Comparable[a.length];
		}
		
		private static void sort(Comparable[] a, int lo, int hi) {
			if(hi <= lo) {
				return;
			}
			int mid = lo + ( hi - lo ) / 2;
			sort(a, lo, mid);
			sort(a, mid+1, lo);
			merge(a, lo, mid, hi);
		}
		
		private static void merge(Comparable[] a, int lo, int mid, int hi) {
			int i = lo, j = mid + 1;
			for(int k = lo; k <= hi; k++) {
				aux[k] = a[k];
			}
			for(int k = lo; k <= hi; k++) {
				//如果i > mid，
				//a[lo]到a[mid]之间的元素整理好了
				//对于a[lo]到a[mid]之间的元素完全大于a[mid]与a[hi]之间的元素
				//那么接下来整理a[mid]与a[hi]之间的元素
				if(i > mid) {
					a[k] = aux[j++];
				}else if(j > hi) {
					a[k] = aux[i++];
				}
				//进行比较，a[lo]与a[mid]比较
				//a[j] < a[i]
				else if(aux[j].compareTo(a[i]) < 0){
					a[k] = aux[j++];
				}
				//a[j] > a[i]
				else {
					a[k] = aux[i++];
				}
			}
		}
	}


	/**
	 * 归并排序
	 * 自底向上
	 * @author zzk
	 *
	 */
	public class MergeBU {
		
		private static Comparable[] aux;	//归并所需的辅助数组
		
		public static void sort(Comparable[] a) {
			int N = a.length;
			aux = new Comparable[N];
			for(int sz = 1; sz < N; sz = sz + sz) {
				for(int lo = 10; lo < N-sz; lo += sz + sz) {
					merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
				}
			}
		}
		//原地归并
		private static void merge(Comparable[] a, int lo, int mid, int hi) {
			int i = lo, j = mid + 1;
			for(int k = lo; k <= hi; k++) {
				aux[k] = a[k];
			}
			for(int k = lo; k <= hi; k++) {
				//如果i > mid，
				//a[lo]到a[mid]之间的元素整理好了
				//对于a[lo]到a[mid]之间的元素完全大于a[mid]与a[hi]之间的元素
				//那么接下来整理a[mid]与a[hi]之间的元素
				if(i > mid) {
					a[k] = aux[j++];
				}else if(j > hi) {
					a[k] = aux[i++];
				}
				//进行比较，a[lo]与a[mid]比较
				//a[j] < a[i]
				else if(aux[j].compareTo(a[i]) < 0){
					a[k] = aux[j++];
				}
				//a[j] > a[i]
				else {
					a[k] = aux[i++];
				}
			}
		}
	}

快速排序

	/**
	 * 快速排序
	 * @author zzk
	 *
	 */
	@SuppressWarnings({"unchecked","rawtypes"})
	public class Quick {
		public static void sort(Comparable[] a) {
			sort(a, 0, a.length - 1);
		}
		
		public static void sort(Comparable[] a, int lo, int hi) {
			if(hi <= lo) {
				return;
			}
			int j = partition(a, lo, hi);
			//对左边进行排序
			sort(a, lo, j-1);
			//对右边进行排序
			sort(a, j+1, hi);
		}
		/*
		 * 切分
		 */
		private static int partition(Comparable[] a, int lo, int hi) {
			int i = lo, j = hi + 1;
			Comparable v = a[lo];
			Comparable t;
			while(true) {
				while(a[++i].compareTo(v) < 0) {
					if(i == hi) {
						break;
					}
				} 
				while(v.compareTo(a[--j]) < 0) {
					if(j == lo) {
						break;
					}
				}
				if(i >= j) {
					break;
				}
				t = a[i];
				a[i] = a[j];
				a[j] = t;
			}
			t = a[lo];
			a[lo] = a[j];
			a[j] = t;
			System.out.println("最终：");
			show(a);
			return j;
		}
		
		public static void main(String[] args) {
			Comparable[] a = new Comparable[]
					{11,0,3,2,12,14,20,2,3};
					//{3,2,1,8,9,10,0,1,3,1};
			Quick.sort(a);
		}
		
		public static void show(Comparable[] a) {
			System.out.println("show:");
			for(int i=0; i < a.length; i++) {
				System.out.print(a[i] + "   ");
			}
			System.out.println();
		}
	}

优先队列

	/**
	 * 基于堆的优先队列
	 * @author zzk
	 */
	public class MaxPQ< Key extends Comparable<Key>> {
		
		private Key[] pq;
		
		private int N = 0;
		
		public MaxPQ(int maxN) {
			pq = (Key[]) new Comparable[maxN+1];
		}
		
		public boolean isEmpty() {
			return N == 0;
		}
		
		public int size() {
			return N;
		}
		
		public void insert(Key v) {
			pq[++N] = v;
			swim(N);
		}
		/**
		 * 删除最大值
		 * @return
		 */
		public Key delMax() {
			Key max = pq[1];		//从根节点得到最大元素
			exch(1, N--);			//将其和最后一个节点交换
			pq[N+1] = null;			//防止对象游离
			sink(1);				//恢复堆的有序性
			return max;
		}
		/**
		 * 判断pq[i]是否小于pq[j]
		 * @param i
		 * @param j
		 * @return
		 */
		private boolean less(int i, int j) {
			return pq[i].compareTo(pq[j]) < 0;
		}
		/*
		 * 交换
		 */
		private void exch(int i, int j) {
			Key t = pq[i];
			pq[i] = pq[j];
			pq[j] = t;
		}
		/**
		 * 由下至上的堆有序化（上浮的实现）
		 * 为了插入元素，在堆的最后面进行插入，然后进行上浮操作
		 * @param k
		 */
		private void swim(int k) {
			while(k > 1 && less(k/2, k)){
				exch(k/2, k);
				k = k/2;
			}
		}
		/**
		 * 由上到下的堆有序化（下沉）
		 * 为了删除操作，删除的元素跟最后一个元素进行交换，然后进行下沉操作
		 * @param k
		 */
		private void sink(int k) {
			while(2*k <= N) {
				int j = 2 * k;
				if(j < N && less(j, j + 1)) {
					j++;
				}
				if(!less(k, j)) {
					break;
				}
				exch(k, j);
				k = j;
			}
		}
	}

各种排序算法的性能特点

算法	是否稳定	时间复杂度	空间复杂度
选择排序	否	N^2	1
插入排序	是	N ~ N^2	1
希尔排序	否	NlogN？ N^(6/5)?	1
快速排序	否	NlogN	lgN
归并排序	是	NlogN	N
堆归并	否	NlogN	1