合并排序算法未正确合并
Merge Sort algorithm isn't merging properly
所以，我确实知道合并排序应该做什么，而且我现在可以稍微想象一下了。递归拆分直到数组中只剩下一个元素，因为一个元素的数组已经排序，它减少了每次递归所需的工作量，并且将一个已经排序的数组附加到另一个数组的计算量比按正常迭代排序。
我现在有两个主要问题。一，关于分裂（这可能是一个简单的分裂，但如果不固定它会扔掉所有东西），当我通过低 -> 中（+/- 1）和中 -> 高来分裂它们时，我遇到了一个问题基本情况未正确测试并且过早 returns ，导致未排序的数组。举个例子，引用我在另一个论坛的回复，"if I have a middle of 5, hi of 9 and low of 0, then I have to either split it right from 0 to 5 and left from 6 to 9, or right 0 to 4 and left 5 to 9. The problem I'm having is that if you split it again, say from 6 to 9, I have a middle of 7 due to rounding, meaning the right will have only 6 to 7, making it fail the case of hi - low > 2 since 7 - 6 equals 1 and is less than 2, leaving 2 potentially unsorted elements."
现在，无论哪种方式都会发生这种情况，因为将 +/- 添加到 mid 中的任何一种都会导致一种奇数低的数字，效果不佳。我该如何解决这个问题？
其次，在合并的时候，如何正确（高效）的检查B和C的数组边界是否合适。我是否需要另一个条件语句来检查 PosB 和 PosC 是否在边界内，如果一个不在边界内，我如何适当地（整齐地）将另一个数组的左边添加到最终数组。
提前致谢。这应该是在 Visual Basic 中，但目前伪代码似乎是解决这些问题的最佳方法，而不是强调正确的语法。
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
问题是，数组的边界是包容性的，这意味着：
当您访问 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 -> 真 -> return。但在 6-7 范围内仍然是两个元素。因此，为了解决这个问题，编写 (hi - low) < 1 或更容易阅读 (hi - low) == 0.
就足够了
下一点是关于 VBA 的，所以这只是一个想法，因为我对 VBA 不是很熟悉：
mid = (hi + low) / 2
如果此 return 是整数，则结果可能四舍五入为较小的值 ( (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 中写过任何东西。
如果还有任何问题，请随时提出。
所以，我确实知道合并排序应该做什么，而且我现在可以稍微想象一下了。递归拆分直到数组中只剩下一个元素，因为一个元素的数组已经排序，它减少了每次递归所需的工作量，并且将一个已经排序的数组附加到另一个数组的计算量比按正常迭代排序。
我现在有两个主要问题。一，关于分裂（这可能是一个简单的分裂，但如果不固定它会扔掉所有东西），当我通过低 -> 中（+/- 1）和中 -> 高来分裂它们时，我遇到了一个问题基本情况未正确测试并且过早 returns ，导致未排序的数组。举个例子，引用我在另一个论坛的回复，"if I have a middle of 5, hi of 9 and low of 0, then I have to either split it right from 0 to 5 and left from 6 to 9, or right 0 to 4 and left 5 to 9. The problem I'm having is that if you split it again, say from 6 to 9, I have a middle of 7 due to rounding, meaning the right will have only 6 to 7, making it fail the case of hi - low > 2 since 7 - 6 equals 1 and is less than 2, leaving 2 potentially unsorted elements."
现在，无论哪种方式都会发生这种情况，因为将 +/- 添加到 mid 中的任何一种都会导致一种奇数低的数字，效果不佳。我该如何解决这个问题？
其次，在合并的时候，如何正确（高效）的检查B和C的数组边界是否合适。我是否需要另一个条件语句来检查 PosB 和 PosC 是否在边界内，如果一个不在边界内，我如何适当地（整齐地）将另一个数组的左边添加到最终数组。
提前致谢。这应该是在 Visual Basic 中，但目前伪代码似乎是解决这些问题的最佳方法，而不是强调正确的语法。
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
问题是，数组的边界是包容性的，这意味着：
当您访问 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 -> 真 -> return。但在 6-7 范围内仍然是两个元素。因此，为了解决这个问题，编写 (hi - low) < 1 或更容易阅读 (hi - low) == 0.
下一点是关于 VBA 的，所以这只是一个想法，因为我对 VBA 不是很熟悉：
mid = (hi + low) / 2
如果此 return 是整数，则结果可能四舍五入为较小的值 ( (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 中写过任何东西。
如果还有任何问题，请随时提出。