Java順序付けアルゴリズム（7）：半値挿入順序

Java順序付けアルゴリズム（7）：半値挿入順序
折半挿入並べ替え法は、二分割挿入並べ替え法とも呼ばれ、直接並べ替え法の改良版であり、i-1回挿入を行う必要があります。異なる点は、i番目の挿入は、i＋1個目の要素が挿入すべき位置を探して、前i個のデータがすでに秩序状態にあると仮定します。
コードの実装:

package sort;

public class BinaryInsertSortTest {
	public static int count = 0;

	public static void main(String[] args) {

		int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
		print(data);
		binaryInsertSort(data);
		print(data);

	}

	public static void binaryInsertSort(int[] data) {
		for (int i = 1; i < data.length; i++) {
			if (data[i] < data[i - 1]) {
				//   i     
				int tmp = data[i];
				//           
				int low = 0;
				//           
				int high = i - 1;
				while (low <= high) {
					//       
					int mid = (low + high) / 2;
					//          i     ，       
					if (data[mid] < tmp) {
						low = mid + 1;
					} else {
						high = mid - 1;
					}
				}
				// low~i         1 
				for (int j = i; j > low; j--) {
					data[j] = data[j - 1];
				}
				data[low] = tmp;
				print(data);
			}
		}
	}

	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}

}

 
実行結果:

5	3	6	2	1	9	4	8	7	
3	5	6	2	1	9	4	8	7	
2	3	5	6	1	9	4	8	7	
1	2	3	5	6	9	4	8	7	
1	2	3	4	5	6	9	8	7	
1	2	3	4	5	6	8	9	7	
1	2	3	4	5	6	7	8	9	
1	2	3	4	5	6	7	8	9