如何实现合并排序？

Question

我正在尝试实现递归合并排序，但该方法只在排序后的向量中写入零。这是我的代码。在主函数中，我只是将值读入一个向量并将其作为参数传递给合并排序。关于我做错了什么的任何想法？谢谢。

public static void mergesort(int []  v){
int mid=v.length/2;

if( v.length < 2)
    return;

int l[]=new int [mid];
int r[] = new int [v.length-mid];

for(int i=0; i<mid-1; i++)
    l[i]=v[i];

for(int i=mid; i<v.length-1; i++)
    r[i-mid]=v[i];

mergesort(l);
mergesort(r);
mergesort(l,r,v); 


}

public static void mergesort(int [] l, int [] r, int [] v){
int i=0, j=0, k=0;

while(i< l.length && j< r.length){

    if(l[i] <= r[j]){
    v[k]=l[i];
    i++;
    }
    else{
    v[k]=r[j];
    j++;
    }
k++;
}

while(i < l.length){
    v[k]=l[i];
    i++;
    k++;
}

while(j< r.length){
    v[k]=r[j];
    j++;
    k++;
}
}

Answer 1

算法有两个错误。

错误一：

while (i < r.length && j < r.length) {
    if (l[i] <= r[j]) {
        v[k] = l[i];
        i++;
    } else {
        v[k] = r[j];
        j++;
    }
    k++;
}

这里的i必须小于l.length。这就是 ArrayIndexOutOfBoundsException 的原因 if l.length != r.length.

错误 2：

for (int i = 0; i < mid - 1; i++)
    l[i] = v[i];

for (int i = mid; i < v.length - 1; i++)
    r[i - mid] = v[i];

i 的范围必须是 0 到 (mid - 1)。所以 for 循环应该在两个地方都使用 <= 运算符，如下所示：

for (int i = 0; i <= mid - 1; i++)
    l[i] = v[i];

for (int i = mid; i <= v.length - 1; i++)
    r[i - mid] = v[i];

这就是得到零的原因。

修改后的代码如下：

public static void mergesort(int []  v) {
    int mid = v.length / 2;

    if ( v.length < 2)
        return;

    int l[] = new int [mid];
    int r[] = new int [v.length - mid];

    for (int i = 0; i <= mid - 1; i++)
        l[i] = v[i];

    for (int i = mid; i <= v.length - 1; i++)
        r[i - mid] = v[i];

    mergesort(l);
    mergesort(r);
    mergesort(l, r, v);
}

public static void mergesort(int [] l, int [] r, int [] v) {
    int i = 0, j = 0, k = 0;

    while (i < l.length && j < r.length) {
        if (l[i] <= r[j]) {
            v[k] = l[i];
            i++;
        } else {
            v[k] = r[j];
            j++;
        }
        k++;
    }

    while (i < l.length) {
        v[k] = l[i];
        i++;
        k++;
    }

    while (j < r.length) {
        v[k] = r[j];
        j++;
        k++;
    }
}

Answer 2

假设你输入一个大小为2的向量；然后根据你的代码

mid=1;

for(int i=0;i<mid-1;i++)

// here   i < (1-1)   which will never execute

    l[i]=v[i];

如何实现合并排序？

How to implement mergeSort?

java

sorting

mergesort