Java実装二分(折半)挿入ソート

シーケンスa[0]、a[1]...a[n];ここで、a[i-1]の前は既に秩序化されており、挿入時a[i]の場合、a[i]の挿入位置を二分法で検索する
効率:O(N^2)は、初期の基本秩序のシーケンスに対して、効率的に直接ソートを挿入するよりも劣る.ランダム無秩序シーケンスの場合、直接挿入ソートよりも効率が高い

/*
 *   (  )    
 *       a[0],a[1]...a[n];  a[i-1]       ,    a[i] ,       a[i]     
 */
public class BinaryInsertSort {

	public static void main(String[] args) {
		int len = 10;
		int[] ary = new int[len];
		Random random = new Random();
		for (int j = 0; j < len; j++) {
			ary[j] = random.nextInt(1000);
		}
		binaryInsert(ary);
		/*
		 *      ：     ，       ，     ，        ：O(n lg n)     ，    ，      O(n^2)
		 *                O(n|logn)。
		 */
		//     
		printArray(ary);
	}
	/**
	 *     
	 * @param ary
	 */
	private static void binaryInsert(int[] ary) {
		int setValueCount = 0;
		//             ，                  
		for (int j = 1; j < ary.length; j++) {//     n
			//      
			int key = ary[j];
			// ∆             
//			int index = binarySearchAsc(ary, ary[j], 0, j - 1);//    ：O(logn)
//			int index = binarySearchDesc(ary, ary[j], 0, j - 1);//    ：O(logn)
			int index = binarySearchDesc2(ary, ary[j], 0, j - 1);//    ：O(logn)
			printArray(ary);
			System.out.println(" " + j +"              ：" + index);
			//        ，             
			for (int i = j; i > index; i--) {//    ,    ：(n-1)+(n-2)+...+n/2=O(n^2)
				ary[i] = ary[i - 1]; //i-1 <==> index
				setValueCount++;
			}
			ary[index] = key;
			setValueCount++;
		}
		System.out.println("
     (setValueCount)=====> " + setValueCount);
	}

	/**
	 *           
	 * 
	 * @param ary
	 *                      
	 * @param target
	 *                
	 * @param from
	 *                     
	 * @param to
	 *                     
	 * @return         ，        
	 */
	private static int binarySearchAsc(int[] ary, int target, int from, int to) {
		int range = to - from;
		//       0，          ，     
		if (range > 0) {
			//      
			int mid = (to + from) / 2;
			//         ，       
			if (ary[mid] > target) {
				/*
				 * mid > target,     ，target  ，        ，  target   mid   ，
				 *        ，  from  mid-1    ，   to=mid-1
				 */
				return binarySearchAsc(ary, target, from, mid - 1);
			} else {
				/*
				 * mid < target,     ，target  ，     ，           mid+1
				 */
				return binarySearchAsc(ary, target, mid + 1, to);
			}
		} else {
			if (ary[from] > target) {//  5,4,      4
				return from;
			} else {
				return from + 1;
			}
		}
	}
	/**
	 *        ，   
	 */
	private static int binarySearchDesc(int[] ary, int target, int from, int to) {
		int range = to - from;
		if (range > 0) {
			int mid = (from + to) >>> 1;
			if (ary[mid] > target) {
				return binarySearchDesc(ary, target, mid + 1, to);
			} else {
				return binarySearchDesc(ary, target, from, mid - 1);
			}
		} else {
			if (ary[from] > target) {//  5,4,      4
				return from + 1;
			} else {
				return from;
			}
		}
	}
	
	/**
	 *        ，    
	 */
	private static int binarySearchDesc2(int[] ary, int target, int from, int to) {
//		while(from < to) {
		for (; from < to; ) {
			int mid = (from + to) >>> 1;
			if (ary[mid] > target) {
				from = mid + 1;
			} else {
				to  = mid -1;
			}
		}
		//from <==> to;
		if (ary[from] > target) {//  5,4,      4
			return from + 1;
		} else {
			return from;
		}
	}

	private static void printArray(int[] ary) {
		for (int i : ary) {
			System.out.print(i + " ");
		}
	}

}

印刷

918 562 442 531 210 216 931 706 333 132  1              ：1
918 562 442 531 210 216 931 706 333 132  2              ：2
918 562 442 531 210 216 931 706 333 132  3              ：2
918 562 531 442 210 216 931 706 333 132  4              ：4
918 562 531 442 210 216 931 706 333 132  5              ：4
918 562 531 442 216 210 931 706 333 132  6              ：0
931 918 562 531 442 216 210 706 333 132  7              ：2
931 918 706 562 531 442 216 210 333 132  8              ：6
931 918 706 562 531 442 333 216 210 132  9              ：9

     (setValueCount)=====> 24
931 918 706 562 531 442 333 216 210 132