直接插入排序

直接插入排序：

      将n个元素的数列分为已有序和无序两个部分，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中

      算法适用于少量数据的排序，时间复杂度为O(n^2)，是稳定的排序方法

      
      {{a1}，{a2，a3，a4，…，an}}

      {{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}

      …

      {{a1(n-1），a2(n-1) ，…},{an(n-1)}}

      每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

      第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

public class StraightInsertionSort {

	/**
	 * 辅助函数:输出数组内容
	 * 
	 * @param a：待输出数组
	 */
	public static void printArray(int[] a) {
		for (int index = 0; index < a.length; index++) {
			System.out.print(a[index] + " ");
		}
		System.out.println("");
	}

	/**
	 * 直接插入排序 实现1
	 * 
	 * @param a：待排序数组
	 */
	public static void insertSort(int[] a) {
		// 输出原始数组
		printArray(a);
		for (int index = 1; index < a.length; index++) {

			int subIndex = index;

			// 等待插入的数据
			int currentData = a[index];

			while ((subIndex > 0) && (a[subIndex - 1] > currentData)) {
				a[subIndex] = a[subIndex - 1];
				subIndex--;
			}

			// 插入到合适的位置
			a[subIndex] = currentData;

			// 每次排序后也输出
			printArray(a);
		}
	}

	/**
	 * 直接插入排序 实现2
	 * @param a：待排序数组
	 */
	public static void insertSort2(int[] a) {
		
		int n = a.length;
		int i, j;
		for (i = 0; i < n; i++) {
			int temp = a[i];
			for (j = i; j > 0 && temp < a[j - 1]; j--) {
				a[j] = a[j - 1];
			}
			a[j] = temp;
			
			printArray(a);
		}
	}

	public static void main(String[] args) {
		//insertSort(new int[] { 8, 2, 4, 9, 3, 6, 7, 10 });
		insertSort2(new int[] { 8, 2, 4, 9, 3, 6, 7, 10 });
	}
}