递归操作的顺序是什么? [英] What is the sequence of actions at a recursion?

问题描述

我试图理解合并排序算法的Java代码，但我确实停留在拆分阶段.完整代码在这里:

I am trying to understand a merge sort algorithm java code but I really stuck at the splitting phase. Full code is here:

public class Main {

    public static void main(String[] args) {
        int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

        mergeSort(intArray, 0, intArray.length);

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

    // { 20, 35, -15, 7, 55, 1, -22 }
    public static void mergeSort(int[] input, int start, int end) {

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

        int mid = (start + end) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid, end);
        merge(input, start, mid, end);
    }

    // { 20, 35, -15, 7, 55, 1, -22 }
    public static void merge(int[] input, int start, int mid, int end) {

        if (input[mid - 1] <= input[mid]) {
            return;
        }

        int i = start;
        int j = mid;
        int tempIndex = 0;

        int[] temp = new int[end - start];
        while (i < mid && j < end) {
            temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
        }

        System.arraycopy(input, i, input, start + tempIndex, mid - i);
        System.arraycopy(temp, 0, input, start, tempIndex);
    }
}

使用以下mergeSort方法:

public static void mergeSort(int[] input, int start, int end) {

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

    int mid = (start + end) / 2;
    mergeSort(input, start, mid);
    mergeSort(input, mid, end);
    merge(input, start, mid, end);
}

有两个递归调用mergeSort和一个merge调用，那么此方法的操作顺序是什么?如何在没有任何额外变量的情况下进行拆分以保持未排序的未排序数据呢?

there are two recursive calls to mergeSort and one merge call, so what is the sequence of actions at this method and how splitting could be done without any extra variables for keeping divided unsorted data?

推荐答案

使用[]表示拆分，| |. |对于单次运行，{}用于合并运行.这是顺序:

Using [ ] to indicate splits, | | for single runs, { } for merged runs. This is the order:

                                        level of recursion
[ 20   35  -15    7   55    1  -22]     0
[ 20   35  -15]                         1
| 20|                                   2
     [ 35  -15]                         2
     | 35|                              3
          |-15|                         3
     {-15   35}                         2
{-15   20   35}                         1
               [  7   55    1  -22]     1
               [  7   55]               2
               |  7|                    3
                    | 55|               3
               {  7   55}               2
                         [  1  -22]     2
                         |  1|          3
                              |-22|     3
                         {-22    1}     2
               {-22    1    7   55}     1
{-22  -15    1    7   20   35   55}     0

这篇关于递归操作的顺序是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！