一、算法

1.算法概述

直接插入排序法采用顺序查找法来查找当前记录在已经排好序的序列中的插入位置，而折半插入排序法则是在查找的过程中采用折半查找法来确定当前记录在有序序列中的位置，这便是折半插入排序法与直接插入排序法的不同之处

往期相关文章传送门：

2.算法步骤

设待排序的记录存放在数组r[1…n ]中，r[1]默认是一个有序序列
循环n-1次，每次使用折半查找法，查找r[i](i=2,…,n)在已排序好的序列r[1,….i-1]中的合适插入位置，然后将r[ i ]插入表长为i-1的有序序列r[ 1,…,i-1 ]中，直到将r[ n ]插入到表长为n-1的有序序列r[ 1…n-1 ]，最后得到一个表长为n的有序序列

（注：图片来源《数据结构简明教程》）

二、算法实践

1.Java代码

package TwentyOne_Challenge;

public class DaySix {
    public static void main(String[] args) {
        int []a={3,38,5,44,15,36,26,27,2,47,46,4,19,50,48};
        System.out.print("原来序列如下：");
        for (int i = 0; i <a.length ; i++) {
            System.out.print(a[i]+" ");
        }
        sort(a);
        System.out.println();
        System.out.print("经过折半插入排序后：");
        for (int i = 0; i <a.length ; i++) {
            System.out.print(a[i]+" ");
        }
    }
    private static void sort(int a[]){
        for (int i = 1; i <a.length ; i++) {
            if(a[i]<a[i-1]){
                int temp=a[i];//使用temp暂时存储待排序的值
                int left=0,right=i-1;//左右区间的起始下标
                //使用折半查找法查找待排序的记录在已经排好序的序列中的合适插入位置
                while(left<=right){
                    int mid=(right-left)/2+left;
                    if(temp<a[mid]){
                        right=mid-1;
                    }else{
                        left=mid+1;
                    }
                }
                //找到合适位置后，下面将有序序列中逐个后移空出位置供待排序的记录插入
                for(int j=i-1;j>=right+1;j--){
                    a[j+1]=a[j];
                }
                //最后一次循环时,left与right相等，等下一次循环发生交错循环结束，所以此时插入位置应为right+1或者left
                a[right+1]=temp;
                //a[left]=temp; 也是正确的
            }
        }

    }

}

2.执行结果

三、复杂度分析

1.时间复杂度

        从时间上比较，折半查找比顺序查找快，所以就平均性能来说，折半插入排序优于直接插入排序。折半插人排序所需要的关键字比较次数与待排序序列的初始排列无关,仅依赖于记录的个数。不论初始序列情况如何，在插入第i个记录时，需要经过以2为底 i 的对数向上取整次比较，才能确定它应插人的位置。所以当记录的初始排列为正序或接近正序时，直接插入排序比折半插入排序执行的关键字比较次数要少。
        折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。
        在平均情况下，折半插入排序仅减少了关键字间的比较次数,而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为O(n^2)