java 我的二进制插入排序算法的错误在哪里？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3075752/
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
Where is my error in my binary insertion sort algorithm?
提问by dato datuashvili
I have tried to implement binary insertion sort algorithm.
我试图实现二进制插入排序算法。
Here is my code:
这是我的代码：
public class binary_insertion {
public static void sort(int a[],int n){
for (int i=0;i<n;++i){
int temp=a[i];
int left=0;
int right=i;
while (left<right){
int middle=(left+right)/2;
if (temp>=a[middle])
left=right+1;
else
right=middle;
}
for (int j=i;j>left;--j){
swap(a,j-1,j);
}
}
}
public static void main(String[] args){
int a[]=new int[]{12,10,34,23,9,7,8,5,6};
sort(a,a.length);
for (int i=0;i<a.length;i++){
System.out.println(a[i]);
}
}
public static void swap(int a[],int i,int j){
int k=a[i];
a[i]=a[j];
a[j]=k;
}
}
and my result is wrong:
我的结果是错误的：
5
7
6
9
8
10
12
34
23
What did I do wrong?
我做错了什么？
回答by IVlad
First thing that stands out is here:
首先突出的是这里：
while (left<right){
int middle=(left+right)/2;
if (temp>=a[middle])
left=right+1;
else
right=middle;
You want left = middle + 1.
你要left = middle + 1。
The code works for me with that change.
该代码适用于我的更改。
回答by Willy William
Some built-in functions of java can be used here
这里可以使用java的一些内置函数
public void sort(int array[])
{
for (int i = 1; i < array.length; i++)
{
int x = array[i];
// Find location to insert using binary search
int j = Math.abs(Arrays.binarySearch(array, 0, i, x) + 1);
//Shifting array to one location right
System.arraycopy(array, j, array, j+1, i-j);
//Placing element at its correct location
array[j] = x;
}
}
public static void main(String[] args)
{
int[] arr = {37, 23, 0, 17, 12, 72, 31,
46, 100, 88, 54 };
sort(arr);
for(int i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
}
Output is:
Sorted array:
0 12 17 23 31 37 46 54 72 88 100
输出为：
排序数组：
0 12 17 23 31 37 46 54 72 88 100
