java 简单插入排序

/***
 * 简单插入排序算法练习
 * 
 * @author bobo
 * 
 */
public class InsertSort {
	/***
	 * 插入排序的逻辑为：新建一个有序序列，从源数组中挨个挑取数组插入到有序序列的何合适位置
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 1, 0, 3, 4, 2, 3, 5, 3, 6, 8, 2 };
		show(a);
		for (int i = 0; i < a.length-1; i++) {
			insertOne(a, i+1);
			show(a);
		}
		show(a);
	}

	/**
	 * 一次插入的方法
	 * 
	 * @param a
	 *            要被插入的有序序列 为提高算法的空间效率 是源数组
	 * @param i
	 *            要插入的数据的索引
	 */
	private static void insertOne(int[] a, int index) {
		// 待插入的数据的索引为i则a的有序长度应该是index
		// 第一层循环的条件中=是哨兵原则，因为index处的值有可能就放在有序序列的队尾
		for (int i = 0; i <= index; i++) {
			if (a[i] >= a[index]) {// 找到插入位置
				int tmp = a[index];// 缓存数据 防止被覆盖掉
				// 后移i到index-1这些数组的元素，腾出i的位置同时覆盖掉index的位置
				// 后移数组元素应该从后面开始 否则会出现覆盖的情况
				for (int j = index - 1; j >= i; j--) {
					a[j + 1] = a[j];
				}
				a[i] = tmp;
			}
		}
	}

	private static void show(int[] a) {
		for (int i : a) {
			System.out.print(i + "\t");
		}
		System.out.println();
	}
}