排序算法运行时间显示为0且输入10万时代码失效的问题求助

问题1：排序耗时始终显示为0 #

原因 #

1. 死代码消除优化：编译器检测到排序后的数组未被后续操作使用，会直接跳过排序步骤，导致计时结果为0。
2. 计时精度不足：数据量较小时排序耗时极短，microseconds精度无法捕捉有效时长。

修复方案 #

• 保留排序代码：添加排序结果校验（如检查数组是否有序）或打印部分结果，避免死代码被编译器优化。
• 提升计时精度：改用nanoseconds统计时长，或重复运行排序操作后取平均，放大耗时数值。

问题2：输入规模100000时程序崩溃 #

原因 #

1. 栈溢出：代码中大量使用栈上分配的大数组（如generateRandVal里的bool used[1000000]、main里的int mergeS_arr[n]），栈内存空间有限（通常仅几MB），大数组会耗尽栈空间导致崩溃。
2. 非标准变长数组（VLA）：int mergeS_arr[n]属于C99特性，C++标准未定义，不同编译器支持程度不一，易引发兼容性问题。

修复方案 #

• 替换栈上大数组：改用std::vector或动态内存分配（new/delete），利用堆内存存储大数据。
• 移除所有变长数组，使用标准C++容器或动态数组。

修改后的完整代码 #

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<iomanip>
#include<chrono>
#include<vector>
#include<cassert>
using namespace std;

void generateRandVal(vector<int>& arr, int sID){
    vector<bool> used(1000000, false); // 改用vector避免栈溢出
    int count = 0;

    while(count < sID){
        int num = rand() % 1000000;
        if (!used[num]){
            arr[count] = num;
            used[num] = true;
            count++;
        }
    }
}

void printArr(const vector<int>& arr){
    for (size_t i = 0; i < arr.size(); i++) {
        cout << setfill('0') << setw(6) << arr[i] << " ";
        if ((i + 1) % 10 == 0) cout << endl;
    }
    cout << endl;
}

// 检查数组是否有序，避免死代码消除
bool isSorted(const vector<int>& arr){
    for(size_t i = 1; i < arr.size(); i++){
        if(arr[i] < arr[i-1]) return false;
    }
    return true;
}

int partition(vector<int>& arr, int left, int right){
    int pivot = arr[left];
    int l = left + 1;
    int r = right;

    while (l <= r) {
        while(l <= r && arr[l] <= pivot) l++;
        while(l <= r && arr[r] > pivot) r--;
        if(l < r) swap(arr[l], arr[r]);
    }

    swap(arr[left], arr[r]);
    return r;
}

void quickSort(vector<int>& arr, int left, int right){
    if(left < right){
        int p = partition(arr, left, right);
        quickSort(arr, left, p-1);
        quickSort(arr, p+1, right);
    }
}

void merge(vector<int>& arr, int left, int mid, int right){
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> l(n1), r(n2); // 改用vector避免栈溢出

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

    int i = 0, j = 0, k = left;
    while(i < n1 && j < n2){
        if(l[i] <= r[j]){
            arr[k] = l[i];
            i++;
        }else{
            arr[k] = r[j];
            j++;
        }
        k++;
    }

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

    while(j < n2){
        arr[k] = r[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);
        merge(arr, left, mid, right);
    }
}

int main(){
    srand(time(NULL));
    int sID;

    cout << "Please input the number of subscriber IDs you want (max 1000000): ";
    cin >> sID; 
    sID = min(sID, 1000000); 

    vector<int> unsortedArr(sID);
    generateRandVal(unsortedArr, sID);
    cout << "Before sorting:\n";
    printArr(unsortedArr);

    // 归并排序计时
    vector<int> mergeS_arr = unsortedArr;
    auto start1 = chrono::high_resolution_clock::now();
    mergeSort(mergeS_arr, 0, sID-1);
    auto end1 = chrono::high_resolution_clock::now();
    // 校验排序结果，避免死代码消除
    assert(isSorted(mergeS_arr));
    auto mergeS_duration = chrono::duration_cast<chrono::nanoseconds>(end1 - start1);
    cout << "Merge Sort time taken: " << mergeS_duration.count() << " nanoseconds" << endl;

    // 快速排序计时
    vector<int> quickS_arr = unsortedArr;
    auto start2 = chrono::high_resolution_clock::now();
    quickSort(quickS_arr, 0, sID-1);
    auto end2 = chrono::high_resolution_clock::now();
    // 校验排序结果
    assert(isSorted(quickS_arr));
    auto quickS_duration = chrono::duration_cast<chrono::nanoseconds>(end2 - start2);
    cout << "Quick Sort time taken: " << quickS_duration.count() << " nanoseconds" << endl;

    return 0;
}

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