【开发者笔记】插入排序改进

  public static void insertionSort(int[] arr) {　　　　　　　　　　
        for (int j = 1; j < arr.length; j++) {　　　　　　　　　　//c1*n
            int key = arr[j];　　　　　　　　　　　　　　　　　　　　//c2*n
            int i;　　　　　　　　　　　　　　　　　　　　　　　　　　 //c3*n
            for (i = j - 1; i >= 0 && arr[i] > key; i--) {　　　//c4*n*(n+1)/2
                arr[i + 1] = arr[i];　　　　　　　　　　　　　　　　//c5*n*(n+1)/2
                }
            arr[i + 1] = key;　　　　　　　　　　　　　　　　　　　　//c6*n
        }
    }

 
/*插入排序的改进版，用二分法插入从而取代一次次的比较，减小了n*n-nlgn的时间复杂度*/
public static void inproveInsertionSort(int[] arr) {
        for (int j = 1; j < arr.length; j++) {　　　　　　//c1*n
            int key = insertToArray(arr,0,j-1,j);　　　　//c2*n*log2n
            int temp=arr[j];　　　　　　　　　　　　　　　　//c3*n
            for(int i=j;i>key;i--){　　　　　　　　　　　　//c4*n*(n+1)/2
                arr[i]=arr[i-1];　　　　　　　　　　　　　　//c5*n*(n+1)/2
            }
            arr[key]=temp;　　　　　　　　　　　　　　　　　　//c6*n
        }
    }
/*二分法查找key应该插入有序数组arr【b,e】的位置，返回应当插入的数组index，递归查询*/
 public static int insertToArray(int[]arr,int b,int e,int key){　　//nlog2n
        if(b>=e){
            if(arr[key]<arr[b]){
                return b;
            }
            else return b+1;
        }
        int mid=(b+e)/2;
        if(arr[key]<=arr[mid])return insertToArray(arr,b,mid,key);
        return insertToArray(arr,mid+1,e,key) ;
    }