java - Java中使用二分查找实现二分插入排序

Question

我在将这两种算法组合在一起时遇到问题。我被要求修改二分搜索以返回应将元素插入数组的索引。然后，我被要求实现一个二分插入排序，它使用我的二分搜索对随机生成的int数组进行排序。

我的二分搜索按照预期的方式工作，每当我单独测试它时都会返回正确的索引。我写了二进制插入排序来感受一下它是如何工作的，并且让它也能工作。一旦我将两者结合在一起，它就会破裂。我知道我错误地将它们一起实现，但我不确定我的问题出在哪里。

这是我得到的:

public class Assignment3
{
    public static void main(String[] args)
    {   
        int[] binary = { 1, 7, 4, 9, 10, 2, 6, 12, 3, 8, 5 };

        ModifiedBinaryInsertionSort(binary);

    }

    static int ModifiedBinarySearch(int[] theArray, int theElement)
    {
        int leftIndex = 0;
        int rightIndex = theArray.length - 1;
        int middleIndex = 0;

        while(leftIndex <= rightIndex)
        {
            middleIndex = (leftIndex + rightIndex) / 2;

            if (theElement == theArray[middleIndex])
                return middleIndex;
            else if (theElement < theArray[middleIndex])
                rightIndex = middleIndex - 1;
            else
                leftIndex = middleIndex + 1;
        }

        return middleIndex - 1;
    }

    static void ModifiedBinaryInsertionSort(int[] theArray)
    {
        int i = 0;
        int[] returnArray = new int[theArray.length + 1];

        for(i = 0; i < theArray.length; i++)
        {
            returnArray[ModifiedBinarySearch(theArray, theArray[i])] = theArray[i];
        }

        for(i = 0; i < theArray.length; i++)
        {
            System.out.print(returnArray[i] + " ");
        }
    }
}

运行时得到的返回值为1 0 0 0 0 2 0 0 3 5 12。有什么建议吗？

更新:更新了 ModifiedBinaryInsertionSort

static void ModifiedBinaryInsertionSort(int[] theArray)
{
    int index = 0;
    int element = 0;
    int[] returnArray = new int[theArray.length];

    for (int i = 1; i < theArray.lenght - 1; i++)
    {
        element = theArray[i];
        index = ModifiedBinarySearch(theArray, 0, i, element);
        returnArray[i] = element;

        while (index >= 0 && theArray[index] > element)
        {
            theArray[index + 1] = theArray[index];
            index = index - 1;
        }
        returnArray[index + 1] = element;
    }
}

Answer 1

这是我使用二分搜索对整数数组进行排序的方法。 它修改作为参数传递的数组。

public static void binaryInsertionSort(int[] a) {
    if (a.length < 2)
        return;
    for (int i = 1; i < a.length; i++) {
        int lowIndex = 0;
        int highIndex = i;
        int b = a[i];

        //while loop for binary search
        while(lowIndex < highIndex) {
            int middle = lowIndex + (highIndex - lowIndex)/2; //avoid int overflow
            if (b >= a[middle]) {
                lowIndex = middle+1;
            }
            else {
                highIndex = middle;
            }
        }
        //replace elements of array
        System.arraycopy(a, lowIndex, a, lowIndex+1, i-lowIndex);
        a[lowIndex] = b;
    }
}