java折半插入排序算法

package datastructure.sort;

public class BinaryInsertSort {
    public static int getInsertIndex(int[] arr, int end) {
        int firstIndex = 0;
        int lastIndex = end - 1;
        int key = arr[end];
        int insertIndex = 0;
        while (firstIndex <= lastIndex) {

            int mid = (firstIndex + lastIndex) >> 1;
            if (key == arr[mid]) {
                insertIndex = mid + 1;
                break;
            }
            // 待插入关键字大于已排序好的中间数字，则插入位置在后半部分
            else if (key > arr[mid])
                firstIndex = mid + 1;
            // 待插入关键字小于已排序好的中间数字，则插入位置在前半部分
            else
                lastIndex = mid - 1;
            insertIndex = firstIndex;
        }

        return insertIndex;
    }

    public static void binaryInsertSort1(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int insertIndex = getInsertIndex(arr, i);
            int j;
            for (j = i - 1; j >= insertIndex && temp < arr[j]; j--)
                arr[j + 1] = arr[j];
            arr[j + 1] = temp;
        }

    }

    public static void main(String[] args) {
        int[] arr = { 1,0,2,1 };
        BinaryInsertSort.binaryInsertSort1(arr);
        ;
        for (int i : arr)
            System.out.print(i + ",");
    }

}