算法导论——插入排序——伪代码和Java实现

第二章第一节：插入排序

    我们首先介绍插入排序。相信大部分人都打过扑克牌，许多人喜欢发一张牌就拿一张牌到手上，并且按顺序来放好牌。开始时我们左手为空，牌在桌子上。然后我们每次从桌子上拿走一张牌并将它插入左手中的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。

伪代码：

INSERTION-SORT(A)			//A是数组
 for j = 2 to A.length
	key = A[j]
	//(将A[j]插入排序序列A[1..j-1])
	i = j - 1
	while i > 0 and A[i] > key
		A[i+1] = A[i]
		i = i - 1
	A[i+1] = key

Java代码实现：

//升序排序
public void InsertSortAscending(int[] A){
		for(int j = 1;j < A.length;j++){
			int key = A[j];
			//将A[j]插入排序序列A[1..j-1]
			int i = j - 1;
			while(i >= 0 && A[i] > key){
				A[j] = A[i];
				i = i - 1;
			}
			A[i+1] = key;
		}
}

    下面我们来看一下插入排序的运行步骤
    用数组A[2,4,7,1,3,6]来举例子
    每次for循环中，黄色的长方形是A[j]的值，在第7行的while循环中将它与其左边的蓝色的长方形中的值进行比较。蓝色的箭头指出数组在第8行向右移动一个位置，黄色的箭头指出第11行关键字被移到的地方。
    第一次循环：如下图所示

    第二次循环：如下图所示

    注意：这里A[2]大于A[1]，因为A[1]肯定是大于A[0]的所以没必要在比较A[2]与A[1]的大小。while循环因不满足条件会退出。

    第三次循环：如下图所示

    第四次循环：如下图所示

    第五次循环：如下图所示

    A数组此时如图所示：

    第六次循环时j为6不满足循环j<A.length条件，循环退出。
‘-----------------------------------------------------------------’
    插入排序的讲解到这里已经结束
    其他算法：[算法导论——各章节算法伪代码和java实现]