学步园

    折半插入排序是直接插入排序的一种优化，他利用了直接插入排序中前面的元素已经完成排序的特点进行折中对比。他的效果与直接插入排序一样，但是速度更快。

package com.h3c.paixu;

public class 折半排序Demo {

	public static void main(String[] args) {
		// 1. 初始化一个无序数组
		int[] myArr = { 23, 35, 73, 27, 4, 77, 54, 84, 47, 56, 34, 32, 75, 32,
				31, 0, 99, 7, 54, 57 };

		myArr = 折半排序(myArr);

		for (int i : myArr) {
			System.out.print(i + " ");
		}

		System.out.println("");
	}

	private static int[] 折半排序(int[] myArr) {

		for (int n = 1; n < myArr.length; n++) {
			int index = 找位置(myArr, 0, n, myArr[n]);

			if (index != n) {// 如果需要挪位
				int tmpNum = myArr[n];
				for (int k = n; k > index; k--) {
					myArr[k] = myArr[k - 1];
				}
				myArr[index] = tmpNum;
			}
		}

		return myArr;
	}

	private static int 找位置(int[] tmpArr, int startIndex, int endIndex, int num) {
		int index = 0;

		// 获取折半元素的索引
		int helfIndex = (endIndex - startIndex) / 2 + startIndex;

		if (tmpArr[helfIndex] > num) {
			// 如果startIndex == endIndex，获得的折半元素就是最终对比元素，如果大于num，则返回折半的索引
			if (helfIndex == startIndex) {
				return startIndex;
			}

			index = 找位置(tmpArr, startIndex, helfIndex, num);
		} else {
			// 如果startIndex == endIndex，获得的折半元素就是最终对比元素，如果大于num，则返回折半后一位的索引
			if (helfIndex == startIndex) {
				return startIndex + 1;
			}

			index = 找位置(tmpArr, helfIndex, endIndex, num);
		}
		return index;
	}
}