我的二进制插入代码有什么问题？

Question

我是 Java 的初学者，我试图创建一个 class 来实现二进制插入排序，并对数据大小为 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();
        }

有人可以帮我修复我的代码吗？

Answer 1

您的二进制插入排序代码包含许多错误，您的编译器一定会告诉您这些错误。您的首要任务应该是了解并解决所有这些问题。或者，二进制插入排序代码的许多问题似乎是由于它是通过尝试修改标准插入排序代码而产生的。我建议从头开始实现二进制版本。另外，先实现排序；在排序本身工作后添加检测（比较和交换计数）。

此外，您的代码中有一些明显的奇怪之处：

以递归方式实现任何版本的插入排序都是非典型且无益的。
您对递归实现的特定尝试无论如何都没有意义：主循环将运行只有一次迭代，循环后的代码将失效。
很难确定，但我认为您对二进制插入排序的整个想法是错误的。您似乎试图将数组拆分成多个部分以递归地对它们进行排序，如合并排序或快速排序，但这不是二进制插入排序的工作方式。二分插入排序与标准插入排序的区别主要在于它使用二分搜索而不是线性搜索来查找每个元素的插入位置。

Answer 2

您的代码中有错误。我纠正了他们。首先，您的 left 和 right 变量在这一行中定义：-

public double binaryInsertionSort(long array[], int value, int left, int right)

你为什么又在方法体内定义它们。所以我删除了他们的双重声明。其次，您将 left 变量的值分配给了 y，这是错误的。实际上你必须分配 y toleft 的值。您代码中的第三个错误是您的方法调用错误。您使用四个参数定义了 binaryInsertionSort 并通过单个参数调用它，因此我修改了您的方法调用，如下所示：-

sortTime = binaryInsertionSort(sortedArray,10,20,30);

其余都是小错误。这是您的 `binaryInsertionSort 方法的核心代码：-

public double binaryInsertionSort(long array[], int value, int left, int right) {

setType("Binary Insertion Sort");

long temp;

int y=0;

//int left, right;

double numOfSwap = 0, numOfComparisons = 0;

double startTime = System.nanoTime();

for (int x = 1; x < array.length; x++) {

temp = array[x];

numOfSwap++;

y=left;

right = x;

if (left>right){
return -1;
}

int middle = (left + right)/2;

if (array[middle] == value){

    numOfComparisons++;
    return middle;

} else if (array[middle]>value){

    numOfComparisons++;
    return binaryInsertionSort(array, value,left, middle -1);

} else{

    numOfComparisons++;    
    return binaryInsertionSort (array, value, middle +1, right);
    }

}

double endTime = System.nanoTime();

setSwap(numOfSwap / 3);

setComparisons(numOfComparisons);

setTime(endTime - startTime);

return getTime();

}
`

我已将程序的完整更正代码邮寄给您。检查你的邮箱。无论您觉得我的回答有用与否，请确认我。快乐编码:)

我的二进制插入代码有什么问题？

What is Wrong with my Binary Insertion Code?

java

sorting

search

binary

insertion