[数据结构]二分插入排序

二分插入排序是对二分查找和插入排序的一个结合，插入操作时通过二分查找找到要插入的位置.

#include <stdio.h>
// 打印数组a
void printArr(int a[],int n){
    for (int i = 0; i < n; ++i)
    {
        printf("%d\t",a[i]);
    }
    printf("\n");
}

void ModInsertSort(int a[],int n){
    int i,j,temp,left,right,mid;

    for ( i = 1; i < n; ++i)
    {
      left=0;
      temp=a[i];
      right=i-1; 
      while(left<=right){
        mid=(left+right)/2;
        if(a[mid]>temp){
            right=mid-1;
         }else{
           left=mid+1;
         }
      }
      for ( j = i-1; j >right;j--)
        a[j+1]=a[j];

      a[right+1]=temp;
    }
}

int main(){
    int a1[]={10,111,22,31,14,57,46,89,39};
    ModInsertSort(a1,9);
    printArr(a1,9);
}
输出结果：
yaopans-MacBook-Pro:algorithm yaopan$ ./a.out 
10  14  22  31  39  46  57  89  111

JAVA描述

public class BinInserSort {

    //二分插入排序

    public static void ModInsertSort(int a[]){
        int i,j,right,left,mid,temp;
        for (i =1; i < a.length; ++i) {
            temp=a[i];
            left=0;
            right=i-1;
            while(left<=right){
                 mid=(left+right)/2;
                 if(a[mid]>temp){
                     right=mid-1;
                 }else{
                     left=mid+1;
                 }
            }

            for(j=i-1;j>right;j--){
                a[j+1]=a[j];
            }
            a[right+1]=temp;
        }
    }
    public static void printArry(int[] a){
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+"\t");
        }
        System.out.println("\n");
    }
    public static void main(String[] args) {
        int a[]={1,2,34,24,5,6,7,8,77,90,37,19,20};
        System.out.println("排序前:");
        printArry(a);
        ModInsertSort(a);
        System.out.println("排序后:");
        printArry(a);

    }
}
排序前:
1   2   34  24  5   6   7   8   77  90  37  19  20  

排序后:
1   2   5   6   7   8   19  20  24  34  37  77  90