C++新手求助：如何实现归并排序完整过程的步骤打印

嘿，作为C++新手想把归并排序的每一步都清晰打印出来太合理了！我看了你已经搭好的分治法代码框架，现在咱们把它补全，让拆分（divide）和合并（merge）的每一步都明明白白展示出来。

先看看你给出的初始代码（我帮你整理了格式）：

#include <iostream>
using namespace std;
//prototype
void mergeSort2(int, int);
void merge2(int, int, int);
void printArray(int, int);
//input
int S[7] = { 38, 27, 43, 3, 9, 82, 10 };
//count divide and merge
int divideCount = 1;
int mergeCount = 1;
int main() {
    //show input
    printArray(0, 6);
    cout << endl;
    //start merge sort
    mergeSort2(0, 6);
    cout << "\n最终排序结果：";
    printArray(0, 6);
    return 0;
}

不过你的代码里mergeSort2、merge2和printArray都还没实现，接下来咱们把这几个函数补全，同时加上分步打印的逻辑。

完整实现代码 #

#include <iostream>
using namespace std;

// 函数声明
void mergeSort2(int left, int right);
void merge2(int left, int mid, int right);
void printArray(int left, int right);
void printIndent(int level); // 用于打印缩进，让分步结构更清晰

// 输入数组
int S[7] = { 38, 27, 43, 3, 9, 82, 10 };
// 拆分和合并的计数
int divideCount = 1;
int mergeCount = 1;
// 用于控制缩进的层级，拆分时+1，合并时-1
int indentLevel = 0;

int main() {
    cout << "初始数组：";
    printArray(0, 6);
    cout << "\n\n开始归并排序过程：\n";
    mergeSort2(0, 6);
    cout << "\n最终排序结果：";
    printArray(0, 6);
    return 0;
}

// 打印数组的指定区间[left, right]
void printArray(int left, int right) {
    cout << "[";
    for (int i = left; i <= right; ++i) {
        cout << S[i];
        if (i != right) cout << ", ";
    }
    cout << "]";
}

// 打印缩进，让每一层拆分/合并的结构更直观
void printIndent(int level) {
    for (int i = 0; i < level; ++i) {
        cout << "  ";
    }
}

// 归并排序的拆分函数
void mergeSort2(int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        
        // 打印当前拆分步骤
        printIndent(indentLevel);
        cout << "第" << divideCount << "次拆分：将 ";
        printArray(left, right);
        cout << " 拆分为 ";
        printArray(left, mid);
        cout << " 和 ";
        printArray(mid+1, right);
        cout << "\n";
        divideCount++;
        indentLevel++;
        
        // 递归拆分左右子数组
        mergeSort2(left, mid);
        mergeSort2(mid + 1, right);
        
        indentLevel--;
        // 合并左右子数组
        merge2(left, mid, right);
    }
}

// 合并两个有序子数组的函数
void merge2(int left, int mid, int right) {
    int temp[7]; // 临时数组用于存储合并结果
    int i = left;    // 左子数组的起始索引
    int j = mid + 1; // 右子数组的起始索引
    int k = left;    // 临时数组的起始索引
    
    // 打印合并前的两个子数组
    printIndent(indentLevel);
    cout << "第" << mergeCount << "次合并：将 ";
    printArray(left, mid);
    cout << " 和 ";
    printArray(mid+1, right);
    cout << " 合并为 ";
    
    // 合并两个有序子数组到临时数组
    while (i <= mid && j <= right) {
        if (S[i] <= S[j]) {
            temp[k++] = S[i++];
        } else {
            temp[k++] = S[j++];
        }
    }
    // 复制左子数组剩余元素
    while (i <= mid) {
        temp[k++] = S[i++];
    }
    // 复制右子数组剩余元素
    while (j <= right) {
        temp[k++] = S[j++];
    }
    // 将临时数组的内容复制回原数组
    for (i = left; i <= right; ++i) {
        S[i] = temp[i];
    }
    
    // 打印合并后的结果
    printArray(left, right);
    cout << "\n";
    mergeCount++;
}

代码说明 #

• 缩进层级indentLevel：用来控制每一步打印的缩进，拆分时层级加1，合并完成后层级减1，这样能直观看出归并排序的递归结构，哪一步属于哪一层的拆分/合并。
• printIndent函数：根据当前层级打印空格，让输出的结构更清晰，像树状结构一样展示递归过程。
• 拆分过程打印：每次拆分时，打印当前要拆分的数组，以及拆分成的两个子数组，并记录拆分次数。
• 合并过程打印：每次合并前，打印要合并的两个有序子数组，合并完成后打印合并后的结果，并记录合并次数。

运行这段代码后，你就能看到从初始数组开始，每一次拆分、每一次合并的完整过程，完全符合你想要的分步展示需求。

内容的提问来源于stack exchange，提问作者Jenny Choi