C++测试归并/插入排序时大数组触发段错误原因排查

核心问题分析 #

段错误的主要原因是栈内存溢出，同时代码还存在其他逻辑错误：

• 栈空间通常只有几MB，代码中用栈分配变长数组（int forMerge[asize];、int leftArr[n1];），当数组大小超过栈容量时直接崩溃。
• 数组复制逻辑错误：auto forInsertion = forMerge;只是复制指针，导致两个变量指向同一数组，排序操作互相干扰。
• 未初始化随机数生成器：rand()每次生成相同序列，测试结果无参考性。
• 计时代码拼写错误：插入排序的时间计算复用了归并排序的起止时间，且变量名拼写有误。

修复后的完整代码 #

#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;

void generateArray(vector<int>& arr) {
    for (size_t i = 0; i < arr.size(); ++i) {
        arr[i] = rand();
    }
}

void insertionSort(vector<int>& arr) {
    int size = arr.size();
    for (int i = 1; i < size; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void merger(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    // 用vector在堆上分配内存，避免栈溢出
    vector<int> leftArr(n1);
    vector<int> rightArr(n2);

    for (int i = 0; i < n1; ++i)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        rightArr[j] = arr[mid + 1 + j];

    int i = 0;
    int j = 0;
    int k = left;

    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merger(arr, left, mid, right);
    }
}

void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    // 初始化随机数生成器
    srand(time(nullptr));
    // 生成1000到100999之间的数组大小，可根据需求调整范围
    int asize = rand() % 100000 + 1000;
    vector<int> forMerge(asize);
    generateArray(forMerge);
    // 直接复制vector，得到独立的测试数组
    vector<int> forInsertion = forMerge;

    auto startMerge = high_resolution_clock::now();
    mergeSort(forMerge, 0, asize - 1);
    auto stopMerge = high_resolution_clock::now();
    auto durationMerge = duration_cast<nanoseconds>(stopMerge - startMerge);
    cout << "归并排序耗时: " << durationMerge.count() << " 纳秒" << endl;

    auto startInsertion = high_resolution_clock::now();
    insertionSort(forInsertion);
    auto stopInsertion = high_resolution_clock::now();
    auto durationInsertion = duration_cast<nanoseconds>(stopInsertion - startInsertion);
    cout << "插入排序耗时: " << durationInsertion.count() << " 纳秒" << endl;
}

关键修复点说明 #

• 替换栈数组为vector：vector在堆上分配内存，支持动态大小且不会触发栈溢出，适合大数据量测试。
• 修复数组复制逻辑：直接用vector的赋值运算符复制，确保两个排序算法操作独立的原始数据。
• 初始化随机数生成器：添加srand(time(nullptr))，每次运行生成不同的随机数组，测试结果更真实。
• 修正计时错误：插入排序的时间计算改为stopInsertion - startInsertion，并修正变量名拼写错误。
• 限制数组大小范围：用rand() % 100000 + 1000生成合理的测试大小，避免数组过大导致内存占用过高。

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