Java Merge Sort не дает благоприятного результата - PullRequest
Новая
       11

Java Merge Sort не дает благоприятного результата

0 голосов
/ 06 января 2019

Я новичок в Java. Это мой код для сортировки слиянием, но он не дает мне благоприятных результатов. Может кто-нибудь объяснить, пожалуйста, какую ошибку я совершил? 

public class Test {

public int arr[] = {5,7,8,4,3,2,6,1};

public static void main(String args[]) {
    Test t = new Test();
    System.out.println("Before sorting"+ Arrays.toString(t.arr));
    t.mergeSort(t.arr);
    System.out.println("After Sorting"+ Arrays.toString(t.arr));

}


public void mergeSort(int[] a){
    int n = a.length;
    if(n < 2)
        return;
    int m = n/2;
    int[] left = new int[m];
    int[] right = new int[n - m];
    for(int i = 0;i < m;i++) {
        left[i] = a[i];
    }
    for(int i = m;i < n;i++) {
        right[i - m] = a[i];
    }
    mergeSort(left);
    mergeSort(right);
    merge(left,right,arr);
}

private void merge(int[] left, int[] right, int[] arr2) {
    int n = left.length;
    int m = right.length;
    int i=0,j=0, k=0;
    while(i < n && j < m) {
        if(left[i] < right[j]) {
            arr2[k] = left[i];
            i++;
            k++;
        }
        else {
            arr2[k] = right[j];
            j++;
            k++;
        }

    }
    while(i<n) {
        arr2[k] = left[i];
        i++;
        k++;
    }
    while(j<m) {
        arr2[k] = right[j];
        j++;
        k++;
    }


}
}

Я не получаю отсортированный массив после реализации вышеуказанной программы. Похоже, он не возвращает объединенный массив. Я не могу выяснить проблему, и любая помощь будет оценена.

1 Ответ

0 голосов
/ 06 января 2019

Ваша проблема в том, что после mergeSort (слева) и mergeSort (справа) левая и правая стороны фактически не сортируются, потому что массив arr - единственное, что на самом деле изменяется на этапе слияния.

Как правило, вы реализуете MergeSort, используя только один массив и передавая соответствующие начальный и конечный индексы для части массива, с которой вы работаете, на каждом этапе слияния или рекурсии.

Тогда у вас будет что-то вроде mergeSort (int [] a, int leftIndex, int rightIndex), а mergeSort (a, 0, a.length-1) будет сортировать полный массив a.

...