2、其它插入排序 ●(1)折半插入排序 ●由于插入排序的基本操作是在一个有序表中进行查找和插 入,则从上章的讨论可知,这个“查找”操作可利用“折半 查找”来实现,由此进行的插入排序称之为折半插入排序。 ●直接插入排序的基本操作是向有序表中插入一个记录,平均情况 下总比较次数约为n214。既然是在有序表中确定插入位置,可以 不断二分有序表来确定插入位置,通过待插入记录与有序表居中 的记录按关键码比较,将有序表一分为二,下次比较在其中一个 有序子表中进行,这样继续下去,直到要比较的子表中只有一个 记录时,比较一次便确定了插入位置。 北京邮电大学自动化学院北京邮电大学自动化学院 9 2、其它插入排序 ⚫ （1）折半插入排序 ⚫ 由于插入排序的基本操作是在一个有序表中进行查找和插 入，则从上章的讨论可知，这个“查找”操作可利用“折半 查找”来实现，由此进行的插入排序称之为折半插入排序。 ⚫ 直接插入排序的基本操作是向有序表中插入一个记录，平均情况 下总比较次数约为n 2 /4。既然是在有序表中确定插入位置，可以 不断二分有序表来确定插入位置，通过待插入记录与有序表居中 的记录按关键码比较，将有序表一分为二，下次比较在其中一个 有序子表中进行，这样继续下去，直到要比较的子表中只有一个 记录时，比较一次便确定了插入位置