插入排序

插入排序 Insertion Sort

插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]騆[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。
　　简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序，折半插入排序留到“查找”内容中进行。
　　图1演示了对4个元素进行直接插入排序的过程，共需要(a),(b),(c)三次插入。

图1 对4个元素进行插入排序

在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。所以，我们设元素的类型ElementType中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定L[i]是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将L[i]放入L[0]中，这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。

/**
 * 插入排序
 * 
 * @author 吖大哥
 * @date Jun 16, 2014 9:31:55 AM
 */
public class InsertSort {

	public static void main(String[] args) {
		int[] arr = { 12, 1, 2, 454, 23, 56 };
		InsertSort.doInsertSort2(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "\t");
		}
	}

	/**
	 * 插入排序(WHILE循环实现)
	 * 
	 * @paramsrc待排序数组
	 */
	public static void doInsertSort1(int[] src) {
		int len = src.length;
		for (int i = 1; i < len; i++) {
			int temp = src[i];
			int j = i;

			while (src[j - 1] > temp) {
				src[j] = src[j - 1];
				j--;
				if (j <= 0) {
					break;
				}
			}
			src[j] = temp;
		}
	}

	/**
	 * 插入排序(FOR循环实现)
	 * 
	 * @paramsrc待排序数组
	 */
	public static void doInsertSort2(int[] src) {
		int len = src.length;
		for (int i = 1; i < len; i++) {
			int j;
			int temp = src[i];
			for (j = i; j > 0; j--) {
				if (src[j - 1] > temp) {
					src[j] = src[j - 1];

				} else {
					// 因为前面已经是排好了序的，所以直接通出当前一轮的比较
					break;
				}
			}
			src[j] = temp;
		}
	}
}