【时间效率】 确定插入位置所进行的折半查找,关键码的比 较次数至多为log2(mn+1)次,移动记录的次数和 直接插入排序相同,故时间复杂度仍为0()是 个稳定的排序方法。 102.3表插入排序 直接插入排序、折半插入排序均要大量移动记 录,时间开销大。若要不移动记录完成排序,需要 改变存储结构,进行表插入排序。所谓表插入排序, 就是通过链接指针,按关键码的大小,实现从小到 大的链接过程,为此需增设一个指针项。操作方法 与直接插入排序类似,所不同的是直接插入排序要 移动记录,而表插入排序是修改链接指针。用静态 链表来说明。【时间效率】 确定插入位置所进行的折半查找，关键码的比 较次数至多为 ，次，移动记录的次数和 直接插入排序相同，故时间复杂度仍为O(n2 )。是一 个稳定的排序方法。 10.2.3表插入排序 直接插入排序、折半插入排序均要大量移动记 录，时间开销大。若要不移动记录完成排序，需要 改变存储结构，进行表插入排序。所谓表插入排序， 就是通过链接指针，按关键码的大小，实现从小到 大的链接过程，为此需增设一个指针项。操作方法 与直接插入排序类似，所不同的是直接插入排序要 移动记录，而表插入排序是修改链接指针。用静态 链表来说明。 log 2 (n +1) 