0

我正在创建一个 Java 程序,在其中实现 MergeSort 算法。我的代码如下(到目前为止):

public void merge(Integer [] left, Integer[] right, Integer[] a) {

    int i = 0;                  // a[] index (A)
    int lIndex = 0;             // left[] index (B)
    int rIndex = 0;             // right[] index (C)

    // Begin main merge process
    while((lIndex < left.length) && (rIndex < right.length)) {
        if(left[lIndex] <= right[rIndex]) {
            a[i] = left[lIndex]; // Store it
            lIndex++; // Increase index of left[]
        }
        else {
            a[i] = right[rIndex]; // Store it
            rIndex++; // Increase index of right[]
        }
        i++; // Increase index of a[]
    }
    if(i == lIndex) { // If the left array is sorted
        while(rIndex < right.length) { // Copy the contents of rhe right array to a[]
            a[i] = right[rIndex];
            i++;
            rIndex++;
        }
    }
    else { // If the right array is sorted
        while(lIndex < left.length) { // Copy the contents of the left array to a[]
            a[i] = left[lIndex];
            i++;
            lIndex++;
        }
    }
}

问题是每次我执行该函数时,输入数组都会部分排序返回。我的意思是大多数元素都在正确的位置,但有一两个放置错误,还有一些是其他元素的重复!由于我看不出真正的问题是什么,有人可以帮我吗?该实现是一个小项目,我不能使用 int[](比方说)代替 Integer[],以便使用 Arrays.copyOf() 方法复制数组 A[] 的内容。提前致谢,请原谅我的语法/拼写错误。

请注意,输入数组始终是 2 的幂(2、4、8、16 等),因此每次除以 2 以找到中间元素的索引时,我总是得到一个偶数。

4

2 回答 2

2

我认为你的问题在这里:

if(i == lIndex)

检查列表中的元素是否用完的方法是:

if (lIndex == left.length)

In other words, if you take some elements from the left and some from the right, even if you exhaust the left array first, i will NOT be equal to lIndex when you've exhausted the left array. It will be greater.

于 2013-03-31T01:57:12.127 回答
1

据我所知,问题出在您的合并方法中,这里:

if (i == lIndex) { // If the left array is sorted ...

i不一定等于lIndex左数组排序的时候。结果,并不总是执行合并的最后部分。您看到的重复元素是从原始数组A中遗留下来的,因此没有被覆盖。

正确的条件是:

if (lIndex == left.length) { // If the left array is sorted ...
于 2013-03-31T01:56:22.197 回答