递归在C叠 [英] recursion in c stacks
问题描述
这里是code。在合并sort..am无法进行分区,以真正了解如何recusrion工作在它!
here is the code to partition in merge sort..am not able to understand actually how does recusrion works in it!!
归并排序划分
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);
}
}
其实我得到搞砸了许多递归问题,我不能够理解如何做系统堆栈作品递归... 是一个初学者。
actually am getting messed up in many recursive problems and am not able to understand how does system stack works in recursion... am a beginner..
推荐答案
让我们的例子
阵列 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
从下
转至顶部,两个阵列形成有
Go from bottom to top, two arrays are formed with
改编[低... MID]
和
改编[中等+ 1 ...高]
每个递归调用,最后他们都得到合并。
arr[low...mid]
and
arr[mid+1...high]
on each recursive calls, and finally they both get merged.
分区和放大器;合并过程将继续,只要低
&LT; 高
Partitioning & Merging process continues as long as low
< high
它只是一个例子,说明归并
正在这里,你可以按照code这个例子。
Its just an example how mergeSort
is working here, you can follow the code with this example.
与调用分区(ARR,0,7)
这个排序的数组将有:
A call with partition(arr, 0,7)
on this unsorted array will have :
在第一遍中期= 3
改编
被分成2部分使用
On first pass mid =3
arr
gets divided into 2 parts using
partion(ARR,0,3)
和 partion(ARR,4,7)
每个这些分区再次吐尽分为两个部分,即0至3被分为(0,1)
&放大器; (2,3)
,再进一步(0,1)
和(1,1 )
。 (1,1)
被跳过的低&GT;高
这最后的2个元素被合并了归并
Each of those partitions are again spitted up into two parts i.e for 0 to 3 gets divided into (0,1)
& (2,3)
, further again (0,1)
and (1,1)
. (1,1)
is skipped as low > high
this last 2 elements are merged up with mergeSort
一组这样的小排序的数组被最后合并起来,因为它出来递归在随后的通行证。
A group of such small sorted array are then finally merged up as it comes out of recursion on subsequent passes.
这是有点难以解释这里,以文字形式,尝试在纸上,我敢肯定,你自己看着办吧,有更小的数组,表示为4个元素。
This is bit difficult to explain here, in textual format, try it on paper,I'm sure you can figure it out, with even more smaller array, say for 4 elements.
这篇关于递归在C叠的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!