歸併排序算法不正確合併

Question

所以，我不知道什麼是合併排序是應該做的，我有點現在可以進行可視化。遞歸分割，直到只有一個元件被留在陣列中，由於一個元件的陣列已經排序，它減少了所需要的每一遞歸的工作量，並附加一個已排序陣列到另一陣列比至少很多計算密集按正常迭代排序。

我有兩個主要問題現在。一，關於分裂（這可能是一個簡單的，但它會拋出一切，如果不是固定的），當我通過低 - >中（+/- 1）和中 - >高分裂他們時，我遇到了問題基礎案例未正確測試並過早返回，導致未排序的數組。舉個例子，當我引用我的回答從另一個論壇，「如果我有喜9和低的0 5中間，然後我不得不要麼是正確的，從0分裂，5和6人至9日，或者右邊0到4，左邊5到9.我遇到的問題是，如果你再次分割它，比如從6到9，由於四捨五入，我有一個7的中間值，這意味着右邊只有6到7 ，因爲7 - 6等於1並且小於2，所以它在高 - > 2的情況下失敗，留下2個可能未分類的元素。「現在

，這種情況無論哪種方式，如添加到+/-中旬要麼會導致一種奇怪的低數量，並不能很好的工作。我如何解決這個問題？第二，當談到合併時，我如何正確（有效地）檢查B和C的數組邊界是否合適。我需要另一個條件語句來檢查POSB和POSC是否是在邊界，如果一個不是，我怎麼能適當地（整齊）上留下什麼其他的陣列到陣列的最後添加。

在此先感謝。這應該是在視覺基礎上，但現在僞代碼似乎是解決這些問題的最好方法，而不是強調正確的語法。

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有你的結果（6,7,8），3個元素的位置。邏輯結果是：如果你只需要一個數組中的一個範圍描述的元素，你將不得不寫[6-6]; [6-7]意味着還有兩個元素（6和7）。讓我們看一下下面的代碼用一個例子：

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

當你給6-7的範圍內，以該功能會發生什麼？ 7-6 = 1 - > true - >返回。但是在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時，抽象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寫的任何東西。

如果還有任何問題可以隨時詢問。