假设在排序过程中,前四个记录已按关键字递增的次序,重
新排列,构成一个含 4 个记录的有序序列 :
现要将第 5 个(关键字为 76 )的记录插入上述序列,可以得
到一个新的含 5 个记录的有序序列,则首先要找到插入的位
置,然后进行插入。
假设从 R ( 97 )起向左进行顺序查找,由于 65 76
97 ,则 R ( 76 )应插入在 R ( 65 )和 R ( 97 )之间,
从而得到下列新的有序序列 :
{R ( 38 ), R ( 49 ), R ( 65 ), R ( 76 ), R ( 97
) } ( 2 )
称从式( 1 )到式( 2 )的过程为一趟直接插入排序。
{38 , 49 , 65 , 97} ( 1 )
第 3 页 / 共 72 页