合并排序算法没有正确合并

Question

因此，我确实知道合并排序应该做什么，而且我现在可以将其可视化。递归拆分直到数组中只剩下一个元素，因为一个元素的数组已经排序，它减少了每个递归所需的工作量，并且将一个已经排序的数组附加到另一个数组比按常规迭代排序要少得多。

我现在有两个大问题。第一，在拆分(这可能是一个简单的，但如果不是固定的话，它会抛出所有的东西)，当我通过低->中间(+/- 1)和中间->高来分割它们时，我会遇到一个问题，在这个问题中，基本情况没有得到正确的测试并提前返回，导致一个未排序的数组。举个例子，我引用了另一个论坛的回答：“如果我的中间值为5，hi为9，低为0，那么我必须从0到5，左从6到9，或者从右0到4，从左5到9。我遇到的问题是，如果你再把它分开，比如从6到9，由于舍入，我的中间值只有7，这意味着右边只有6到7，这使得它不能满足hi - low >2的情况，因为7-6等于1，并且小于2，留下了2个可能没有排序的元素。”

现在，无论是哪种方式都会发生这种情况，因为添加+/-对两者都会导致一个奇怪的低数，但效果不太好。我怎么才能避开这一切？

第二，当涉及到合并时，我如何正确(高效)检查B‘’sand的数组边界是否合适。我是否需要另一个条件语句来检查PosB和PosC是否在范围内，如果没有，我如何才能适当地(整洁地)将其他数组的剩余内容添加到最终数组中。

提前谢谢。这应该是在visual中，但就目前而言，伪代码似乎是解决这些问题的最佳方法，而不是强调正确的语法。

A[] = { 28, 39, 48, 27, 9, 88, 11, 4, 7} ' Global variable, disregard bad programming practices

Function Split(int low, int hi){ ' Adding brackets because not only am I used to java, it should help readability
    if (hi - low) < 2 then
        return array of elements from [low, hi]
    end if

    mid = (hi + low) / 2
    B[] = split(low, mid-1) ' Either I do mid-1 or mid+1, the results seem the same
    C[] = split(mid, hi) ' Same problems as above
    D[] = Merge(B[], C[])
    return D[]
End Function

Function Merge(B[], C[]) ' I use two arrays because I figured it'd be the easiest to work with.
    int PosB = 0, PosC = 0, PosMax = (b.length + c.length) -1 ' PosB and PosC keep track of the positions in the cells of B and C respectively. 
                                                                'PosMax keeps track of the max cell that E[] (declared below) should have as well as the max number for the for loop
    E[num] ' Declare and iniatialize an array that is supposed to hold the combined values of B and C, sorted.
    for i = 0 to num
        if PosC >= c.length or B[PosB] < C[PosC] ' Checks if C[] already has added everything it has to E[] and if so, proceeds to add the
                                                    ' supposedly already sorted array B[]'s elements to E[]. Emphasis on "supposedly". A problem here is it does not check for if PosB
                                                    ' is out of bounds, which is a huge problem with primitive arrays. Also checks if the current element in C is greater than the
                                                    ' current element in B, and if so, add the element in B and increment.
            E[i] = B[PosB]
            PosB += 1 ' Does not check whether or not PosB is at the end, gotta figure a way to check
        Else
            E[i] = C[PosC]
            PosC += 1
        End If
    Next
End Function 

Answer 1

问题是，数组的边界是包含的，这意味着：

当您访问6-8中的位置时，结果中有3个元素(6、7、8)。逻辑结果是:如果只想在数组中使用范围描述一个元素，则必须编写6-6；6-7意味着仍然有两个元素(6和7)。让我们用一个示例查看下面的代码：

if (hi - low) < 2 then
    return array of elements from [low, hi]

当您将范围从6-7给这个函数时会发生什么? 7-6=1 ->真->返回。但在6-7的范围内仍然有两个因素。因此，要解决这个问题，只需编写(hi - low) < 1或更容易阅读(hi - low) == 0就足够了。

下一点是关于VBA的，所以这只是一个想法，因为我对VBA不太熟悉：

mid = (hi + low) / 2

如果这返回一个整数，结果可能四舍五入到较低的值( (3+4 ) /2=3 )。如果是这样的话，我会写如下：

B[] = split(low, mid)
C[] = split(mid + 1, hi)

原因是mid已经是较低的边框(由于四舍五入)。当边框接近于0时，Substracting 1可能会导致一些问题，因为它可能导致负值。

第二部分：

更容易将这一进程分为两部分：

E[num]' I don't know what num means but I suppose it's correct here
int PosE = 0
'adding elements to the new array while they can be compared to each other
while(c.length > 0 and b.length > 0)
    if(C[PosC] < B[PosB])
       E[PosE] = C[PosC]
       PosC += 1
    Else
       E[PosE] = B[PosB]
       PosB += 1
    End If
    PosE += 1
Next

'one of the array B or C (or both) is empty now. The remaining elements have to be added. The order doesn't matter any more.

for i = PosC to c.length 'I don't know if this is possible in VBA but I think you know what I mean: adding all the remaining elements of C to E (if there are any)
    E[PosE] = C[PosC]
    PosC += 1
    PosE += 1
Next

'doing the same with B; it could happen that one of those loops never run
for i = PosB to b.length
    E[PosE] = B[PosB]
    PosB += 1
    PosE += 1
Next

我希望这能奏效，因为我从来没有用VB写过任何东西。

如果还有任何问题，请随意提问。