一头扎进算法导论-二分法思想改进插入排序O（nlog2(n)）

蔚落 2022-07-16 10:50 153阅读 0赞

**背景：**我们知道在插入算法中，是根据while循环采用一种线性查找（反向）来扫描已排好序的子数组A\[1…j-1\]。现在我们使用二分查找来把插入排序的最坏总运行情况O（n^2） 改进为O（nlog2(n)）

public int[] sortByBinary(int[] a){
            System.out.println(Arrays.toString(a));
            for(int k=1;k<a.length;k++){
                int value = a[k];
                int start = 0;
                int end = k-1;
                int insertIndex = insertByBinary(a,start,end,value);
                for(int i=end;i>=insertIndex;i--){
       //从结尾到插入位置
                    a[i+1] = a[i];//位置偏移
                }
                a[insertIndex] = value;
                System.out.println(Arrays.toString(a));
            }
            return a;
        }
    
        /** * jiangjintai * 2016年10月16日 * @param a * @param start * @param end */
        private int insertByBinary(int[] a, int start,int end,int value) {
       //返回插入位置
            int mid  = (start+end)/2;
            if(start>end){
       //临界条件，返回插入位置，为结束指针加1，一定要达到临界条件或当前数等于中间数时才能返回
                return end+1;
            }
            //使用当前数与中间数进行判断
            if(value>a[mid]){
                start=mid+1;//如果降序的话，那么就往后移，改成end=mid-1;
                return insertByBinary(a, start,end,value);
            }else if(value<a[mid]){
                end = mid - 1;//如果降序的话，那么就往后移，改成start=mid+1;
                return insertByBinary(a, start,end,value);
            }else{
       //当前数等于中间数，则返回中间数坐标
                return mid;
            }
        }