直接插入排序算法（JAVA版）

时间复杂度：O(n*n) 直接插入排序：遍历第二个到最后一个，找到每一个值的最佳位置，插进去：）
1.a[i]和前一个值a[i-1]比较，如果小于前一个值
2.设此值为temp，把a[i-1]向后移一位a[i]=a[i-1]
3.检查前面的a[<=i-2]是否有比temp大的，如果比temp大，后移一位
4.直到一个比temp小的或者j=-1，此时把temp赋值到j+1即可 举例子：
原序列：8 4 5 3
第一次 4 8 5 3
第二次 5<8，所以temp = 5, 序列变成 4 8 8 3,然后和i-2=0前面的4比较大小，5>4，所以5应该在1的位置上，把temp赋值到1位置上，4 5 8 3
第三次 3<8，所以temp = 3, 序列变成 4 5 8 8,然后和i-2=2前面的5比较大小，3>5，序列变成 4 5 5 8,再比较3>4，序列变成 4 4 5 8，此时j=-1，那temp肯定在0位上，最终序列3 4 5 8

public class Paixu {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = {8,4,5,3};
		int[] insertSorta = new Paixu().insertSort(a);
		pw(insertSorta);
	}

	/*
http://fatkun.com
直接插入排序：遍历第二个到最后一个，找到每一个值的最佳位置，插入进去
1.a[i]和前一个值a[i-1]比较，如果小于前一个值
2.设此值为temp，把a[i-1]向后移一位a[i]=a[i-1]
3.检查前面的a[<=i-2]是否有比temp大的，如果比temp大，后移一位
4.直到一个比temp小的或者j=-1，此时把temp赋值到j+1即可

初始序列：8 4 5 3
4 8 5 3
4 5 8 3
3 4 5 8
	 */
	int[] insertSort(int[] arr) {
		int temp;
		for (int i = 1; i < arr.length; i++) {
			pw(arr);
			if (arr[i] < arr[i - 1]) {//如果当前值小于前一个
				temp = arr[i]; //设定岗哨
				arr[i] = arr[i - 1]; //把前一个值移到后一位

				//继续和前面的进行比较，如果比temp大，则后移一位
				//这里j从前两个开始，因为前一个知道必定比temp大了，无需再比较
				int j = i - 2;
				while (j>=0 && temp < arr[j]){
					arr[j + 1] = arr[j];
					j--;
				}
				//上一个循环结束后，j在最后一个比temp小的位置或者-1，所以j+1，把当前值放在这里
				arr[j + 1] = temp;
			}
		}
		return arr;
	}

	//打印数组
	private static void pw(int[] arr){
		for (int i : arr)
		System.out.print(i+" ");
		System.out.println("");
	}

}

简化一些，去掉一些注释，代码基本一样

int[] insertSort(int[] arr) {
		int temp;
		for (int i = 1; i < arr.length; i++) {
			pw(arr);
			if (arr[i] < arr[i - 1]) {
				temp = arr[i];
				//这里和前面不太一样，从i的前一个就开始比较，也就是判断前面所有元素（多判断了一次arr[i]和arr[i-1]）
				int j = i - 1;
				while (j>=0 && temp < arr[j]){
					arr[j + 1] = arr[j];
					j--;
				}
				arr[j + 1] = temp;
			}
		}
		return arr;
	}