如何消除ShellSort算法运行时测试中的时间波动？

核心问题 #

1. 步长数组访问越界：int k = steps.size(); 后直接访问 steps[k]，但vector索引从0开始，steps的size为8，最大合法索引是7，这会触发未定义行为，是图表异常抬升的关键诱因。
2. 随机数生成冗余且精度不足：每次循环都用time(nullptr)初始化mt19937，该函数返回秒级时间戳，若循环在1秒内完成多次，会导致多个N对应的测试数组完全相同；同时重复初始化也会引入额外时间开销，干扰测量结果。
3. 计时范围包含无关操作：当前计时覆盖了数组创建、随机填充的过程，这些操作的开销会混入排序时间，导致数据失真。
4. 单次测量误差大：系统进程调度、缓存波动等外部因素会导致单次排序时间波动明显，无法反映算法真实性能。

修复与优化方案 #

1. 修复步长数组越界问题 #

将k的初始值改为steps.size() - 1，并调整循环条件避免越界：

int k = steps.size() - 1;
while (k >= 0 && N < steps[k]) {
    k--;
}

2. 优化随机数生成逻辑 #

• 只初始化一次随机数生成器，避免重复初始化的开销和种子重复问题；
• 使用random_device获取更随机的种子（平台支持时），替代精度不足的秒级时间戳。

3. 精确控制计时范围 #

仅对ShellSort的核心排序代码计时，排除数组创建、随机填充的时间。可以预先生成测试数组，再开始计时。

4. 多次重复测量取平均值 #

对每个N值，重复排序多次（比如100次），取平均时间抵消系统干扰带来的波动。

修改后的完整代码 #

#include <iostream>
#include <vector>
#include <random>
#include <chrono>

using namespace std;

// 提取ShellSort为独立函数，方便重复调用
void shellSort(vector<int>& A, const vector<int>& steps) {
    int N = A.size();
    int k = steps.size() - 1;
    while (k >= 0 && N < steps[k]) {
        k--;
    }

    for (; k >= 0; k--) {
        for (int i = steps[k]; i < N; i += 1) {
            int temp = A[i];
            int j;
            for (j = i; j >= steps[k] && A[j - steps[k]] > temp; j -= steps[k])
                A[j] = A[j - steps[k]];
            A[j] = temp;
        }
    }
}

int main() {
    const int REPEAT_TIMES = 100; // 重复测量次数
    vector<int> steps = {1, 2, 8, 32, 128, 512, 2048, 8192};

    // 初始化随机数生成器，仅执行一次
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<int> dist(0, 999);

    for (int N = 2; N <= 5000; N++) {
        // 预先生成测试数组
        vector<int> A(N);
        for (int i = 0; i < N; ++i) {
            A[i] = dist(mt);
        }

        long long total_duration = 0;
        for (int r = 0; r < REPEAT_TIMES; r++) {
            vector<int> temp_A = A; // 每次使用相同的数组副本测试
            auto t1 = chrono::high_resolution_clock::now();
            shellSort(temp_A, steps);
            auto t2 = chrono::high_resolution_clock::now();
            auto duration = chrono::duration_cast<chrono::nanoseconds>(t2 - t1);
            total_duration += duration.count();
        }

        // 计算平均时间
        long long avg_duration = total_duration / REPEAT_TIMES;
        cout << N << " " << avg_duration << "\n";
    }
    return 0;
}

额外说明 #

• 提取排序函数为独立模块，既方便重复调用，也让计时逻辑更清晰；
• 使用uniform_int_distribution替代mt() % 1000，保证随机数分布更均匀；
• 每次重复测试使用原数组的副本，确保每次排序的初始状态完全一致，排除排序状态对时间的影响；
• 可根据性能情况适当增大REPEAT_TIMES的值，进一步降低时间波动。

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