学科分类
目录
数据结构

折半插入排序

折半插入排序(binary insertion sort)是对直接插入排序的改进。在直接插入排序中,主要的时间消耗在数据的比较和移动上。那么有没有方法降低数据比较的次数呢?由于前半部分的序列已经有序,在为新数据寻找插入点时,可以采用折半查找的方法来提高寻找速度。

以数组arr[]为例,在将arr[]排列为一个降序序列的过程中,寻找插入点的具体操作是:

(1)分别使用low记录有序序列首位元素下标,high记录有序序列末尾元素下标,tmp记录待插入元素的数据;

(2)若low<=high,将arr[tmp]与arr[m]作比较,其中m=(low+high)/2:

a) 若tmp<arr[m],使low=m+1;

b) 若tmp>=arr[m],使high=m-1;

(3)重复步骤 (2),直到low<=high不成立,此时找到插入点,其下标为high+1。

该过程与查找中的折半查找相同。以图1中的序列为例,演示折半查找的查找过程。其中arr[0]~arr[7]为有序序列,arr[8]~arr[9]为待排序序列。

图1 折半查找

(1)首先使low=0,high=7,则m=(low+high)/2=3,使用tmp记录arr[8],tmp=7;

(2)比较tmp与arr[m],tmp>arr[m]=4成立,使high=4-1=3,则m=(0+3)/2=1;

(3)low<=high成立,再次比较tmp与arr[m]=8,tmp<arr[m],使low=m+1=2;

(4)low<=high依然成立,m=(low+high)/2=2,比较tmp与arr[m],tmp>arr[m],使high=2-1=1;

(5)此时low>high,所以插入点为下标为2的位置。

使用折半查找为本次插入寻找合适的插入点时,共进行了3次比较。若是使用直接插入排序,在本轮排序中,tmp需要依次与arr[7]~arr[0]的数据比较,7次比较过后,才找到合适的插入点。所以折半插入排序有效加快了寻找插入点的效率。但折半查找并非绝对提高寻找插入点的效率,对于一个本身有序的序列,反而直接插入排序效率更高。

折半插入中的核心是插入点的查找,若插入点为k,找到插入点后,将有序序列中插入点之后的数据依次后移一位,将新数据插入下标为k处。

使用折半插入排序的算法实现如下。

//折半插入排序
int BinarySort(int arr[], int n)
{
    int i, j;            //定义控制循环的变量
    int low, high, m;    //定义中间变量
    int tmp;
    for (i = 1; i < n; i++)    
    {
        tmp = arr[i];
        low = 0;
        high = i - 1;
        while (low <= high)    //寻找插入点
        {
            m = (low + high) / 2;
            if (tmp > arr[m])
                high = m - 1;
            else
                low = m + 1;
        }
        //移动有序序列中插入点之后的元素
        for (j = i - 1; j >= high + 1; j--)
            arr[j + 1] = arr[j];
        arr[high + 1] = tmp;    //将待排序数据插入有序序列
    }
}

折半插入排序节省了排序过程中比较的次数,但是移动的次数与直接插入排序相同,所以其时间复杂度仍为O(n2)。分析算法可知,在两个数据关键字相同时,不会交换数据顺序,所以该算法是一个稳定的算法。

点击此处
隐藏目录