插入排序---直接插入排序

基本思想
第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。

演示网址：http://www.yxqzzx.cn/teacher/ShowArticle.asp?ArticleID=417
举例说明：

待排序数组R[7,3,4,1,5,8]

第1趟排序：
3 | 7  3  4  1  5  8
3 | 7  7  4  1  5  8
3 | 3  7  4  1  5  8

第2趟排序：
4 | 3  7  4  1  5  8
4 | 3  7  7  1  5  8
4 | 3  4  7  1  5  8


第3趟排序：
1 | 3  4  7  1  5  8
1 | 3  4  7  7  5  8
1 | 3  4  4  7  5  8
1 | 3  3  4  7  5  8
1 | 1  3  4  7  5  8


第4趟排序：
5 | 1  3  4  7  5  8
5 | 1  3  4  7  7  8
5 | 1  3  4  5  7  8
第4趟排序：
R[i-1]<R[i]不需要排序。

从上面的步骤可以看出，直接插入排序的过程为：从数组第一个元素开始，两两相邻的元素进行比较，找出其中的小的元素作为哨兵，并记录位置j，然后从位置j开始，j--到数组起始位置，进行数据交换。

	/**
	 * 直接插入排序
	 * 
	 * @param unsorted
	 */
	public static void insertion_sort(int[] unsorted) {
		for (int i = 1; i < unsorted.length; i++) {
			if (unsorted[i - 1] > unsorted[i]) {
				int temp = unsorted[i];
				int j = i;
				while (j > 0 && unsorted[j - 1] > temp) {
					unsorted[j] = unsorted[j - 1];
					j--;
				}
				unsorted[j] = temp;
			}
		}
	}