java - 制作二分查找函数

Question

我正在做一项家庭作业，我应该创建一个执行二进制插入排序的函数，但我的函数似乎无法正常工作。

这里我尝试将二分查找函数与插入排序函数结合起来(作业任务中指定需要采用函数的形式:insertionSort(int[] array, int lo, int hi ))

 public static void insertionSort(int[] array, int lo, int hi){
        int mid; 
        int pos; 

        for (int i = 1; i < array.length; i++) {

            int x= array[i]; 

            while (lo < hi) {
                mid = lo + (hi -lo)/2;
                if (x == array[mid]) {
                    pos = mid; 
                }
                if (x > array[mid]) {
                    lo = mid+1; 
                }
                else if (x < array[mid]) {
                    hi = mid-1; 
                }
            }
            pos = lo; 

                for (int j = i; j > pos; j--) {
                array[j] = array[j-1]; 
            }
            array[pos] = x; 
        }
    }

如果我尝试使用列表 {2,5,1,8,3} 运行它，输出将为

2 5 1 3 1(如果 lo < hi 并且如果 lo > hi)

2 5 3 8 5(如果 lo==hi)

不过，我期待的是一个排序列表...... 知道我做错了什么吗？

Answer 1

只是为了给您一个可能的想法:

public static void insertionSort(int[] array) {
    if (array.length <= 1) {
        return;
    }

    // Start with an initially sorted part.
    int loSorted = array.length - 1;
    //int hiSorted = array.length;

    while (loSorted > 0) {

        // Take one from the array
        int x = array[0];

        // Where in the sorted part to insert?
        int insertI = insertPosition(array, loSorted);

        // Insert x at insertI
        ...
        --loSorted;
    }
}