Алгоритм сортировки слиянием не полностью объединяется. Правая сторона массива не сливается с левой стороной - PullRequest
Новая
       7

Алгоритм сортировки слиянием не полностью объединяется. Правая сторона массива не сливается с левой стороной

0 голосов
/ 08 мая 2018

Итак, я пытаюсь реализовать алгоритм MergeSort для массива.

Мой несортированный массив: [3, -5, -10, 22, -100, 1]

Однако при выполнении это [-5, -10, 3, 22, -100, 1]

Понятно, что правая сторона позиций массива 4 и 5 явно не сливается.

Я подумал, что, возможно, я не разделил массив полностью, и поэтому он не сливается правильно.

Ниже мой код сортировки слияния: 

public static void main(String[] args) {
    // TODO Auto-generated method stub

    int [] arr = {3, -5, -10, 22, -100, 1};
    System.out.println("unsorted array is" +Arrays.toString(arr));

    mergeSort(arr, 0, arr.length);

    System.out.println("it is now merged "+ Arrays.toString(arr));
}


public static void mergeSort(int[] arr, int start, int end) {
    // TODO Auto-generated method stub

    if(end -start < 2) {
        return;
    }

    int mid = (start + end)/2;

    //merge the left side of array
    mergeSort(arr, start, mid);

    //merge the right side of the array
    mergeSort(arr,mid +1, end);

    merge(arr, start, mid, end);
}

public static void merge(int [] arr, int start, int mid, int end) {

    //checking
    if(arr[mid -1] <= arr[mid]) {
        return;
    }

    if(start <= end && mid >= start && mid <= end) {

    //creating temporary array
    int [] temp = new int[end -start + 1];

    //initialising values
    int i = start;
    int j = mid;
    int tempIndex = 0;

    while(i < mid && j < end + 1) {
        if(arr[i] > arr[j]) {
            temp[tempIndex] = arr[j];
            j++;
        }

        else {
            temp[tempIndex] = arr[i];
            i ++;
        }
        tempIndex ++;
    }

    //exit while loop

    if(i < mid) {
        //if that is true then loop
        for(; i< mid; i++) {
            temp[tempIndex] = arr[i];
            tempIndex ++;
        }
    }

    else {
        for(;j < end +1; j++) {
            temp[tempIndex] = arr[j];
            tempIndex ++;
        }
    }

    //copy back into array

    for (int k = start;k <= end; k++) {
        arr[k] = temp[k-start];
    }

    }
}}

1 Ответ

0 голосов
/ 08 мая 2018

Исправьте две вещи: В основном: 

mergeSort(arr, 0, arr.length);

до: 

mergeSort(arr, 0, arr.length-1);

и в методе mergeSort 

//merge the right side of the array
mergeSort(arr, mid+1, end);

до: 

//merge the right side of the array
mergeSort(arr, mid, end);

Дело в том, что вы всегда предоставляете больше элементов, которые имеет массив (элементы считаются от 0 до arr.length-1), и чем вы пропускаете последнее деление в рекурсивном дереве, когда элементы в разделяющем массиве четные. (Таким образом, вы пропускаете слияние правой части массива)

...