1、直接插入排序 般情况下,第j趟直接插入排序的操作为: 在含有i-1个记录的有序子序列r1.-1中插入一个记录r[ 后,变成含有个记录的有序子序序列r1. ●并且,和顺序查找类似,为了在查找插入位置的过程中避 免数组下标出界,在r[0处设置监视哨。 在自-1起往前搜索的过程中,可以同时后移记录。 整个排序过程为进行n-1趟插入,即:先将序列中的第一个记 录看成是一个有序序列的子序,然后从第2个记录起逐个进行 插入直至整个序列变成按关键字非递减有序序列为止。 北京邮电大学自动化学院北京邮电大学自动化学院 6 ⚫ 一般情况下，第i趟直接插入排序的操作为： ⚫ 在含有i-1个记录的有序子序列r[1…i-1]中插入一个记录r[i] 后，变成含有i个记录的有序子序序列r[1…i]； ⚫ 并且，和顺序查找类似，为了在查找插入位置的过程中避 免数组下标出界，在r[0]处设置监视哨。 ⚫ 整个排序过程为进行n-1趟插入，即：先将序列中的第一个记 录看成是一个有序序列的子序，然后从第2个记录起逐个进行 插入直至整个序列变成按关键字非递减有序序列为止。 ⚫ 在自i-1起往前搜索的过程中，可以同时后移记录。 1、直接插入排序