归并排序中的递归

Question

public static void main(String[] args) {
    int[] numbers = {20,4,7,6,1,3,9,5};
    mergeSort(numbers);
}
private static void mergeSort(int[] inputArray) {
    int inputLength = inputArray.length;
    System.out.println(inputLength);

    if (inputLength < 2)
        return;


    int midIndex = inputLength / 2;

    int[] leftHalf = new int[midIndex];
    int[] rightHalf = new int[inputLength - midIndex];

    for (int i = 0; i < midIndex; i++) {
        leftHalf[i] = inputArray[i];

    }
    for (int i = midIndex; i < inputLength; i++) {
        rightHalf[i - midIndex] = inputArray[i];

    }

    mergeSort(leftHalf);
    mergeSort(rightHalf);
    merge(inputArray, leftHalf, rightHalf);

}
private static void merge(int[] inputArray, int[] leftHalf, int[] rightHalf) {
    int leftSize = leftHalf.length;
    int rightSize = rightHalf.length;

    int i = 0, j = 0, k = 0;

    while (i < leftSize && j < rightSize) {
        if (leftHalf[i] <= rightHalf[i]) {
            inputArray[k] = leftHalf[i];
            i++;
        } else {
            inputArray[k] = rightHalf[j];
            j++;
        }
        k++;
    }
    while (i < leftSize) { //eğer karşılaştırılmayan bir tane kalırsa diye yapılıyor yani 
        inputArray[k] = leftHalf[i];
        i++;
        k++;
    }
    while (j < rightSize) {
        inputArray[k] = rightHalf[j];
        j++;
        k++;
    }

}

在 mergeSort 部分中，如果 inputLength 2部分代码，当长度小于2时我们返回。而上次inputLength是1，它变成2并返回数组[20,4 ]。

从逻辑上讲，这对我来说没有意义。当最后剩下 [20] 时，它如何回到 [20,4] ？

Answer 1

首先你分享的代码在合并功能部分有缺陷，你可以在网上找到适合合并排序的代码，你可以参考
https://www.geeksforgeeks.org/java-program-for-merge -sort/

现在为了理解合并排序，您必须了解堆栈（后进先出）和堆栈的概念。递归。在递归中，递归调用之后的行会等待，直到对函数的递归调用尚未完全执行。因此，在第一次调用合并排序的情况下，

数组的长度为 n，并等待大小为 (n/2) 的 mergeSort(leftHalf) 和 mergeSort(rightHalf) 的完整执行。

现在对于 mergeSort(leftHalf) 和 mergeSort(rightHalf)
将会有子左部分和子右部分，这将持续到数组的大小变得<2并且剩余部分将等待。

成功执行最小部分后，它将返回到调用该部分的上一个部分。最终这将返回到第一次调用该函数的地方。

在您的代码中，两个较小的数组都会合并到较大的数组中，因此左右子数组的数据不会丢失。