Сортировка слиянием возвращает массив размера 1, содержащий "0" вместо отсортированного массива.

Question

Я пытался исправить это, но пока безуспешно. Я впервые имею дело с алгоритмами сортировки для академических c целей, поэтому я, вероятно, где-то допустил простую ошибку; Однако я не смог понять это.

    private int[] mergeAndDivide(int[] array) {
        if (array.length < 2)
            return array;
        int[] arrayOne = Arrays.copyOfRange(array, 0, (array.length - 1) / 2);
        int[] arrayTwo = Arrays.copyOfRange(array, ((array.length - 1) / 2 + 1), (array.length - 1));
        arrayOne = mergeAndDivide(arrayOne);
        arrayTwo = mergeAndDivide(arrayTwo);
        return merge(arrayOne, arrayTwo);
    }

    private int[] merge(int[] arrayOne, int[] arrayTwo) {
        int[] arrayMerged = new int[arrayOne.length + arrayTwo.length];
        int i = 0;
        while (i <= arrayOne.length - 1 && i <= arrayTwo.length - 1) {
            if (arrayOne[i] > arrayTwo[i])
                arrayMerged[i] = arrayTwo[i];
            else
                arrayMerged[i] = arrayOne[i];
        }
        int x = i;
        while (i <= arrayOne.length - 1) {
            arrayMerged[i + arrayTwo.length - 1] = arrayOne[i];
            i++;
        }
        i = x;
        while (i <= arrayTwo.length - 1) {
            arrayMerged[i + arrayOne.length - 1] = arrayTwo[i];
            i++;
        }
        return arrayMerged;
    }

Answer 1

В подпрограмме деления аргумент Arrays.copyOfRange the to является исключительным, что означает, что он не будет включать индекс to в результат. Точно так же в подпрограмме слияния вы должны использовать 2 переменные для итерации двух массивов, и я изменил <= на <в большинстве мест, потому что IMO выглядит чистым. </p>

import java.util.Arrays;

class Solution {
    private static int[] mergeAndDivide(int[] array) {
        if (array.length < 2) return array;
        int[] arrayOne = Arrays.copyOfRange(array, 0, ((array.length - 1) / 2) + 1); // the final index is exclusive meaning it will not be included in the bisected array
        int[] arrayTwo = Arrays.copyOfRange(array, ((array.length - 1) / 2 + 1), array.length);
        arrayOne = mergeAndDivide(arrayOne);
        arrayTwo = mergeAndDivide(arrayTwo);
        return merge(arrayOne, arrayTwo);
    }

    private static int[] merge(int[] arrayOne, int[] arrayTwo) {
        int[] arrayMerged = new int[arrayOne.length + arrayTwo.length];
        int i = 0;
        int j = 0;
        while (i < arrayOne.length && j < arrayTwo.length) { // you need 2 variables to index first and second array;
            if (arrayOne[i] > arrayTwo[j]) {
                arrayMerged[i + j] = arrayTwo[j];
                j++;
            } else {
                arrayMerged[i + j] = arrayOne[i];
                i++;
            }
        }

        while (i < arrayOne.length) {
            arrayMerged[i + j] = arrayOne[i];
            i++;
        }
        while (j < arrayTwo.length) {
            arrayMerged[i + j] = arrayTwo[j];
            j++;
        }
        return arrayMerged;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(mergeAndDivide(new int[]{3, 4, 5, 6, 1})));
    }
}


Result : [1, 3, 4, 5, 6]

Answer 2

Второй аргумент Arrays.copyOfRange() - это индекс первого элемента после конца среза. Используйте для этого array.length / 2 и то же значение, что и начальный индекс для второго фрагмента.

Аналогичным образом используйте < и не настраивайте длину в методе слияния. Есть еще одна ошибка: вы используете один и тот же индекс i в arrayOne, arrayTwo и arrayMerged, вы должны использовать другой индекс в каждом из массивов аргументов и в объединенном массиве.

Вот модифицированная версия:

    private int[] mergeAndDivide(int[] array) {
        if (array.length < 2)
            return array;
        int[] arrayOne = Arrays.copyOfRange(array, 0, array.length / 2);
        int[] arrayTwo = Arrays.copyOfRange(array, array.length / 2, array.length);
        arrayOne = mergeAndDivide(arrayOne);
        arrayTwo = mergeAndDivide(arrayTwo);
        return merge(arrayOne, arrayTwo);
    }

    private int[] merge(int[] arrayOne, int[] arrayTwo) {
        int[] arrayMerged = new int[arrayOne.length + arrayTwo.length];
        int i = 0, j = 0, k = 0;
        while (i < arrayOne.length && j < arrayTwo.length) {
            if (arrayOne[i] <= arrayTwo[j])
                arrayMerged[k++] = arrayOne[i++];
            else
                arrayMerged[k++] = arrayTwo[j++];
        }
        while (i < arrayOne.length) {
            arrayMerged[k++] = arrayOne[i++];
        }
        while (j < arrayTwo.length) {
            arrayMerged[k++] = arrayTwo[j++];
        }
        return arrayMerged;
    }

Answer 3

Ваш код logi c не похож на сортировку слиянием. Это правильный код сортировки слиянием:

public static void main(String[] args) {

    int arr[] = {12, 11, 13, 5, 6, 7};

    System.out.println("\nSorted array");
    for(int i=0;i<=arr.length-1;i++){
        System.out.println("Initial Arr element:"+arr[i]);
    }

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

    System.out.println("\nSorted array");
    for(int i=0;i<=arr.length-1;i++){
        System.out.println("Sorted Arr element:"+arr[i]);
    }
}


public static void mergeS(int[] arr,int startI,int endI){
    //System.out.println("StartIndex:"+startI+" EndIndex:"+endI)

    if (startI< endI)
    {
        // Find the middle point
        int m = (startI+endI)/2;

        // Sort first and second halves
        mergeS(arr,startI, m);
        mergeS(arr , m+1, endI);

        // Merge the sorted halves
        merge(arr, startI,m, endI);
    }
}


public static void merge(int arr[], int startI, int midpoint, int endI){
    // Find sizes of two subarrays to be merged
    int n1 = midpoint - startI + 1;
    int n2 = endI - midpoint;

    /* Create temp arrays */
    int L[] = new int [n1];
    int R[] = new int [n2];

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i)
        L[i] = arr[startI + i];
    for (int j=0; j<n2; ++j)
        R[j] = arr[midpoint + 1+ j];


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarry array
    int k = startI;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }

}