Java排序算法之 —— 插入排序

package algorithm.sort;

/**
 * 原理：插入排序使用的是增量方法，每次将一个待排序的数，插入到已经排好序的数组中，
 * 直到所有待排序的数都插入到有序数组中为止（类似于摸牌后整理牌）。
 * @author Administrator
 */
public class InsertSort {

	//按照升序排序
	public void insertSortUp(int[] a) {
		//第一层循环，对待插入的元素进行循环，从第二个元素开始，直到最后一个
		for (int i = 2; i < a.length; i++) {
			int key = a[i];	//待插入的元素
			//第二层循环，对已排序的数组从第一个元素开始循环，找出第一个大于待插入元素的
			int j = i - 1;
			while (j >= 0 && a[j] > key) {
				a[j+1] = a[j];	//从插入点开始的元素都向后移一个位置
				j--;
			}
			a[j+1] = key;		//将待插入元素插到已排序数组中			
		}
	}
	
	/**
	 * 递归插入排序：为排序A[1..n]，先递归排序A[1..n-1]，
	 * 然后再将A[n]插入到已排序的A[1..n-1]中去
	 * @param a：待排序的数组
	 * @param n：待插入的元素序号
	 */
	public void recursiveInsertSort(int[] a, int n) {
		if(n > 0) {
			recursiveInsertSort(a, n-1);
			//将待插入元素插入已排序数组中
			for (; n > 0 && a[n-1] > a[n]; n--) {
				int temp = a[n-1];
				a[n-1] = a[n];
				a[n] = temp;				
			}
		}
	}
	
	//打印数组
	public void printArr(String str, int[] a) {
		System.out.print(str + "\t");
		for(int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}
	
	public static void main(String[] args) {
		InsertSort is = new InsertSort();
		
		int[] a = {2,2,6,8,3,4};
		is.printArr("排序前：", a);
		is.insertSortUp(a);
		is.printArr("排序后：", a);
		
		int[] b = {4,8,0,2,5,1};
		is.printArr("排序前：", b);
		is.recursiveInsertSort(b, b.length-1);
		is.printArr("排序前：", b);
	}

}