在 Java 中使用二分搜索实现二分插入排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16953009/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Implementing a binary insertion sort using binary search in Java
提问by MacSalty
I'm having trouble combining these two algorithms together. I've been asked to modify Binary Searchto return the index that an element should be inserted into an array. I've been then asked to implement a Binary Insertion Sortthat uses my Binary Searchto sort an array of randomly generated ints.
我无法将这两种算法结合在一起。我被要求修改Binary Search以返回元素应插入数组的索引。然后我被要求实现一个Binary Insertion Sort使用 myBinary Search对随机生成的ints.
My Binary Searchworks the way it's supposed to, returning the correct index whenever I test it alone. I wrote out Binary Insertion Sortto 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.
我Binary Search按照它应该的方式工作，每当我单独测试时都会返回正确的索引。我写出来是Binary Insertion Sort为了感受它是如何工作的，并让它也能工作。一旦我将两者结合在一起，它就会破裂。我知道我一起错误地实施了它们，但我不确定我的问题出在哪里。
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?
当我运行它时，我得到的返回值是1 0 0 0 0 2 0 0 3 5 12. 有什么建议？
UPDATE: updated ModifiedBinaryInsertionSort
更新：更新 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;
}
}
采纳答案by Patashu
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.
插入排序的工作原理是，它创建一个新的空数组 B，并且对于未排序数组 A 中的每个元素，它二分搜索到 B 的到目前为止已经构建的部分（从左到右），将所有元素移动到B 中位置的右侧，它选择一个右侧并将元素插入其中。 因此，您正在 B 中构建一个始终排序的数组，直到它是 B 的完整大小并包含 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.
一，二分查找应该能够获取一个 int startOfArray 和一个 int endOfArray，它只会在这两点之间进行二分查找。这允许您使其仅考虑数组 B 中实际为已排序数组的部分。
Two, before inserting, you must move all elements one to the right before inserting into the gap you've made.
二，在插入之前，您必须将所有元素向右移动一位，然后再插入您制作的间隙中。
回答by Taekahn
I realize this is old, but the answer to the question is that, perhaps a little unintuitively, "Middleindex - 1" will not be your insertion index in all cases. If you run through a few cases on paper the problem should become apparent.
我意识到这是旧的，但问题的答案是，也许有点不直观，“Middleindex - 1”不会在所有情况下都是您的插入索引。如果您在纸上处理几个案例，问题应该变得明显。
I have an extension method that solves this problem. To apply it to your situation, you would iterate through the existing list, inserting into an empty starting list.
我有一个解决这个问题的扩展方法。要将其应用于您的情况，您将遍历现有列表，插入一个空的起始列表。
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);
}
回答by JumpMan
Dude, I think you have some serious problem with your code. Unfortunately, you are missing the fruit (logic) of this algorithm. Your divine goal here is to get the index first, insertion is a cake walk, but index needs some sweat. Please don't see this algorithm unless you gave your best and desperate for it. Never give up, you already know the logic, your goal is to find it in you. Please let me know for any mistakes, discrepancies etc. Happy coding!!
伙计，我认为您的代码存在严重问题。不幸的是，您错过了该算法的成果（逻辑）。你在这里的神圣目标是首先获得索引，插入是小菜一碟，但索引需要一些汗水。请不要看这个算法，除非你竭尽全力并且迫切需要它。永不放弃，你已经知道逻辑，你的目标是在你身上找到它。请让我知道任何错误，差异等。快乐编码！！
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();
}
}
}
回答by Stephane B.
Here is my method to sort an array of integers using binary search. It modifies the array that is passed as argument.
这是我使用二进制搜索对整数数组进行排序的方法。它修改作为参数传递的数组。
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;
}
}
