数据结构与算法——第10章-排序-折半插入排序算法(10.2)

发表于 2023-06-02 分类于开发， N-数据与算法，数据结构与算法阅读时长 ≈ 1 分钟

一概述

1 2	1.折半插入排序算法 2.示例代码

二折半插入排序算法

1
2
3

上一节介绍了直接插入排序算法的理论实现和具体的代码实现，
如果你善于思考就会发现该算法在查找插入位置时，采用的是顺序查找的方式，
而在查找表中数据本身有序的前提下，可以使用折半查找来代替顺序查找，这种排序的算法就是折半插入排序算法。

三示例代码

3.1 该算法的具体代码实现为

#include <stdio.h>
void print(int a[], int n ,int i){
    printf("%d:",i);
    for(int j=0; j<n; 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;
}

4.2 运行结果为

4.3 时间复杂度

1
2

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

五参考

C语言中文网—折半插入排序算法（C语言代码实现）

0%