2

我无法将这两种算法结合在一起。我被要求修改Binary Search以返回元素应插入数组的索引。然后我被要求实现一个Binary Insertion Sort使用 myBinary 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;
    }
}
4

4 回答 4

2

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

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;
    }
}
于 2017-04-10T08:24:57.270 回答
1

插入排序的工作原理是，它创建一个新的空数组 B，并且对于未排序的数组 A 中的每个元素，它对 B 到目前为止已构建的部分进行二进制搜索（从左到右），将所有元素移动到B 中位置的右侧它选择一个右侧并将元素插入其中。因此，您正在 B 中构建一个始终排序的数组，直到它是 B 的完整大小并包含 A 中的所有内容。

两件事情：

一，二分查找应该可以取一个int startOfArray 和一个int endOfArray，并且只会在这两个点之间进行二分查找。这允许您仅考虑数组 B 中实际上是已排序数组的部分。

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

于 2013-06-06T02:59:28.423 回答
1

我意识到这是旧的，但问题的答案是，也许有点不直观，“Middleindex - 1”在所有情况下都不会是您的插入索引。如果您在纸上处理几个案例，问题应该会变得很明显。

我有一个解决这个问题的扩展方法。要将其应用于您的情况，您将遍历现有列表，插入一个空的起始列表。

public static void BinaryInsert<TItem, TKey>(this IList<TItem> list, TItem item, Func<TItem, TKey> sortfFunc)
        where TKey : IComparable
    {
        if (list == null)
            throw new ArgumentNullException("list");

        int min = 0;
        int max = list.Count - 1;
        int index = 0;

        TKey insertKey = sortfFunc(item);

        while (min <= max)
        {
            index = (max + min) >> 1;

            TItem value = list[index];
            TKey compKey = sortfFunc(value);
            int result = compKey.CompareTo(insertKey);

            if (result == 0)
                break;
            if (result > 0)
                max = index - 1;
            else
                min = index + 1;
        }

        if (index <= 0)
            index = 0;
        else if (index >= list.Count)
            index = list.Count;
        else
            if (sortfFunc(list[index]).CompareTo(insertKey) < 0)
                ++index;

        list.Insert(index, item);
    }
于 2014-10-18T17:58:25.190 回答
0

伙计，我认为您的代码存在严重问题。不幸的是，您错过了该算法的成果（逻辑）。您在这里的神圣目标是首先获得索引，插入是小菜一碟，但索引需要一些汗水。请不要看到这个算法，除非你尽了最大的努力并迫切需要它。永不放弃，你已经知道逻辑，你的目标是在你身上找到它。请让我知道任何错误，差异等。快乐编码！ 

public class Insertion {
private int[] a;
int n;
int c;

public Insertion()
{
    a = new int[10];
    n=0;
}

int find(int key)
{
    int lowerbound = 0;
    int upperbound = n-1;

    while(true)
    {
        c = (lowerbound + upperbound)/2;
        if(n==0)
            return 0;
        if(lowerbound>=upperbound)
        {
            if(a[c]<key)
                return c++;
            else
                return c;
        }
        if(a[c]>key && a[c-1]<key)
            return c;
        else if (a[c]<key && a[c+1]>key)
            return c++;
        else
        {
            if(a[c]>key)
                upperbound = c-1;
            else
                lowerbound = c+1;
        }
    }
}

void insert(int key)
{
   find(key);
   for(int k=n;k>c;k--)
   {
       a[k]=a[k-1];
   }
   a[c]=key;
   n++;
}
void display()
{
    for(int i=0;i<10;i++)
    {
        System.out.println(a[i]);
    }
}

public static void main(String[] args)
{
    Insertion i=new Insertion();
    i.insert(56);
    i.insert(1);
    i.insert(78);
    i.insert(3);
    i.insert(4);
    i.insert(200);
    i.insert(6);
    i.insert(7);
    i.insert(1000);
    i.insert(9);
    i.display();
}

}

于 2015-04-12T01:07:06.050 回答