使用Java中的二进制搜索实现二进制插入排序

Question

我在将这两种算法结合在一起时遇到麻烦。我被要求修改Binary Search以返回将元素插入数组的索引。然后有人要求Binary Insertion Sort我实现一个使用my Binary Search对随机生成的数组进行排序的ints。

我Binary Search按照预期的方式工作，每当我单独测试它时都返回正确的索引。我写信Binary Insertion Sort是为了了解它是如何工作的，并使其也能工作。一旦将两者结合在一起，它就会崩溃。我知道我在一起实施起来不正确，但是我不确定问题出在哪里。

这是我得到的：

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

插入排序的工作方式是，创建一个新的空数组B，然后对未排序数组A中的每个元素进行二进制搜索，以搜索到目前为止已构建的B部分（从左到右），将所有html" target="_blank">元素移至在B中位置的右边，它选择一个右边并在其中插入元素。因此，您将在B中随时构建一个排序数组，直到它成为B的完整大小并包含A中的所有内容。

两件事情：

第一，二进制搜索应该能够采用int startOfArray和int
endOfArray，并且它将仅在这两点之间进行二进制搜索。这使您可以仅考虑数组B的实际排序数组部分。

二，在插入之前，必须将所有元素向右移动一个，然后再插入到已创建的间隙中。