归并排序算法 void MSort（ElemType SR[ ]，ElemType TR1[ ]，int s，int t）{ /// / 将SR[s...t]进行2-路归并排序为TR1[s...t]。 if（s==t） TR1[s]=SR[s];（1） else{ m=（s+t）/2; （2） MSort（SR，TR2，s，m）; （3） MSort（SR，TR2，m+1，t）; （4） Merge（TR2，TR1，s，m，t）; （5） } } } 请画出该归并排序算法的递归调用过程。 输入无序数组为56，20，10，25，8。

下面是该归并排序算法的递归调用过程：

初始状态：

SR: 56 20 10 25 8
TR1: 0 0 0 0 0
TR2: 0 0 0 0 0

1. s=1, t=5，不满足条件，继续执行。
2. m=3，调用 MSort(SR, TR2, 1, 3)。
3. s=1, t=3，不满足条件，继续执行。
4. m=2，调用 MSort(SR, TR2, 1, 2)。
5. s=1, t=2，不满足条件，继续执行。
6. m=1，调用 MSort(SR, TR2, 1, 1)。
7. s=1, t=1，满足条件，执行 TR1[1]=SR[1]。
8. 返回上一层递归。
9. 执行 Merge(TR2, TR1, 1, 1, 2)，得到 TR1: 20 56 0 0 0。
10. 返回上一层递归。
11. m=2，调用 MSort(SR, TR2, 3, 2)。
12. 不满足条件，直接返回上一层递归。
13. 执行 Merge(TR2, TR1, 1, 3, 2)，得到 TR1: 10 20 25 56 8。
14. 返回上一层递归。
15. 执行 Merge(TR2, TR1, 1, 2, 5)，得到 TR1: 8 10 20 25 56。

最终排序结果为：8 10 20 25 56。

相关问题

这段代码怎样改错void Headadjust(SStablel& S, int s, int m) { //分数堆排序 Elemtype rc; rc = S.R[s]; for (int j = 2 * s; j <= m; j *= 2) { if (j < m && S.R[j].score < S.R[j + 1].score)++j; if (rc.score >= S.R[j].score) break; S.R[s] = S.R[j]; s = j; } } void Creatheap(SStablel& S) { int n = S.length; for (int i = n / 2; i > 0; --i) Headadjust(S, i, n); } void Headsort(SStablel& S) { Creatheap(S); for (int i = S.length; i > 1; --i) { Elemtype x; x = S.R[1]; S.R[1] = S.R[i]; S.R[i] = x; Headadjust(S, 1, i - 1); } } void Merge(Elemtype r[], Elemtype t[], int low, int mid, int high) { //分数归并排序 int i = low; int j = mid + 1; int k = low; while (i <= mid && j <= high) { if (r[i].score <= r[j].score) t[k++] = r[i++]; else t[k++] = r[j++]; } while (i <= mid) t[k++] = r[i++]; while (j <= high)t[k++] = r[j++]; } void Msort(Elemtype r[], Elemtype t[], int low, int high) { Elemtype s[1]; if (high == low)t[low] = r[low]; else { int mid = (high + low) / 2; Msort(r, s, low, high); Msort(r, s, mid + 1, high); Merge(s, t, low, mid, high); } } void Mergesort(SStablel& S) { Msort(S.R, S.R, 1, S.length); }

在这段代码中，有两个函数名拼写错误，应该将 `SStablel` 改为 `SStable`，这可能是由于其他地方的拼写错误导致的。此外，代码中的 `Elemtype` 类型在没有给出定义的情况下使用，需要在代码开头或其他地方给出定义。

修改后的代码如下：

void Heapadjust(SStable& S, int s, int m) {         //分数堆排序
    Elemtype rc;
    rc = S.R[s];
    for (int j = 2 * s; j <= m; j *= 2) {
        if (j < m && S.R[j].score < S.R[j + 1].score)++j;
        if (rc.score >= S.R[j].score) break;
        S.R[s] = S.R[j];
        s = j;
    }
}

void Createheap(SStable& S) {
    int n = S.length;
    for (int i = n / 2; i > 0; --i)
        Heapadjust(S, i, n);
}

void Heapsort(SStable& S) {
    Createheap(S);
    for (int i = S.length; i > 1; --i) {
        Elemtype x;
        x = S.R[1];
        S.R[1] = S.R[i];
        S.R[i] = x;
        Heapadjust(S, 1, i - 1);
    }
}

void Merge(Elemtype r[], Elemtype t[], int low, int mid, int high) {   //分数归并排序
    int i = low;
    int j = mid + 1;
    int k = low;
    while (i <= mid && j <= high) {
        if (r[i].score <= r[j].score) t[k++] = r[i++];
        else t[k++] = r[j++];
    }
    while (i <= mid) t[k++] = r[i++];
    while (j <= high)t[k++] = r[j++];
}

void Msort(Elemtype r[], Elemtype t[], int low, int high) {
    Elemtype s[1];
    if (high == low)t[low] = r[low];
    else {
        int mid = (high + low) / 2;
        Msort(r, s, low, high);
        Msort(r, s, mid + 1, high);
        Merge(s, t, low, mid, high);
    }
}

void Mergesort(SStable& S) {
    Msort(S.R, S.R, 1, S.length);
}

void Merge(RedType R[],RedType T[],int low,int mid,int high)//归并排序 { int i=low,j=mid+1,k=low; while(i<=mid&&j<=high) { if(R[i].key<-R[j].key) T[k++]=R[i++]; else T[k++]=R[j++]; } while(i<=mid) T[k++]=R[i++]; while(j<=high) T[k++]=R[j++]; } void MSort(RedType R[],RedType T[],int low,int high) { RedType S[]={}; if(low==high) T[low]=R[low]; else { int mid=(low+high)/2; MSort(R,S,low,mid); MSort(R,S,mid+1,high); Merge(S,T,low,mid,high); } } void MergeSort(SqList &L)//归并排序 { MSort(L.r,L.r,1,L.length); }请问上述代码 该如何输出每一趟的排序结果？

要输出每一趟归并排序的结果，你可以在归并操作前后添加打印语句来实现。以下是修改后的代码示例：

void Merge(RedType R[], RedType T[], int low, int mid, int high) // 归并排序
{
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high)
    {
        if (R[i].key < -R[j].key)
            T[k++] = R[i++];
        else
            T[k++] = R[j++];
    }
    while (i <= mid)
        T[k++] = R[i++];
    while (j <= high)
        T[k++] = R[j++];

    // 输出当前趟的排序结果
    for (int index = low; index <= high; index++)
    {
        R[index] = T[index];
        cout << R[index].key << " ";
    }
    cout << endl;
}

void MSort(RedType R[], RedType T[], int low, int high)
{
    RedType S[] = {};
    if (low == high)
        T[low] = R[low];
    else
    {
        int mid = (low + high) / 2;
        MSort(R, S, low, mid);
        MSort(R, S, mid + 1, high);
        Merge(S, T, low, mid, high);
    }
}

void MergeSort(SqList &L) // 归并排序
{
    MSort(L.r, L.r, 1, L.length);
}

在`Merge`函数中，添加了一个循环来输出当前趟的排序结果。在`MergeSort`函数中，调用了`MSort`函数来进行归并排序。每次归并操作后，都会输出当前趟的排序结果。

这样，你就可以看到每一趟归并排序的结果了。希望对你有帮助！