[数据结构与算法]【二、折半插入排序】

算法思想：
1. 从前面的有序子序列中使用 “折半查找 ”查找出待插入元素应该被插入的位置
2. 给插入位置腾出空间
3. 将待插入元素复制到表中的插入位置

public class 折半插入排序 {
    public static void main(String[] args) {
        int nums[]={6,1,3,2,4};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    static void sort(int nums[]){
        int j;
        for (int i=1;i<nums.length;i++){
            int temp=nums[i];           //记录当前元素
            //1.折半查找
            int low = 0; int high=i-1;
            while (low<=high){                  //每次结束的时候，low>high
                int mid = low+(high-low)/2;
                if (temp<nums[mid])high=mid-1;  //注意此处的比较时，temp<nums[mid]
                else low=mid+1;
            }
            //2.给插入位置腾出空间
            for (j= i-1;j>high;j--){
                nums[j+1]=nums[j];
            }
            //3.将待插入元素复制到表中的插入位置
            nums[j+1]=temp;
        }
    }
}