java我的二进制插入代码有什么问题?
我是一名Java初学者,试图创建一个实现二进制插入排序的类,并对数据大小为50、500、5000、50000和500000的随机数组进行排序
当我将其实现为插入排序时,该程序运行良好
public double InsertionSort(long array[]) {
setType("Insertion Sort");
long temp;
int y;
double numOfSwap = 0, numOfComparisons = 0;
double startTime = System.nanoTime();
for (int x = 1; x < array.length; x++) {
temp = array[x];
numOfSwap++;
y = x;
numOfComparisons++;
while ((y > 0)) {
numOfComparisons++;
if ((array[y - 1]) > temp) {
array[y] = array[y - 1];
numOfSwap++;
y = y - 1;
} else
break;
}
array[y] = temp;
numOfSwap++;
}
double endTime = System.nanoTime();
setSwap(numOfSwap / 3);
setComparisons(numOfComparisons);
setTime(endTime - startTime);
return getTime();
}
但当我尝试插入二进制搜索时,它不再起作用了
public double binaryInsertionSort(long array[], int value, int left, int right) {
setType("Binary Insertion Sort");
long temp;
int y;
int left, right;
double numOfSwap = 0, numOfComparisons = 0;
double startTime = System.nanoTime();
for (int x = 1; x < array.length; x++) {
temp = array[x];
numOfSwqp++;
int left = y;
int right = x;
if (left>right)
return -1;
int middle = (left + right)/2;
if (array[middle] == value)
return middle;
numOfComparisons++;
else if (array[middle]>value)
return binaryInsertionSort(array, value,left, middle -1);
numOfComparisons++;
else
return binaryInsertionSort (array, value, middle +1, right);
numOfComparisons++;
}
double endTime = System.nanoTime();
setSwap(numOfSwap / 3);
setComparisons(numOfComparisons);
setTime(endTime - startTime);
return getTime();
}
有人能帮我修改代码吗
# 1 楼答案
二进制插入排序代码包含许多编译器必须告诉您的错误。你的首要任务应该是理解并解决所有这些问题。或者,二进制插入排序代码的许多问题似乎是由于试图调整标准插入排序代码而产生的。我建议从零开始实现二进制版本。此外,首先实现排序;在排序本身工作后添加插装(比较和交换计数)
此外,代码中还有一些明显的奇怪之处:
递归地实现任何版本的插入排序都是不典型的,也没有好处
无论如何,您对递归实现的具体尝试都没有意义:主循环将只运行一次迭代,循环后的代码将失效
很难确定,但我认为你对二进制插入排序的整个想法都错了。您似乎试图将数组拆分为多个部分,以递归方式对它们进行排序,比如合并排序或快速排序,但二进制插入排序不是这样工作的。二进制插入排序与标准插入排序的主要区别在于,它使用二进制搜索而不是线性搜索来查找每个元素的插入位置
# 2 楼答案
你的代码有错误。我纠正了他们。首先,您的
left
和right
变量在这一行中定义:-为什么要在方法体中再次定义它们。所以我删除了他们的双重声明。其次,您将
left
变量的值赋给了y
,这是错误的。实际上你必须给y to
左赋值。代码中的第三个错误是方法调用错误。您使用四个参数定义了binaryInsertionSort,并通过单个参数调用它,所以我修改了您的方法调用,如下所示:-sortTime=二进制插入排序(SortDarray,10,20,30)
其余的都是小错误。以下是“binaryInsertionSort”方法的正确代码:-
我给你发了完整的程序代码。检查你的邮箱。无论你觉得我的答案有用与否,都要告诉我。快乐编码:)