java - 二分查找和插入排序

Question

我的 insertInOrder 方法是错误的(它向后打印数字列表)。我正在读取一个数字列表，我想使用插入排序算法使用二进制搜索的索引位置按升序对数字进行排序。我不太确定如何解决这个问题，非常感谢您的帮助。

static void insertInOrder( int[] arr, int cnt, int newVal ) {

    int index = bSearch( arr, 0, arr.length-1, newVal) ;
    if (index < 0) {
        index  = -1 - index ;
    }
    for ( int i = cnt; i >= index+1 ; --i) {
       arr[i] = arr[i-1];
    }

    arr[index] = newVal;
}


public static int bSearch(int[] a, int lo, int hi, int key) {
    int mid = (lo+hi)/2;
    if(lo>hi)
        return -1;
    else if (a[mid]==key)
        return mid;
    else if (a[mid]<key)
        return bSearch(a, mid+1, hi, key);
    else
        return bSearch(a, lo, mid-1, key);
}

---

Reading in: 5 13 7 9 21
Current Output: 21 9 7 13 5
Desired Output: 5 7 9 13 21

---

这是我的 insertInOrder

    int[] arr = new int[INITIAL_CAP];
    int arrCnt= 0;
    while (infile.hasNextInt())
    {
        if ( arrCnt==arr.length )
            arr = doubleMyLength(arr);
        insertInOrder( arr, arrCnt, infile.nextInt() );
        ++arrCnt;
    }
    infile.close();

    arr = trimMyLength( arr, arrCnt );
    System.out.println("Sorted array of " + arr.length + " ints from " + args[0] + " after insert in order:" );
    printArray( arr );  // we trimmed it so count == length so we don't bother to pass in count

Answer 1

当在数组中找不到 newVal 时(这很可能发生)，您的 bSearch() 返回 -1。然后，insertInOrder() 始终将项目插入到位置 index = -1 - index，即 0。这就是结果错误的原因。

要使其正确，您的 bSearch() 需要返回值大于 newVal 的最小索引。