1

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

我很困惑我们如何在退出左/右排序合并递归后合并回这些子数组。让我们从最底部开始，当我们的元素被分成两个子数组时，左子数组称为 B，右子数组称为 C。在 16:43 左右，我们跳转到合并函数并对数组 B 和 C 进行排序，这只是 8 3.归并排序功能（代码如下）基本上是通过索引比较B和C的元素。从元素 0 开始，我们比较两个数组中的每个元素，并将最小的元素添加到数组 A 中。我们增加该元素来自的数组的索引等，直到我们基本上有了一个排序数组。

我们基本上做我们上面所做的，然后再次退出我们所在的递归调用并继续合并 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]
}
4

1 回答 1

1

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

假设 Top 有一个数组 Original，内容为 {3,4,2,1}。热门调用 MergeSort(Original)

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}。

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

于 2013-08-04T10:46:50.600 回答