插入排序

插入排序
插入排序
需要从给的数组的第二个数既是下标为1的位置开始，和前一个数比较，如果比前一个数小就和他交换位置，如果不比它小就进行下一个位置。
在简单排序（冒泡、选择、插入）中是最优的，因为她比冒泡排序比较和交换的次数少，而且对于基本有序的数组来说，插入排序只需要比较一半的元素就可以完成排序，效率比较高。

这个是每一躺插入排序的过程
// 9 3 1 4 6 8 7 5 2
// 3 9 1 4 6 8 7 5 2
// 3 1 9 4 6 8 7 5 2
// 1 3 9 4 6 8 7 5 2
// 1 3 4 9 6 8 7 5 2
// 1 3 4 6 9 8 7 5 2
// 1 3 4 6 8 9 7 5 2
// 1 3 4 6 8 7 9 5 2
// 1 3 4 6 7 8 9 5 2
// 1 3 4 6 7 8 5 9 2
// 1 3 4 6 7 5 8 9 2
// 1 3 4 6 5 7 8 9 2
// 1 3 4 5 6 7 8 9 2
// 1 3 4 5 6 7 8 2 9
// 1 3 4 5 6 7 2 8 9
// 1 3 4 5 6 2 7 8 9
// 1 3 4 5 2 6 7 8 9
// 1 3 4 2 5 6 7 8 9
// 1 3 2 4 5 6 7 8 9
// 1 2 3 4 5 6 7 8 9

public class InstertionSort {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根

		int[] a = {9,3,1,4,6,8,7,5,2};
		sort(a);
		print(a);
	}
	static void sort(int []a) {
		for(int  i =1;i<a.length;i++) {
			for(int j = i;j>0;j--) {
				if(a[j] <a[j-1]) {
					swap(a,j,j-1);
				}
			}
		}
	}
	static void swap(int []a,int i,int j) {
		int  temp  = a[i];
		a[i]= a[j];
		a[j] = temp;
	}
	static void print(int[] arr ) {
		for(int i = 0;i < arr.length;i++) {
			System.out.print(arr[i]);
		}
		
	}

}