排序_直接插入排序

import java.util.*;
/**
 * 直接插入排序
 * 原理参考：http://www.cnblogs.com/kkun/archive/2011/11/23/2260265.html
 * 我的理解是输入一组数
 * 第一步给前两个数排序
 * 第二步给前三个数排序
 * 以此类推
 * 因此每次第i个数准备插入时，前0~i-1个数均已有序
 * @author zz
 *
 */
public class InsertSortion {
	public static void sort(int[] a){
		int temp, j;
		for(int i = 1; i < a.length; i++) {	 //索引是从1开始 	
			temp = a[i];
			j = i;
			while(j > 0 && temp < a[j-1]) { //若a[i] < a[i-1],则 比a[i]大的均后移一位
	    		a[j] = a[j-1];
	    		j--;
	    	}
	    	a[j] = temp;   //在合适位置保存a[i]
	    	System.out.println(Arrays.toString(a));
	    }
	}
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
        System.out.println("请输入数组元素的个数n: ");
        int n = input.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
        	a[i] = input.nextInt();
        }
        sort(a);
	}
}