递归部分解释

我被合并排序递归部分卡住了。递归部分解释

void divide(int arr[], int low, int high) { 

int mid; 

if(low < high) { 
    mid = (low + high)/2; 
    divide (arr, low, mid); 
    divide (arr, mid+1, high); 
    numbersSort (arr, low, mid, high); 
    } 
}

假设数组大小为4。第一时，它将由分别divide(arr,0,4)然后divide(arr,0,2)，divide(arr,0,1)，divide(arr,0,0)被调用。但是一说到divide(arr,0,0)就应该停在低位<高位。那么如何分工和numberSort()函数？

我有另一个查询问，什么时候numberSort（）工作？如果你可以通过模拟上面的代码给我一行一行，我会感激你的。我对此感到非常恐慌。高级谢谢。

来源

2015-10-17 Rana

为什么你不能使用调试器来查看代码的行为？ –

@rana如上所示，使用调试器。如果您对编码真的很陌生，并且不知道如何使用它，请先尝试在每行之后添加打印件。这将有助于您快速了解代码。然后查看GDB手册或类似的东西来学习调试 – knightrider

http://wiki.codeblocks.org/?title=Debugging_with_Code:Blocks –

示例自顶向下合并排序divide（）函数只是保持调用自身，直到子数组大小减小到1，在这种情况下，可以将大小为1的子数组视为排序。只有这样，才开始实际的合并，在分割（arr，0,0）和分割（arr，1,1）之后开始，然后不做任何事情。 numbersSort（）然后合并arr [0]和arr [1]，然后返回。下一个合并发生在分割（arr，2,2）和分割（arr，3,3），合并arr [2]和arr [3]之后。然后在返回之后，arr [0 1]和arr [2 3]被合并，产生一个由4个整数组成的有序数组。请注意，所有划分都会生成索引对（低，高），numbersSort（）是实际合并数据的位置。

一般来说，自顶向下归并排序是一个深度优先，左先排序。非迭代自底向上合并排序跳过用于生成索引的所有递归，并且通过偶数和奇数索引合并开始，将[0]与[1]，[2]和[3]，[4]合并为[ 5]，...。然后在下一个过程中合并大小为2的运行，[0 1]与[2 3]，[4 5]与[6 7]合并，等等，直到数组合并为止。

传递与待排序数组大小相同的临时数组可以用来消除在合并排序期间创建，复制和删除工作数组。

范例显示自顶向下的归并排序操作的顺序：操作

7 4 2 5 3 0 6 1 
7 4 2 5|3 0 6 1 
7 4|2 5 
7|4 
4 7 
    2|5 
    2 5 
2 4 5 7 
     3 0|6 1 
     3|0 
     0 3 
      6|1 
      1 6 
     0 1 3 6 
0 1 2 3 4 5 6 7

范例显示自下而上归并排序顺序：

7 4 2 5 3 0 6 1 
7|4|2|5|3|0|6|1   run size = 0 
4 7|2 5|0 3|1 6   run size = 1 
2 4 5 7|0 1 3 6   run size = 4 
0 1 2 3 4 5 6 7   done

来源

2015-10-17 18:57:21 rcgldr

那么它是如何分裂和numberSort（）函数的工作？

当您调用另一个函数时，给定函数中的执行不会停止，它只会暂停，直到该函数返回。所以想象你目前正在执行divide(arr,0,1)。 low仍然小于high，所以你输入条件并致电divide(arr,0,0)，它可以做任何它需要做的事情（提示：尽量不要担心它现在所做的事情），然后你打电话给divide(arr,1,1)，这又是它的事情，并返回。接下来，你调用numbersSort(arr,0,0,1)，它重新组合了数组的两部分，结果是该数组从索引0到索引1排序。

好到目前为止？好吧，接下来你就回来。和它发生的divide(arr,0,1)调用刚才我们谈到是由divide(arr,0,2)调用来调用，所以当divide(arr,0,1)回报的divide(arr,0,2)执行刚刚divide(arr,0,1)后从点继续进行。所以接下来的事情将是divide(arr,2,2)电话，对吧？ 2不小于2，因此只需立即返回，然后点击numbersSort(arr,0,1,2)，即将数组的两部分（即0到1和2到2）组合到一个从0到正确排序的数组中2.现在的阵列从指数0到索引2

但排序，当然，这divide(arr,0,2)被称为在divide(arr,0,4)调用的上下文，所以当divide(arr,0,2)返回发生的divide(arr,3,4)接下来的事情。让我们假设，做正确的事情，从排序索引3索引4的数组，然后你到了numbersSort(arr,0,2,4)，该阵列的两个部分，并返回结合，任何函数调用divide(arr,0,4)。

绝对可以硬朗首先要解决递归你的头。保持它 - 它会最终点击。如果您可以在调试器中逐步查看代码，可以帮助您了解发生了什么。此外，通过纸上的代码工作可以提供帮助。尽量不要理解它是如何在一个层次上同时运行的，而是要寻找单个层次上发生的事情，并相信调用任何函数（甚至是递归调用）只是做正确的事情。

来源

2015-10-17 15:17:57 Caleb

递归部分解释

回答

相关问题