【摘要】：折半插入排序算法如下：折半插入所需的关键字比较次数与待排序记录序列的初始排列无关，仅仅和记录个数有关。因此，用折半插入排序时，进行的关键字比较次数为：可见，折半插入排序所需的比较次数比线性插入排序的比较次数要少，但两种插入排序所需的辅助空间和记录的移动次数是相同的。因此，折半插入排序的时间复杂度为O。
所谓折半查找，与前面讲的一样，就是在插入R[i]时（此时R[1]，R[2]，…，R[i-1]已排序），取R i/2的关键字k i/2与ki进行比较。如果Ki＜K i/2，R[i]的插入位置只能在R[1]和R i/2之间，则在R[1]和R i/2-1之间继续进行折半查找；如果ki>k i/2，则在R i/2 +1和R[i-1]之间进行折半查找，如此反复，直到最后确定插入位置为止。折半查找的过程是处于有序表中间位置记录的关键字k i/2和ki进行比较的过程，每经过一次比较，便可排除一半记录，把可插入的区间缩小一半，所以称为折半。
设置初始指针low指向有序表的第一个记录，尾指针high指向有序表的最后一个记录，中间指针mid指向有序表中间位置的记录。每次将待插入记录的关键字与mid指向位置记录的关键字进行比较，从而确定待插入记录的插入位置。折半插入排序算法如下：
折半插入所需的关键字比较次数与待排序记录序列的初始排列无关，仅仅和记录个数有关。在插入第i个记录时，要确定插入位置关键字的比较次数。因此，用折半插入排序时，进行的关键字比较次数为：(www.xing528.com)
可见，折半插入排序所需的比较次数比线性插入排序的比较次数要少，但两种插入排序所需的辅助空间和记录的移动次数是相同的。因此，折半插入排序的时间复杂度为O（n2）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
