折半插入排序思路总结以及算法性能分析

（一）前言：

考研时间不多了，一些算法就算当时看懂了记住了，之后以往的速度还是很快。决定以后每次懂了之后，回寝室后用代码给实现下，顺便记录下自己的思路，也便于之后自己遗忘的时候拿出来温习。

（二）思路：

我的理解吧，折半插入排序，其实就是直接插入排序的升级版（关于直接插入排序，你可以参考我的另一篇文章：https://www.jianshu.com/p/93269b02a188），区别在于，直接插入排序，需要同待插入数的前面序列，一个个比较，从而找到插入位置。而折半插入排序则通过二分查找法找到插入位置。

（三）代码+注释：

#include <stdio.h>
/*
折半插入排序，通过二分查找找到插入位置
*/
void BinaryInsertSort(int *a, int n)
{
    int low,high,temp,m,i,j;

    for(i=1;i<n;i++)
    {
        temp=a[i];//待插入数
        low=0;//上界，下标为0
        high=i-1;//下界，即是待插入数的前面一个数的下标
        m=(low+high)/2;
      //改变序列范围，确定插入位置，直到low>high
        while(low<=high)
        {
            if(a[m]>a[i])
                high=m-1;
            else
                low=m+1;
        }
      //插入位置即下标为low，这个步骤，想不明白可以在草稿纸上模拟下步骤，理解应该不难
        for(j=i-1;j>=low;j--)
        {
            a[j+1]=a[j];
        }
      //循环移动序列，原a[i]被覆盖，将待插入数temp赋值给a[low]
        a[low]=temp;
    }
    return;
}
int main(){
    int a[6]={2,4,3,2,7,3};
    BinaryInsertSort(a,6);
    for(int i=0;i<6;i++){
        printf("%d ",a[i]);
    }
}

明天写快排的思路，溜了溜了，睡觉。