插入排序的准则是在有序序列中插入新的记录以达到扩大有序区的长度的目的一趟直接插入排序的基本思想则是:在对记录序列R[n]的排序过程中区段R[i]中的记录已按关键字非递减的顺序排列将R[i]插入到有序序列R[i]中使区段R[i]中的记录按关键字非递减顺序排列
由此实现一趟插入排序的步骤为
)在R[i]中查找R[i]的插入位置即确定j(≤j＜i)使得R[j]key≤R[i]key＜R[j+i]key
)将R[j+i]中的记录后移一个位置
)将R[i]插入到j+的位置
和顺序查找类似为了避免在查找过程中判别循环变量是否出界设置R[]为监视哨并在查找的同时进行记录后移如下演示所示
