import java.util.Arrays;

/**
 *插入二分排序
 * @author 123
 *
 */
public class Sort2{
	public static void sort(int[] A){
		int[] B = A.clone();
		for(int i=1;i<A.length;i++){
			int left = 0;
			int right = i;
			int mid = 0;
			while(left<=right){
				mid = (left+right)/2;
				if(A[i]>A[mid]){
					left = mid+1;
				}
				if(A[i]<A[mid]){
					right = mid-1;
				}
				if(A[i]==A[mid]){
					break;
				}
				if(left-right==1&&A[i]>A[mid]){
					mid++;
				}
			}
			int j=i;
			while(j!=mid){
				Swap.swap(A,j,j-1);
				j--;
			}
		
			System.out.print(B[i]+":::");
			System.out.println(Arrays.toString(A));
		}
	}
}
``