10.21折半插入排序 直接插入排序的基本操作是向有序表中插入 个记录,插入位置的确定通过对有序表中记录按关 键码逐个比较得到的。平均情况下总比较次数约为 n24。既然是在有序表中确定插入位置,可以不断二 分有序表来确定插入位置,即一次比较,通过待插 入记录与有序表居中的记录按关键码比较,将有序 表一分为二,下次比较在其中一个有序子表中进行, 将子表又一分为二。这样继续下去,直到要比较的 子表中只有一个记录时,比较一次便确定了插入位10.2.1 折半插入排序 直接插入排序的基本操作是向有序表中插入一 个记录，插入位置的确定通过对有序表中记录按关 键码逐个比较得到的。平均情况下总比较次数约为 n 2 /4。既然是在有序表中确定插入位置，可以不断二 分有序表来确定插入位置，即一次比较，通过待插 入记录与有序表居中的记录按关键码比较，将有序 表一分为二，下次比较在其中一个有序子表中进行， 将子表又一分为二。这样继续下去，直到要比较的 子表中只有一个记录时，比较一次便确定了插入位 置