java - 难以理解合并排序算法的合并部分

Question

我在理解合并排序算法的“合并”部分时遇到了一些麻烦，因为我试图在上下文中理解算法的某些部分，而某些变量/循环对我。我了解递归除法过程和合并的排序方面，但在这个特定的合并算法中:

    public static void merge(int data[], int temp[], int low, int middle, int high){
    int ri=0; //result index
    int ti=low;//temp index
    int di=middle;//data index
    int[] result = new int[high-low+1];

    while (ti<middle && di<=high){
      if (data[di]<temp[ti]){
        result[ri++] = data[di++];//smaller is in data
       } 
       else{
            result[ri++] = temp[ti++];//smaller is in temp
            }
    } 

while(ti<middle) result[ri++]=temp[ti++];
while(di<=high) result[ri++]=data[di++];
for(int i=0;i<high;i++) data[low+i]=result[i];

我不明白最后 3 个循环:

while(ti<middle) result[ri++]=temp[ti++];
while(di<=high) result[ri++]=data[di++];
for(int i=0;i<high;i++) data[low+i]=result[i];

您能否解释这 3 个循环在合并上下文中的作用，以及任何进一步的建议以更好地理解合并排序算法的合并部分？

Answer 1

这个循环的条件while (ti<middle && di<=high)意味着一旦两半中至少有一个没有更多元素，它就会终止。但是另一个中仍然可以有一些元素。这就是为什么我们需要这两行:

while(ti<middle) result[ri++]=temp[ti++]; // Remaining elements from the first half.
while(di<=high) result[ri++]=data[di++]; // Remaining elements from the second half.

现在我们需要将合​​并的结果复制到原数组中。这正是最后一行所做的。

关于合并阶段的理解:你理解算法本身吗(数学意义上的，不涉及任何具体的编程语言)？如果你不这样做，那就先尝试在不看任何代码的情况下完全理解它。如果您确实了解算法但不了解这段代码，那很好，因为这段代码非常糟糕。

你可以看一下更清晰的实现:

mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = 
    let (firstHalf, secondHalf) = splitAt (length xs `div` 2) xs
    in merge (mergeSort firstHalf) (mergeSort secondHalf)  

merge xs [] = xs
merge [] ys = ys
merge xs@(x:xt) ys@(y:yt) 
    | x <= y = x : merge xt ys
    | otherwise = y : merge xs yt