arrays - 合并排序算法(合并数组部分)

Question

问题是关于从 16:43 到 23:34 的视频中的合并排序 http://youtu.be/M814OagXWTI?t=16m43s

我很困惑我们如何在退出左/右排序合并递归后合并回这些子数组。当我们的元素被分成两个子数组时，让我们从最底部开始，左边的子数组称为 B，右边的子数组称为 C。在 16:43 左右，我们跳入合并函数并对数组 B 和 C 进行排序，它们仅为 8和 3. 合并排序函数(代码如下)基本上通过索引比较 B 和 C 的元素。从元素 0 开始，我们比较两个数组中的每个元素，将最小的元素添加到数组 A。我们增加该元素来自哪个数组的索引等等，直到我们基本上有了一个排序数组。排序数组完成后，我们退出递归调用以爬回先前暂停的递归堆栈，并继续拆分子数组 8 3 2 9 的右侧。

我们基本上做了上面所做的，然后再次退出我们所在的递归调用并继续合并 3 8 2 9。好的，这是我的问题:我在代码。我们将合并的元素反馈给数组 A，但是当我们调用合并函数合并 2 8 和 2 9 时，我们传递的是数组 B、C 和 A。然后我们使用数组 B 和 C 进行比较，但是元素我们想排序在 A 中，不是吗？那不就是把错误的东西分类了吗？我真的需要对这部分进行一些说明。

伪代码:

 MergeSort(A[0...n-1]){
if n<=1
    return A;

copy A[0...n/2-1] to B[0...n/2-1]
copy A[n/2...n-1] to C[0...n/2-1]
MergeSort(B[0...(n/2)-1)
MergeSort(C[0...(n/2)-1)
Merge(B,C,A)

Merge(B[0...p-1], C[0...q-1], A[0...p+q-1]){
i=0; j=0; k=0
while( i <p and j<q) do{
    if B[i] <= C[j] {
        A[k]=B[i];
        i=i+1;
    }
    else {
    A[k]=C[j];
    j=j+1;
    }
    k=k+1
}

//Copy leftover element
if i==p
    A[k...p+q-1]=C[j...q-1]
else
    A[k...p+q-1]=B[i...p-1]
}

Answer 1

这是使用引用算法的简单排序的逐条叙述。缩进表示堆栈深度。每个 MergeSort 或 Merge 调用都按时间顺序编号。 A3表示调用3中的A数组，“==”表示“等价于”。 “=”表示“有内容”。

假设 Top 有一个数组 Original，内容为 {3,4,2,1}。 Top calls MergeSort(原图)

MergeSort1(A1==Original={3,4,2,1}) Create B1={3,4} and C1={2,1}
  MergeSort2(A2==B1={3,4}) Create B2={3} and C2={4}
    MergeSort3(A3==B2={3}) Base case, no changes.
    MergeSort4(A4==C2={4}) Base case, no changes.
    Merge5(B5==B2={3},C5==B2={4},A5==A2==B1) Write {3,4} into A5, which is A2, which is B1.
  MergeSort6(A6==C1={2,1}) Create B6={2} and C6={1}
    MergeSort7(A7==B6={2}) Base case, no changes.
    MergeSort8(A8==C6={1}) Base case, no changes.
    Merge9(B9==B6={2},C9==C6={1},A9==A6==C1) Write {1,2} into A9, which is A6, which is C1.
  Merge10(B10==B1={3,4},C10==C1=={1,2},A10==A1==Original) Write {1,2,3,4} into A10, which is A1, which is Original.

所有这一切的高级结果是用 {1,2,3,4} 替换 Original 中的 {3,4,2,1}。

要记住的关键点是每个函数调用都有自己的堆栈框架，有自己的变量，但它的形式参数映射到实际参数，即调用者框架中的变量或参数。