排序【插入排序】

插入排序思想：
    将当前无序序列的首个记录插入到有序序列中，逐个扩充有序序列直至完成排序。
    数组有N个元素，那么要求至多进行N(N-1)/2次比较，时间复杂度O(N*N),空间复杂度O(N).

/**
 * InsertSort.java
 * 
 * 插入排序
 * 
 * @author Administrator
 */

public class InsertSort {

	public static void insertSort(int[] a) {

		for (int i = 1; i < a.length; i++)

			if (a[i] < a[i - 1]) {

				int temp = a[i]; // 复制为哨兵.
				int insertLoc = i; // 要插入的位置

				for (insertLoc = i - 1; temp < a[insertLoc]; insertLoc--) {
					a[insertLoc + 1] = a[insertLoc];
				}

				a[insertLoc + 1] = temp; // 插入到正确的位置.

			}

	}

	public static void main(String[] args) throws Exception {

		if (args.length == 0) {
			System.out.println("请输入数字以空格隔开");
			System.exit(-1);
		}

		int[] a = new int[args.length];

		for (int i = 0; i < args.length; i++)

			a[i] = Integer.parseInt(args[i]);

		insertSort(a);

		// 输出排序后的数组元素。
		for (int i = 0; i < a.length; i++)
			System.out.println(a[i]);

	}
}