为什么归并排序的 Merge() 函数有一个条件第二个循环？

Question

merge1(int low, int high, int S[], U[]) 
{ 
    int k = (high - low + 1)/2
    for q (from low to high) U[q] = S[q]
    int j = low 
    int p = low 
    int i = low + k 

    while (j <= low + k - 1) and (i <= high) do 
    { 
        if ( U[j] <= U[i] ) 
        {
            S[p] := U[j] 
            j := j+1
        } 
        else 
        { 
            S[p] := U[i] 
            i := i+1 
        } 
        p := p+1 
    } 

    if (j <= low + k - 1) 
    { 
        for q from p to high do 
        { 
            S[q] := U[j] 
            j := j+1 
        } 
    }
}


merge_sort1(int low, int high, int S[], U[]) 
{ 
    if low < high 
    { 
        int k := (high - low + 1)/2 
        merge_sort1(low, low+k-1, S, U) 
        merge_sort1(low+k, high, S, U) 
        merge1(low, high, S, U) 
    } 
}

所以，基本上，这是我的课堂笔记。我发现它总体上很混乱，但我理解其中最重要的部分。我不明白的是“if (j <= low + k - 1)”部分的需要。看起来它检查左侧部分是否有任何“剩余”元素。合并排序时这可能吗？

Answer 1

合并两个排序列表（我们称其为 left 和 right）时，您会不断取出一项并将其添加到 result 列表中，直到您left 或 right 列表中的项目已用完。这是由第一个 while 循环完成的。现在您需要将左侧或右侧列表中剩余的元素添加到结果列表中。有两个选项：

• 左边的列表没有元素，右边的列表还有一些。按照此处编写代码的方式，我们不需要执行任何操作，因为 S 数组的末尾已经包含 right 列表中的最后一个元素。 p>

• 右边的列表已经没有元素了，左边的列表还有一些。然后我们将剩余的元素复制到S的末尾。这就是 merge1 末尾的 if 的作用。

---

关于您的问题此代码是否“不好”：代码是正确的，但我会进行一些更改以使其更具可读性：

• 描述性变量名称。
• 将分隔 left 和 right 列表的中点传递给 merge1，而不是重新计算。