实现排序使用的Java二进制搜索二进制插入 [英] Implementing a binary insertion sort using binary search in Java
问题描述
我无法对这两种算法结合起来。我一直在问修改二进制搜索返回一个元素应该插入到一个数组的索引。我一直再要求实施折半插入排序使用我的二进制搜索来随机生成一个数组排序整数。
我的二进制搜索和它应该的方式，返回每当我独自测试正确的索引。我写了折半插入排序来感受一下它是如何工作的，并得到了以工作为好。只要我结合两者结合起来，它打破。我知道我实现它们错误地在一起，但我不知道在哪里我的问题奠定了。
下面是我有：
公共类Assignment3
{
公共静态无效的主要（字串[] args）
{
INT []二元= {1，7,4，9，10，2，6，12，3，8,5};
ModifiedBinaryInsertionSort（二进制）;
}
静态INT ModifiedBinarySearch（INT [] theArray，INT theElement）
{
INT leftIndex = 0;
INT rightIndex = theArray.length - 1;
INT middleIndex = 0;
而（leftIndex＆LT; = rightIndex）
{
middleIndex =（leftIndex + rightIndex）/ 2;
如果（theElement == theArray [middleIndex]）
返回middleIndex;
否则，如果（theElement＆LT; theArray [middleIndex]）
rightIndex = middleIndex - 1;
其他
leftIndex = middleIndex + 1;
}
返回middleIndex - 1;
}
静态无效ModifiedBinaryInsertionSort（INT [] theArray）
{
INT I = 0;
INT [] returnArray =新INT [theArray.length + 1];
对于（i = 0; I＆LT; theArray.length;我++）
{
returnArray [ModifiedBinarySearch（theArray，theArray [I]）] = theArray [I]
}
对于（i = 0; I＆LT; theArray.length;我++）
{
System.out.print（returnArray [我] +）;
}
}
}
返回值，我得到这个当我运行它 1 0 0 0 0 2 0 0 3 5 12 。有什么建议？
更新：更新ModifiedBinaryInsertionSort
静态无效ModifiedBinaryInsertionSort（INT [] theArray）
{
INT索引= 0;
INT元素= 0;
INT [] returnArray =新INT [theArray.length]
的for（int i = 1; I＆LT; theArray.lenght - 1;我++）
{
元= theArray [I]
指数= ModifiedBinarySearch（theArray，0，I，元素）;
returnArray [I] =元;
而（索引＆gt; = 0＆功放;＆放大器; theArray [指数]＆gt;元素）
{
theArray [索引+ 1] = theArray [指数]
指数=指数 - 1;
}
returnArray [索引+ 1] =元;
}
}
如何插入排序的工作原理是，它会创建一个新的空数组B和，在无序数组A每一个元素，它的二进制搜索到B的部分已建成至今（从左至右），转移所有元素给它选择一个正确的，并插入的元素B中的位置的权利。那么，你是建立在B上不惜一切倍排序的数组，直到这是B的全尺寸，并包含所有事情，。
两件事情：
一，二分搜索应该能采取一个int startOfArray和int endOfArray，它只会这两个点之间的二进制搜索。这使您可以使其考虑数组b只有一部分实际上是排序的数组。
二，在插入之前，你必须在一移动的所有元素，以正确的插入到你所做的差距了。
I'm having trouble combining these two algorithms together. I've been asked to modify Binary Search to return the index that an element should be inserted into an array. I've been then asked to implement a Binary Insertion Sort that uses my Binary Search to sort an array of randomly generated ints.
My Binary Search works the way it's supposed to, returning the correct index whenever I test it alone. I wrote out Binary Insertion Sort to get a feel for how it works, and got that to work as well. As soon as I combine the two together, it breaks. I know I'm implementing them incorrectly together, but I'm not sure where my problem lays.
Here's what I've got:
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] + " ");
}
}
}
The return value I get for this when I run it is 1 0 0 0 0 2 0 0 3 5 12. Any suggestions?
UPDATE: updated 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;
}
}
How an insertion sort works is, it creates a new empty array B and, for each element in the unsorted array A, it binary searches into the section of B that has been built so far (From left to right), shifts all elements to the right of the location in B it choose one right and inserts the element in. So you are building up an at-all-times sorted array in B until it is the full size of B and contains everything in A.
Two things:
One, the binary search should be able to take an int startOfArray and an int endOfArray, and it will only binary search between those two points. This allows you to make it consider only the part of array B that is actually the sorted array.
Two, before inserting, you must move all elements one to the right before inserting into the gap you've made.
这篇关于实现排序使用的Java二进制搜索二进制插入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
