为什么算法容易忘记之插入排序

在学习常用的排序算法时，常有这样的感觉，一看就懂，过眼就忘。原因在于没有将排序的基本思想与代码中各个循环控制变量的意义联系起来进行理解记忆。

插入排序

首先，我们要建立这样一个观念，排序无非就是有N个元素无序地放在N个位置上，排序的目的就是使这N个元素按一定的顺序放置在这N个位置上。基本的思路有两个，第一是给每个位置找到合适的元素并将该元素放置到该位置上，N个位置都放置好正确的元素后，排序完成。第二是给每个元素找到正确的位置并将该元素放置到该位置上，N个元素都找到属于自己的位置时，排序完成。这对理解各种排序算法中的循环控制变量的意义很有帮助。插入排序属于第二种。

基本思想

逐个元素给它们安排位置，只是安排位置的方式比较特别。首先，第一个位置上的元素就放在第一个位置上不动。第2个位置上的元素和它前面位置上的第1个元素比较，根据比较结果，调整第2个元素的位置，使前两个位置上的元素是有序的。第3个位置上的元素与前两个位置上的元素比较，根据比较结果调整第3个元素的位置，使前三个位置上的元素是有序的，然后依次是第4,5,6...个位置上的元素，一直到第N个位置上的元素找到自己的位置时，N个位置上的元素已经“各得其所”，排序完成。

从思想到代码

根据上述思想，我们首先给所有的位置从0到N-1编号。下面我们一步一步分析，按照上面的思想我们需要哪些变量，首先我们需要一个循环控制变量指示要调整位置的元素所在的位置，由于第一个元素不用调整，所以该变量应从1到N-1，将其命名为indexOfElmentToInsert。

然后我们需要一个变量暂存该元素的值，因为待会可能将别的元素安排到它目前所在的位置，这样可以防止丢失它的值，命名该变量为valueOfElementToInsert(简称insert)，然后我们还需要一个循环控制变量用来指示insert元素应当放置的位置的序号，当然，这需要进行一定的比较后才能最终确定，根据上面的思想，该变量的值应该是在indexOfElmentToInsert-1到0之间，命名该变量为indexOfElementToCompare，该位置上的元素命名为valueOfElementToCompare(简称compare)，比较的方法是如果compare比insert大，那就将valueOfElementToCompare挪到它下一个位置上，然后将indexOfElementToCompare往前挪一下(也就是减1),同时相应调整valueOfElementToCompare的值。

如果compare小于insert，说明再往前的所有元素都将小于insert，因此insert应当放置在indexOfElementToCompare+1的位置上，而该位置上的元素已经被往后挪了，我们可以放心地将insert放在这里。到此完成了一个元素的位置查找过程。所有元素都进行完一个这样的过程后，排序结束。

为什么不直接上代码

通过以上的叙述，主要是想让大家都能明白代码中的那些变量是用来做什么的，为什么需要这些变量。明白后，我们再看代码中的这些变量，就可以从感性上升到理性，自然也就很容易理解这些变量的边界值，因为排序的思想就隐含在这些变量之中。

代码在此

`insertion-sort(A)
//A代表待排序的数组
for indexOfElmentToInsert=1 to N-1
{
indexOfElmentToCompare = indexOfElmentToInsert - 1;
while(indexOfElmentToCompare>=0 && valueOfElmentToCompare>valueOfElmentToInsert)
{
A[indexOfElmentToCompare+1] = valueOfElmentToCompare;
indexOfElmentToCompare--;
}
A[indexOfElmentToCompare+1] = valueOfElmentToInsert;
}`

注：希尔排序实质上是一种分组插入排序算法，它需要一个变量叫gap，其值范围一般为[N/2]到1，感兴趣的可以查找资料，按本文的思路进行理解记忆。