Java实现插入排序

原理：把n个待排序的元素，看成一个有序表和一个无序表。开始时，有序表中仅包含一个元素，无序表中包含n - 1个元素，排序时，每次从无序表中取出第一个元素，把它和有序表中的值依次进行比较，将它插入到合适的位置，使之成为一个新的有序表。

public class InsertionSort {
	public void sort(int[] nums) {
		int insertVal = 0; //定义待插入值，因为是局部变量，因此要手动赋值
		int insertIndex = 0; //定义待插入位置，因为是局部变量，因此要手动赋值
		//为什么这是i从1开始而不是0？因为默认第一个元素为有序表中的，所以从第二个元素开始
		for(int i = 1; i < nums.length; i++) {
			insertVal = nums[i]; //默认待插入值为无序表中第一个元素
			insertIndex = i - 1; //默认待插入的位置为无序表第一个元素前面的那个元素，即有序表最后一个元素

			
			while(insertIndex >= 0 && insertVal < nums[insertIndex]) {
				nums[insertIndex + 1] = nums[insertIndex];
				insertIndex--;
			}
			//当退出while循环后，说明此时已经找到了待插入的位置
			if(insertIndex + 1 != i) {
				nums[insertIndex + 1] = insertVal;
			}
		}
		//for循环结束说明排序结束了
		System.out.println(Arrays.toString(nums));
	}
}