【基本思想】
在直接插入排序中,每趟插入过程都进行了两项工作:
- 从有序子表中查找待插入元素应被插入位置
- 给插入位置腾出空间,将待插入元素复制到表中插入位置
可以看出,上述过程总是边比较边移动元素,针对这一过程,进行改进,即将比较与移动分离,先查找出元素的待插入位置,再统一的移动待插入位置后的所有元素
由于有序区是顺序表,因此可以采用折半查找来寻找插入位置
【性能分析】
折半插入排序仅适用于顺序存储方式,是在直接插入排序的基础上进行的改进,其仍是一种稳定排序算法
在排序过程中,仅需一个辅助空间,作为待插入记录的暂存单元,因此空间复杂度为:
由于折半查找的过程减少了元素的比较次数,该比较次数与待排序表的状态无关,仅与 $n$ 的大小有关,故而查找的时间复杂度为 $O(nlog_2n)$,但元素的移动次数没有改变,为 $O(n^2)$,因此,折半插入排序的时间复杂度仍为:
虽然折半插入排序与直接插入排序的时间复杂度相同,但对于数据量不大的情况,折半插入排序往往能表现出较好的性能
【实现】
1 | void insertBinarySort(int a[], int n) { |