二分插入排序（折半插入排序）

二分插入排序（又称折半插入排序），与直接插入法的区别是在有序数列中检索插入位置时采用二分法进行搜索

#include <stdlib.h>

#include <stdio.h>

#define SWAP(x,y,t) t=x;x=y;y=t;

void print(int arr[],int n) {

    for (int i = 0; i <n; i++) {

        printf("%6d", arr[i]);

    }

    printf("n");

}

int binarySearch(int arr[],int value,int begin,int end){

    if(end<=begin){//搜索结束，返回指定位置

        return (value>=arr[begin]?(begin+1):begin);

    }

    int mid=(begin+end)/2;

    if(arr[mid]==value){

        return mid+1;

    }

    if(value<arr[mid]){

        return binarySearch(arr,value,begin,mid-1);  //前半部分搜索

    }

    return binarySearch(arr,value,mid+1,end);//后半部分搜索

}

void binaryInsertSort(int arr[],int n){

    int j,loc;

    for(int i=1;i<n;i++){

        int tmp=arr[i];//记录要插入的值

        j=i-1;

        loc=binarySearch(arr,tmp,0,j);

        for(;j>=loc;j--){//指定位置后移

            arr[j+1]=arr[j];

        }

        arr[j+1]=tmp;//将数据插入到合适位置

        printf_s("%d  %d  n",tmp,loc);

        print(arr,n);

    }

    print(arr,n);

}

int main(){

    int a[]= { 2,5,3,0,2,3,0,-1,5,6,-2,4,5};

    binaryInsertSort(a,sizeof(a)/sizeof(int));

    return 0;

}

最后

以上就是碧蓝皮卡丘为你收集整理的二分插入排序（折半插入排序）的全部内容，希望文章能够帮你解决二分插入排序（折半插入排序）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。