[插入排序]-java实现插入排序

排序思想：将n个待排序的元素看成一个有序表和一个无序表，开始时，有序表中只有一个元素，无序表中有n-1个元素，排序时，每次从无序表中取出第一个元素，把它依次与有序表中元素进行比较，将它插入到有序表中的适当位置，使之最后成为一个有序表。
编程思想：一般初始有序表就是arr[0]，循环遍历设置待插入的数arr[i] 和它想插入的位置 i-1。
时间复杂度：O(n²)

public int[] insertSort(int [] arr){
	for(int i=1; i < arr.length ; i++){
		int insertVal = arr[i];	//待插入的值为arr[i]
		int insertIndex = i -1; // 待插入的位置，插到有序表前一位
		
		// 待插入的值想一直往前插，要确保大于有序表中数据，且不能越过0
		while( insertInde >=0 && insertvalue < arr[insertIndex]){
			//一旦条件成立，有序表中元素后移，待插入的地方继续向前找
			arr[inserIndex+1] = arr[insertIndex];
			insertIndex --;
		}
		//一但跳出循环，说明已经找到了待插入的索引,不好想的话就想是插到末尾。索引得1+1
		arr[insertIndex+1] = insertVal;
	}
	return arr;
}