我正在研究在合并排序中使用递归的控制流。
我使用的特定算法是：
MergeS(ar, p, r){
1. if p<r{
2. k = floor[(p+r)/2]
3. MergeS(ar, p , k)
4. MergeS(ar, k+1, r) //in the schematic diagram I have written this as mergeS(,,)
5. Merge(ar, p ,k, r)
6. }
7.}
Merge(ar, p, k, r){
8. n1 = k-p+1
9. n2 = r-p
10. let L[1...n1+1] and R[1....n2+1] be new arrays
11. for i=1 to n1
12. L[i] = ar[p+i-1]
13. for j=1 to n2
14. R[j] = ar[k+j]
15. L[n1+1] = Infinity
16. R[n2+1] = Infinity
17. i = 1
18. j = 1
19. for t = p to r
20. if L[i] <= R[j]
21. A[t] = L[i]
22. i = i+1
23. else
24. A[t] = R[j]
25. j = j+1
30. }
MergeS(ar, k+1, r)与merge(ar, k+1, r)完全相同。我在后者中使用了小写m，只是为了在逻辑示意图中提供更好的视觉清晰度。
为了理解，我举了一个数组的例子——43、32、56、12、4。
递归调用的流程示意性地显示在下面，直到对 Merge 进行第一次调用并执行该块中的代码。
---1：合并S(ar， 0， 5)-----
if(0<5):true ; set k=(0+5)/2
---暂停 1：MergeS(ar， 0，5)-----Call-->2：MergeS(ar， 0， 2)---------
if(0<2):true ; set k=(0+2)/2
---暂停 2：合并S(ar， 0， 2)-----呼叫-->3：合并S(ar， 0， 1)---------
if(0<1):true ; set k=(0+1)/2
---暂停 3：MergeS(ar， 0，1)-----Call-->4：MergeS(ar，0， 0)---------
if(0<0):false
---简历 3：合并S(ar， 0， 1)-----呼叫-->5：合并S(ar， 0+1， 5)---------
if(1<5):true ; set k=(1+5)/2
---暂停 5：mergeS(ar， 0+1， 5)-----Call-->6：MergeS(ar， 1， 3)---------
if(1<3):true ; set k=(1+3)/2
---暂停 6：MergeS(ar， 1，3)-----Call-->7：MergeS(ar， 1， 2)---------
if(1<2):true ; set k=(1+2)/2
---暂停 7：MergeS(ar， 1，2)-----Call-->8：MergeS(ar，1， 1)---------
if(1<1):false
---简历 7：合并S(ar， 1， 2)------呼叫-->9：合并S(ar， 1+1， 5)---------
if(2<5):true ; set k=(2+5)/2
---暂停 9：mergeS(ar， 2， 5)--------Call-->10：Merge(ar， 2， 3)---------
if(2<3):true ; set k=(2+3)/2
---暂停 10：合并(ar， 2， 3)-------呼叫-->11：合并(ar， 2， 2)----------
if(2<2):false
---简历 10：合并S(ar， 2， 3)-----呼叫-->12：合并S(ar， 2+1， 5)----------
if(3<5):true ; set k=(3+5)/2
---暂停 12：mergeS(ar， 2+1， 5)------Call-->13：MergeS(ar， 5， 5 )---------
if(5<5):false
---简历 12：合并S(ar， 2+1， 5)-------呼叫-->合并(ar， 3， 4， 5)----------
n1 = 4-3+1=2
n2 = 5-4=1
for(i = 0 to i=1):
iteration1:
L[0] = ar[3+0-1]= ar[2] //value 56 is assigned to ar[2]
iteration2:
L[1] = ar[3+1-1] = ar[3] //value 12 is assigned to ar[3]
for(j=0 to j=0):
iteration1:
R[0] = ar[4+0] = ar[4] //value 4 is assigned to ar[4]
x = 0;
y = 0;
for(t=0 to t=1):
iteration1:
/* if(L[0]<= R[0]) //56<=4:false */
else
ar[0] = R[0] //4 is assigned to ar[0]
y = y+1
iteration2:
if(L[0]<=R[1]): //56<=infinity
ar[1] = L[0] // 56 is assigned to ar[1]
在上一步之后，我在ar[0]中获得了一个值4，在ar[2]中获得了一个值56。我的猜测是这是错误的。
我需要帮助了解我哪里出错了，并对此做出解释。
问题中算法中的索引需要在代码中修改以简化使用。我并不是说算法是错误的，它是绝对正确的，只需要修改。
调整后的Merge代码：
private static void Merge(int[] ar, int p, int k, int r) {
int n1 = k-p+1;
int n2 = r-k;
int[] L = new int[n1+1];
int[] R = new int[n2+1];
for(int i=0; i<n1; i++){
L[i] = ar[p+i]; // p+i and not p+i-1
}
for(int i=0; i<n2; i++){
R[i] = ar[k+i+1]; //k+1+i and not k+i
}
// Use of Tnteger.MAX_VALUE
L[n1]=Integer.MAX_VALUE;
R[n2]=Integer.MAX_VALUE;
int i = 0;
int j = 0;
for(int t=p; t<=r; t++){ //carefully set initialization and t<=r and not simply t<r
if(L[i]<r[j]){
ar[t] = L[i];
i++;
}
else{
ar[t] = R[j];
j++;
}
}
}
}
递归调用的正确流程如下所示：(上述控制图流程的变化为斜体)
---1：合并S(ar， 0， 5)-----
if(0<5):true ; set k=(0+5)/2
---暂停 1：MergeS(ar， 0，5)-----Call-->2：MergeS(ar， 0， 2)---------
if(0<2):true ; set k=(0+2)/2
---暂停 2：合并S(ar， 0， 2)-----呼叫-->3：合并S(ar， 0， 1)---------
if(0<1):true ; set k=(0+1)/2
---暂停 3：MergeS(ar， 0，1)-----Call-->4：MergeS(ar，0， 0)---------
if(0<0):false
---中断 4：合并S(ar， 0， 0)-----呼叫-->5：合并S(ar， 0+1，1)---------
if(1<_1_):_false_ ;
---中断 5：合并S(ar， 0+1，1)-----调用-->合并(ar，0,0,1)
在执行Merge参数ar, 0, 0, 1的函数后，数组43 32 56 12 4的前两个索引处的元素被交换。
维护一堆函数调用派上用场。