嘿，我帮你梳理了代码里的几个关键问题，这些正是导致执行时间不符合预期、甚至排序逻辑出错的根源，咱们一步步来解决：

1. 时间统计的低级bug #

你在输出MergeSort的执行时间时，错误复用了QuickSort的起始时间变量start，而不是用MergeSort自己的start2，这直接导致MergeSort的时间和QuickSort完全一致！这个问题在Sorted和Random两个测试块里都存在，必须修正：

// 错误代码（两处都要改）
printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
// 修正为
printf("%0.5fms", (float)(clock() - start2) / CLOCKS_PER_SEC);

另外建议把时间乘以1000转换成毫秒，更符合日常阅读习惯，比如：

printf("%0.5fms", (float)(clock() - start2) / CLOCKS_PER_SEC * 1000);

2. QuickSort的Partition逻辑严重错误 #

你的Partition函数里，把基准点的赋值和交换操作放在了for循环内部，这会导致每次迭代都移动基准元素，完全打乱了分区逻辑！尤其是在处理已排序数组时，会让QuickSort的时间复杂度直接退化为O(n²)，甚至出现错误的排序结果。正确的做法是把这两行移到循环结束后：

void Partition(vector<int>& s, int low, int high, int& pvpoint) {
    int j;
    int pvitem;
    pvitem = s.at(low);
    j = low;
    for (int i = low + 1; i <= high; i++) {
        if (s.at(i) < pvitem) {
            j++;
            swap(s.at(i), s.at(j));
        }
        // 把下面两行移出循环！
        // pvpoint = j;
        // swap(s.at(low), s.at(pvpoint));
    }
    // 循环结束后再确定基准点并完成交换
    pvpoint = j;
    swap(s.at(low), s.at(pvpoint));
}

这个错误是导致QuickSort在已排序数组上表现异常的核心原因。

3. 测试用例的优化建议 #

• 随机种子未初始化：你没有调用srand(time(0))，导致每次运行生成的随机数组完全一样，建议在main函数开头添加这行代码，让测试更具随机性。
• 测试规模差距过大：你给已排序数组的规模是500_{5000，而随机数组是55000}100000，两者规模差距太大，不利于对比时间复杂度。建议把两类测试用例的规模设置成一致（比如都用500、1000...10000），这样对比更直观。
• 已排序数组生成可以更高效：你当前是先生成伪随机数组再调用sort，虽然能工作，但直接生成有序数组（比如for(int j=0;j<Arr.size();j++) Arr[j] = j;）会更高效。

4. 其他小细节（不修改排序核心逻辑） #

• Merge函数里的vector<int> u(s);会复制整个数组，其实可以只复制[low, high]区间的元素来节省内存，但如果要求尽量不修改排序算法本身，这个可以暂时忽略。
• 可以用setw来对齐输出的时间，让结果表格更易读，比如添加<iomanip>头文件后，用cout << setw(10)来控制宽度。

修正后的预期效果 #

搞定这些问题后，你会看到符合预期的对比结果：

• 在已排序数组上，未做基准优化的QuickSort会比MergeSort慢很多（O(n²) vs O(nlogn)）。
• 在随机数组上，两者时间复杂度都是O(nlogn)，QuickSort通常会因为常数更小而略快于MergeSort。

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