Почему эта реализация сортировки слиянием не работает? - PullRequest
Новая
       13

Почему эта реализация сортировки слиянием не работает?

0 голосов
/ 09 марта 2019

Я получил помощь от Здесь , но я особенно не хочу объявлять мои методы как недействительные.Любая помощь будет оценена!

class merges{
public static void main (String args[]){
    int[] A = {10,9,8,7,6,5,4,3,2,1};

    for(int i =0; i< A.length; i++){
        System.out.print(A[i]+" ");
    }
    System.out.println();

    A = mergesort(A,0,A.length-1);

    for(int i =0; i< A.length; i++){
        System.out.print(A[i]+" ");
    }
    System.out.println();
}

static int[] mergesort(int[]A,int l, int r){
    if(l >= r){
        return A;
    }
    else{
        int mid = (l+r)/2;
        mergesort(A,l,mid);
        mergesort(A,mid+1,r);
        return merge(A,l,r);
    }
}

static int[] merge( int[]A, int l, int r){
    int m = (l+r)/2;
    int[]L = new int[m-l+1];
    int[]R = new int[r-m];

    for(int i=0; i<m-l+1; i++ ){
        L[i] = A[l+i];
    }
    for(int i=0; i<r-m; i++ ){
        R[i] = A[m+i+1];
    }

    int i =0;
    int j =0;
    int []B = new int[A.length];
    int k=0;

    while (i<L.length && j<R.length){
        if(L[i]<R[j]){
            B[k] = L[i];
            i++;
        }
        else{
            B[k] = R[j];
            j++;
        }
        k++;
    }

    while(i<L.length){
        B[k] = L[i];
        k++;
        i++;
    }
    while(j<R.length){
        B[k] = R[j];
        k++;
        j++;
    }
    return B;
}
}

Это моя реализация сортировки слиянием, вывод которой я получаю 5 4 3 2 1 10 9 8 7 6.

Может кто-нибудь помочь мне разобраться, как я могу сделатьэта работа?

Я не хочу объявлять методы mergesort и merge как void, я хочу, чтобы они возвращали отсортированный массив.Заранее спасибо.

Ответы [ 2 ]

1 голос
/ 09 марта 2019 
int k=l;

while (i<L.length && j<R.length){
    if(L[i]<R[j]){
        A[k] = L[i];
        i++;
    }
    else{
        A[k] = R[j];
        j++;
    }
    k++;
}

while(i<L.length){
    A[k] = L[i];
    k++;
    i++;
}
while(j<R.length){
    A[k] = R[j];
    k++;
    j++;
}
return A;
1 голос
/ 09 марта 2019

Проблема в том, что ваша функция merge возвращает новый массив, но вы вызываете его так, как будто вы намереваетесь изменить A на месте.

Это можно исправить, скопировав B в A в конце функции merge: 

k = 0;
for(int i=l; i<r; i++ ){
    A[i] = B[k++];
}
...