基本思路：折半插入排序（binary insertion sort）是對(duì)插入排序算法的一種改進(jìn)，由于排序算法過(guò)程中，就是不斷的依次將元素插入前面已排好序的序列中。由于前半部分為已排好序的數(shù)列，這樣我們不用按順序依次尋找插入點(diǎn)，可以采用折半查找的方法來(lái)加快尋找插入點(diǎn)的速度。

步驟：
（1） 將一新的元素插入到有序數(shù)組中，尋找插入點(diǎn)時(shí)，將帶插區(qū)域的首元素設(shè)置為a[low],末元素設(shè)置為a[high],比較時(shí)則將待插元素與參考元素a[m]（m=(low+high)/2）相比較。；
（2）如果待插元素比參考元素小，則選擇a[low]到a[m-1]為新的插入?yún)^(qū)域（即high=m-1）,否則選擇a[m+1]到a[high]為插入?yún)^(qū)域；
（3）如此直到low<=high不成立，即將此位置(low)之后所有元素后移一位，并將新元素插入a[high+1]中。

代碼如下：

public class Binary_Insert_Sort {
    
    public static void main(String[] args){
        int[] a = {1,3,2,5,4,4,4,4,4,4,5,5,5,5,5,5,5,1,1,1,1,2,2,2,3,4,5,7,3,2,2,24,54};
        long start = System.nanoTime();
        sort(a);
        long end = System.nanoTime();
        System.out.println(end-start  + "   " + Arrays.toString(a));
    }
    ////程序運(yùn)行時(shí)間：14639ms
    public static void sort(int[] s){ 
        for(int i = 1; i < s.length; i++){                              
            int temp = s[i];//待插元素
            int low = 0;
            int high = i-1; 
            while(low<=high){
                int mid = (low+high)/2;
                if(temp>s[mid]){//待插元素比中間值大,取m+1到high區(qū)域
                    low = mid+1;
                }else{
                    high= mid-1;
                }
            }
                
            for(int j = i;j>low;j--){//將low后面的數(shù)組整體后移
                s[j]=s[j-1];
            }
            s[low]=temp;
        }
    }
    
}