1、直接插入排序 很设在排序过程中,前四个记录已按关键字递增的次序,重 新排列,构成一个含4个记录的有序序列: ●{38,49,65,97} (93) ●现要将第5个(关键字为76)的记录插入上述序列,可以得 到一个新的含5个记录的有序序列,则首先要找到插入的位 置,然后进行插入。 ●假设从R(97)起向左进行顺序查找,由于65≤76≤97,则 R(76)应插入在R(65)和R(97)之间,从而得到下列新 的有序序列: {R(38),R(49),R(65),R(76),R(97)}(9.4) ●称从式(93)到式(94)的过程为一趟直接插入排序。 北京邮电大学自动化学院北京邮电大学自动化学院 5 1、直接插入排序 ⚫ 假设在排序过程中，前四个记录已按关键字递增的次序，重 新排列，构成一个含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）} (9.4) ⚫ 称从式（9.3）到式（9.4）的过程为一趟直接插入排序。 ⚫ {38，49，65，97} (9.3)