线性插入排序的基本思想是:第1遍,将 初始文件中的记录R1看作有序子文件, 将R2插入这个子文件中。若R2的关键 字小于R1的关键字,则R2插在R1的前 面,否则R2插在R1的后面。第2遍, 将R3插入前面的两个记录的有序子文 件中,得到3个记录的有序子文件。 依此类推,继续进行下去,直到将Rn 插入到前面的n1个记录的有序子文 件中,最后得到n个记录的有序文件 KO K1 K2 K3 K4 K5 图9-1所示为线性插入排序的例子。 初始关键字 15 为了避免检测是否应插在R1的前面,在 R1的前面设立记录R0,它既是中间变 第一遍排序后:21(2143)89154328 量,又是监视哨。设(R1,R2, R1)是已排序的有序子文件,则插 第二遍排序后:89(214389)154328 入R的步骤是:首先将R存放到 然后将Ko(即原R的关键字Ki)依 第三遍排序后:15(152143 次与K1,K2,…比较,若K。K 1,i-2 则R后移 第四遍排序后:43(15214343 个位置,否则停止比较和移动;最后 将R。(即原来待插入的记录R1)移到 j+1的位置上。由于R的前面有监视 第五遍排序后:28(1521284343 哨R,因此不必每次判断下标j是否 出界。算法描述如下线性插入排序的基本思想是：第1遍，将 初始文件中的记录R1看作有序子文件， 将R2插入这个子文件中。若R2的关键 字小于R1的关键字，则R2插在R1的前 面，否则R2插在R1的后面。第2遍， 将R3插入前面的两个记录的有序子文 件中，得到3个记录的有序子文件。 依此类推，继续进行下去，直到将Rn 插入到前面的n-1个记录的有序子文 件中，最后得到n个记录的有序文件。 图9-1所示为线性插入排序的例子。 为了避免检测是否应插在R1的前面，在 R1的前面设立记录R0，它既是中间变 量，又是监视哨。设（R1，R2，…， Ri-1）是已排序的有序子文件，则插 入Ri的步骤是：首先将Ri存放到Ro中， 然后将Ko（即原Ri的关键字Ki）依 次与Ki-1，Ki-2，…比较，若Ko<Kj （j=i-1，i-2，…，1），则Rj后移一 个位置，否则停止比较和移动；最后， 将Ro（即原来待插入的记录Ri）移到 j+1的位置上。由于Ri的前面有监视 哨Ro，因此不必每次判断下标j是否 出界。算法描述如下：