为何我的ShellSort时间复杂度呈线性？需对比InsertSort与不同间隔ShellSort

• 对比InsertSort与不同间隔的ShellSort时，InsertSort的时间复杂度符合O(n²)的预期，但采用Shell间隔的ShellSort耗时远低于预期，呈现线性特征。
• 明确ShellSort应比InsertSort更快，但当前表现超出合理预期；代码可正常完成排序，间隔设置未发现明显问题。
• 编译环境：Code::Blocks，使用GNU GCC Compiler并开启-O0优化。

测试代码 #

#include <iostream>
#include <fstream>
#include <cmath>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

void InsertSort(int tab[], int n)
{
    for(int i=1; i<n; i++)
    {
        int temp = tab[i];
        int j;
        for(j=i-1; j>=0; j--)
        {
            if(tab[j]>temp)
            {
                tab[j+1] = tab[j];
            }
        }
        tab[j+1] = temp;
    }
}

void ShellSort(int tab[], int n, int gaps[], int gapsSize)
{
    for(int g = 0; g < gapsSize; g++)
    {
        int gap = gaps[g];
        for(int k = 0; k < gap; k++)
        {
            for(int i=gap+k; i<n; i=i+gap)
            {
                int temp = tab[i];
                int j;
                for(j=i-gap; j>=0; j=j-gap)
                {
                    if(tab[j]>temp)
                    {
                        tab[j+gap] = tab[j];
                    }
                    else{break;}
                }
                tab[j+gap] = temp;
            }
        }
    }

}

int* ShellSortGaps(int n, int& gapSize) // SHELL
{
    int k=n/2;
    int counter = 0;
    do
    {
        k = k/2;
        counter++;
    }while(k>0);
    int* gap = new int[counter];
    k=n/2;
    for(int i=0; i<counter; i++)
    {
        gap[i] = k;
        k=k/2;
    }
    gapSize = counter;
    return gap;
}

int main()
{
    random_device rd;
    mt19937 generator(rd());
    uniform_int_distribution<int> dist(1, 100000000);
    ofstream myFile;
    myFile.open ("results.csv");
    myFile << "N;TIME(s)" << endl;
    int n = 10000; // starting size of array to sort
    do
    {
        int* tab = new int[n];
        for(int i=0; i<n; i++)
        {
            tab[i] = dist(generator);
        }
        int gapsSize = 0;
        int* gapsResult = ShellSortGaps(n, gapsSize);
        auto start = high_resolution_clock::now();
        //ShellSort(tab,n,gapsResult,gapsSize);
        InsertSort(tab,n);
        auto end = high_resolution_clock::now();
        auto duration = duration_cast<milliseconds>(end - start);
        myFile << n << ";" << duration.count()/1000.0 << endl;
        cout << "N: " << n << " TIME: " << duration.count()/1000.0 << "s" << endl;
        n+=10000;
        delete[] tab;
    }while(n<=250000);
    myFile.close();
    return 0;
}

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