折半插入排序算法（二分插入排序）&C语言代码

折半插入排序的基本思想是：顺序地把待排序的序列中的各个元素按其关键字的大小，通过折半查找插入到已排序的序列的适当位置。

二分（折半）插入（Binary insert sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。

但是，在查找二分点的时间上的时间损耗，导致了这个算法并不能比直接插入排序优秀多少，除非你有十分确切的数据大小和随机访问迭代器。

折半插入排序算法相比较于直接插入排序算法，只是减少了关键字间的比较次数，而记录的移动次数没有进行优化，所以该算法的时间复杂度仍是 O(n2)

折半插入排序算法

与直接插入算法的区别在于：在有序表中寻找待排序数据的正确位置时，使用了折半查找/二分查找。

temp表示当前判断的数字（将要插入的数）。low初次指向有序表第一个数，根据判断条件a[mid]<temp 使low=mid+1，最终停止寻找，low表示插入的位置，mid表示（low + high / 2）初次比较的数字，不符合条件向前或向后依次比较。high指向有序表最后一个数。根据判断条件a[mid]>temp使high=mid-1。注意：low <= high

示例数组为：{3,1,7,5,2,4,9,6}

开始

i从第二个元素开始。mid开始指向第一个下标0。比较 3 > 1 ，high=0-1=-1，low > high跳出循环。low位置0插入元素1。元素3向后移动。

比较7

此时mid指向下标0的数字1，1 < 7， low=0+1=1，low = high，mid = 1 + 1 /2 = 1，mid此时指向3。3 < 7 。low=1+1=2 low > high跳出循环。此时low=2，插入数字7。所以不做交换。

比较5

mid此时指向数字3，3 < 5 ，low=1+1=2，low = high ，mid = 2 + 2 /2 = 2 此时mid指向7， 7 > 5 ，high=2-1=1，low > high。此时low为2，插入5, 有序表中插入位置后面的元素向后移动。

比较2

mid指向数字3，3 > 2 ,high=1-1=0 ，low = high，mid = 0 + 0 /2 = 0, 此时mid指向元素1。1 < 2, low=0+1=1, low > high 跳出循环。此时low的位置指向1插入元素2，其后有序表元素依次后移。

后续

插入数字4

插入数字9

插入数字6

折半插入排序算法C代码

#include <stdio.h>
void print(int a[], int n ,int i){
    printf("%d:",i);
    for(int j=0; j<8; j++){
        printf("%d",a[j]);
    }
    printf("\n");
}
void BInsertSort(int a[],int size){
    int i,j,low = 0,high = 0,mid;
    int temp = 0;
    for (i=1; i<size; i++) {
        low=0;
        high=i-1;
        temp=a[i];
        //采用折半查找法判断插入位置，最终变量 low 表示插入位置
        while (low<=high) {
            mid=(low+high)/2;
            if (a[mid]>temp) {
                high=mid-1;
            }else{
                low=mid+1;
            }
        }
        //有序表中插入位置后的元素统一后移
        for (j=i; j>low; j--) {
            a[j]=a[j-1];
        }
        a[low]=temp;//插入元素
        print(a, 8, i);
    }
   
}
int main(){
    int a[8] = {3,1,7,5,2,4,9,6};
    BInsertSort(a, 8);
    return 0;
}

运行结果

1:13752496
2:13752496
3:13572496
4:12357496
5:12345796
6:12345796
7:12345679

版权属于：ic翼

本文链接：https://bingyishow.top/algorithm/86.html

您必须遵守 署名-非商业性使用-相同方式共享 CC BY-NC-SA 使用这篇文章