C堆栈中的递归

一尘不染

C堆栈中的递归

algorithm

这是在归类排序中划分的代码..am无法真正理解重新存储在其中的工作方式！

合并排序分区

void partition(int arr[], int low, int high){
    int mid;
    if(low < high){
         mid = (low + high)/2;
         partition(arr, low, mid);
         partition(arr, mid + 1, high);
         mergeSort(arr, low, mid, high);
    }
}

实际上在很多递归问题中陷入了混乱，无法理解系统堆栈在递归中的工作方式…是一个初学者。

阅读 248

2020-07-28

共1个答案

一尘不染

让我们举一个例子

数组arr ={ 5,2,4,7,1,3,2,6};8个元素

                            1 2 3 4 5 6 7
                                  ^(partition+mergeSort)
                                  |  
                    +------------+ +---------------+
                    |                              |
                2 4 5 7                          1 2 3 6
                    ^   (partition+mergeSort)        ^ (partition+mergeSort)  
                    |                              |
                +--+ +---+                     +--+ +---+
                |        |                     |        |
               2  5     4  7                 1   3     2  6
                     ^ (partition+mergeSort)          ^  (partition+mergeSort) 
                     |                              | 
                +---+ +---+                    +---+ +---+
                |         |                    |         |
              5   2     4   7                1  3      2   6 
                 4 elements                      4 elements

                          Initial Unsorted Array

从下到上，形成两个阵列

arr[low...mid]并 arr[mid+1...high]在每个递归调用上，最后它们都被合并。

只要low<high

它只是一个示例，说明如何mergeSort在这里工作，您可以在此示例中遵循代码。

partition(arr, 0,7)对该未排序数组进行的调用将具有：

初次mid =3 arr使用时分为两部分

partion(arr,0,3) 和 partion(arr,4,7)

这些分区中的每个分区又被拆分为两个部分，即0到3划分为(0,1)＆(2,3)，再进一步是(0,1)和(1,1)。(1,1)由于`low

high最后2个元素与合并而被跳过mergeSort`

一组如此小的排序数组随后在后续遍历中从递归中合并出来时最终合并在一起。

这在这里很难解释，以文本格式在纸上尝试一下，我相信您可以用更大的数组（例如4个元素）弄清楚。

2020-07-28