10.2插入排序 算法基本思想 将待排序的记录插入到已排序的子文件中去,使得插入之后 得到的子文件仍然是有序子文件。插入一个记录,首先要对有序 子文件进行査找,以确定这个记录的插入位置。按查找方式的不 同,插入排序又可以分为线性插入排序和折半插入排序,前者使 用顺序查找,后者使用折半査找。 1.直接插入排序(线性插入排序) 设待排序的文件为(r[1],r[2],,r[n]) 关键字为(r[1].key,r[2].key,,r[n].key) 首先,将初始文件中的记录r[1]看作有序子文件; 第1遍:将r[2]插入有序子文件中:若r[2].key<r[1].key 则r[2]插在r[1]之前;否则,插在r[1的后面。 第2遍:将记录r[3]插入前面已有2个记录的有序子文件中, 得到3个记录的有序子文件 以此类推,依次插入r[4],.,r[n],最后得到n个记录的递 增有序文件。10.2 插入排序 算法基本思想 将待排序的记录插入到已排序的子文件中去，使得插入之后 得到的子文件仍然是有序子文件。插入一个记录，首先要对有序 子文件进行查找，以确定这个记录的插入位置。按查找方式的不 同，插入排序又可以分为线性插入排序和折半插入排序，前者使 用顺序查找，后者使用折半查找。 1.直接插入排序(线性插入排序) 设待排序的文件为(r[1],r[2],...,r[n]) 关键字为(r[1].key,r[2].key,...,r[n].key) 首先,将初始文件中的记录r[1]看作有序子文件； 第1遍：将r[2]插入有序子文件中：若r[2].key<r[1].key， 则r[2]插在r[1]之前；否则，插在r[1]的后面。 第2遍：将记录r[3]插入前面已有2个记录的有序子文件中， 得到3个记录的有序子文件。 以此类推，依次插入r[4],...,r[n],最后得到n个记录的递 增有序文件