来看看实验要求先:

采用几组不同数据测试以下排序算法的时间性能。
直接插入排序
希尔排序
冒泡排序
快速排序
直接选择排序
堆排序
算法所用时间必须是机器时间，也可以包括比较和移动的次数。实验分析及其结果以清晰的方式来描述，如数学公式或图表等。

    /*
     * @Author: Vastsea(lyx8851@qq.com)
     * @Date: 2023-05-08 22:19:18
     * @LastEditors: Vastsea(lyx8851@qq.com)
     * @LastEditTime: 2023-05-19 00:36:33
     * @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\Experiment_5\测试数据生成.cpp
     * @Description: 
     * Link:https://59888888.xyz/
     * Phone:18893558104
     */
    #include <iostream>
    #include <ctime>
    #include <windows.h>
    using namespace std;
    #define Data_Dir "10^.tds"
    int main()
    {
        long int N, tmp, plus = 10;
        double start, end;
        int choice;
        cout << "输入数据量:" << endl;
        cin >> N;
        cout << "选择生成类型(1:正序 2:逆序 3:随机):" << endl;
        cin >> choice;
        plus *= N;
        FILE *fp;
        if (!(fp = fopen(Data_Dir, "w+")))
        {
            cout << "打开数据文件错误" << endl;
        }
        if (!fprintf(fp, "%d\n", N))
        {
            cout << "写入总数错误" << endl;
            
        }
        cout << "----------开始生成----------" << endl;
        switch (choice)
        {
        case 1:
        {
            start = GetTickCount();
            for (long int i = 1; i <= N; i++)
            {
                fprintf(fp, "%d\n", i);
            }
            end = GetTickCount();
        }
        break;
        case 2:
        {
            start = GetTickCount();
             while (N--)
            {
                fprintf(fp, "%d\n", N);
            }
            end = GetTickCount();
        }
        break;
        case 3:
        {
            srand(time(0));
            start = GetTickCount();
            while (N--)
            {
                tmp = 0 + rand() % plus;
                fprintf(fp, "%d\n", tmp);
     
                // if (!fwrite(&tmp, sizeof(long int), 1, fp))
                // {
                //     cout << "写入错误" << endl;
                // }
     
                // cout<<tmp<<endl;
            }
            end = GetTickCount();
        }
        break;
     
        default:
            break;
        }
        cout << "----------生成结束----用时:" << end - start << "ms------" << endl;
        fclose(fp);
        system("pause");
        return 0;
    }

每次都会在编译目录下生成一个文件名为10^.tds 的文件，这就是当前输出的文件，你应该给他重命名为这种格式:10^2.tds （其实就是给他加了个2，这个2就是数据量级。）并把同一模式（随机、顺序、逆序）的不同量级的数据保存在以模式名命名的文件夹里。最后把三个模式的文件夹放在一个测试数据文件夹里。大概目录就是这样。

    Test_Data
    ├─ Order
    │    ├─ 10^2.tds
    │    ├─ 10^4.tds
    │    ├─ 10^6.tds
    │    └─ 10^8.tds
    ├─ Random
    │    ├─ 10^2.tds
    │    ├─ 10^4.tds
    │    ├─ 10^6.tds
    │    └─ 10^8.tds
    └─ ReverseOrder
           ├─ 10^2.tds
           ├─ 10^4.tds
           ├─ 10^6.tds
           └─ 10^8.tds
    ​ 

点我查看目录树

我的程序里要测试百级，万级，百万级和亿级的数据，所以要提前制备好10^2.tds 10^4.tds 10^6.tds 10^8.tds 这四个东东

（为了能用文本编辑器打开测试数据，没有用二进制存储，数据大小翻了一倍（2.48 GB））

至此，我们已经完成了测试数据的制备，准备开始测试各个算法。

开门见山直接放代码:

    /*
     * @Author: Vastsea(lyx8851@qq.com)
     * @Date: 2023-05-08 22:15:52
     * @LastEditors: Vastsea(lyx8851@qq.com)
     * @LastEditTime: 2023-05-24 20:05:08
     * @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\Experiment_5\排序算法时间性能.cpp
     * @Description:
     * 采用几组不同数据测试以下排序算法的时间性能。
        直接插入排序    -ok33
        希尔排序        -ok
        冒泡排序        -ok
        快速排序        -ok
        直接选择排序    -ok
        堆排序          -ok??
        算法所用时间必须是机器时间，也可以包括比较和移动的次数。实验分析及其结果以清晰的方式来描述，如数学公式或图表等。
     
     * Link:https://59888888.xyz/
     * Phone:18893558104
     */
    #include <iostream>
    #include <cmath>
    #include <ctime>
    #include <windows.h>
    using namespace std;
    /*测试数据Path*/
    #define TEST_DATA_PATH "Test_Data/"
    #define MAX_TEST_DATA_MAGNITUDE 8
    const int e8 = 1e8;
    double startTime, endTime;
    long int Data[e8];
    void Load(long int Data[], char path[])
    {
        FILE *fp;
        int tot;
        // cout<<path<<endl;
        if (!(fp = fopen(path, "r")))
        {
            cout << "打开文件错误" << endl;
            return;
        }
        if (!fscanf(fp, "%d\n", &tot))
        {
            cout << "读总数错误" << endl;
            return;
        }
        for (int i = 0; i < tot; i++)
        {
            fscanf(fp, "%d\n", &Data[i]);
        }
        fclose(fp); // 关闭文件
    }
     
    /*直接插入排序*/
    void InsertSort(long int q[], long int n)
    {
        long int j;
        for (long int i = 2; i <= n; i++)
        {
            q[0] = q[i];
            j = i - 1;
            while (q[0] < q[j])
            {
                q[j + 1] = q[j];
                j = j - 1;
            }
            q[j + 1] = q[0];
        }
    }
     
    void Test_Insert_Sort(char Type[], int Magnitude)
    {
        // 构建文件Path
        char Data_Path[50];
        strcpy(Data_Path, TEST_DATA_PATH);
        strcat(Data_Path, Type);
        strcat(Data_Path, "/10^");
        char mag[5];
        itoa(Magnitude, mag, 10);
        strcat(Data_Path, mag);
        strcat(Data_Path, ".tds");
     
        // cout << "{----------10^" << Magnitude << "级----------}" << endl;
        // cout << "                             [数据读入中...]" << endl;
        Load(Data, Data_Path);
        // cout << "    ==========开始排序==========" << endl;
        startTime = GetTickCount();
        InsertSort(Data, pow(10, Magnitude));
        endTime = GetTickCount();
        cout << "    ---直接插入排序---" << Type << "---10^" << Magnitude << "---用时:" << endTime - startTime << "ms------" << endl
             // cout << "    ==========排序结束---直接插入排序---"<<Type<<"---10^"<<Magnitude<<"---用时:" << endTime - startTime << "ms------" << endl
             << endl
             << endl;
    }
     
    /*希尔排序*/
    void ShellSort(long int q[], long int n)
    {
        long int h = 1;
        while (h < n / 3)
        {
            h = (3 * h) + 1;
        }
        while (h >= 1)
        {
            for (long int i = h; i < n; i++)
            {
                for (long int j = i; j >= h && q[j] < q[j - h]; j -= h)
                {
                    swap(q[j], q[j - h]);
                }
            }
            h /= 3;
        }
    }
     
    void Test_Shell_Sort(char Type[], int Magnitude)
    {
        // 构建文件Path
        char Data_Path[50];
        strcpy(Data_Path, TEST_DATA_PATH);
        strcat(Data_Path, Type);
        strcat(Data_Path, "/10^");
        char mag[5];
        itoa(Magnitude, mag, 10);
        strcat(Data_Path, mag);
        strcat(Data_Path, ".tds");
     
        // cout << "{----------10^" << Magnitude << "级----------}" << endl;
        // cout << "                             [数据读入中...]" << endl;
        Load(Data, Data_Path);
        // cout << "    ==========开始排序==========" << endl;
        startTime = GetTickCount();
        ShellSort(Data, pow(10, Magnitude));
        endTime = GetTickCount();
        cout << "    ---希尔排序---" << Type << "---10^" << Magnitude << "---用时:" << endTime - startTime << "ms------" << endl
             // cout << "    ==========排序结束---希尔排序---"<<Type<<"---10^"<<Magnitude<<"---用时:" << endTime - startTime << "ms------" << endl
             << endl
             << endl;
    }
     
    /*冒泡排序-优化*/
    void BubbleSort(long int q[], long int n)
    {
        bool flag = 0;
        long int temp;
        for (long int i = 0; i < n - 1; i++)
        {
            flag = 0;
            for (long int j = 0; j < n - i - 1; j++)
            {
                if (q[j] > q[j + 1])
                {
                    temp = q[j];
                    q[j] = q[j + 1];
                    q[j + 1] = temp;
                    flag = 1;
                }
            }
            if (!flag)
                break;
        }
    }
     
    void Test_Bubble_Sort(char Type[], int Magnitude)
    {
        // 构建文件Path
        char Data_Path[50];
        strcpy(Data_Path, TEST_DATA_PATH);
        strcat(Data_Path, Type);
        strcat(Data_Path, "/10^");
        char mag[5];
        itoa(Magnitude, mag, 10);
        strcat(Data_Path, mag);
        strcat(Data_Path, ".tds");
     
        // cout << "{----------10^" << Magnitude << "级----------}" << endl;
        // cout << "                             [数据读入中...]" << endl;
        Load(Data, Data_Path);
        // cout << "    ==========开始排序==========" << endl;
        startTime = GetTickCount();
        BubbleSort(Data, pow(10, Magnitude));
        endTime = GetTickCount();
        cout << "    ---冒泡排序---" << Type << "---10^" << Magnitude << "---用时:" << endTime - startTime << "ms------" << endl
             // cout << "    ==========排序结束---直接插入排序---"<<Type<<"---10^"<<Magnitude<<"---用时:" << endTime - startTime << "ms------" << endl
             << endl
             << endl;
    }
     
    /*快速排序*/
    void Quick_Sort(long int q[], long int l, long int r)
    {
        if (l >= r)
            return;
        int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
        while (i < j)
        {
            while (q[++i] < x)
            {
            }
            while (q[--j] > x)
            {
            }
            if (i < j)
                swap(q[i], q[j]);
        }
     
        Quick_Sort(q, l, j);
        Quick_Sort(q, j + 1, r);
    }
     
    void Test_Quick_Sort(char Type[], int Magnitude)
    {
        // 构建文件Path
        char Data_Path[50];
        strcpy(Data_Path, TEST_DATA_PATH);
        strcat(Data_Path, Type);
        strcat(Data_Path, "/10^");
        char mag[5];
        itoa(Magnitude, mag, 10);
        strcat(Data_Path, mag);
        strcat(Data_Path, ".tds");
     
        // cout << "{----------10^" << Magnitude << "级----------}" << endl;
        // cout << "                             [数据读入中...]" << endl;
        Load(Data, Data_Path);
        // cout << "    ==========开始排序==========" << endl;
        startTime = GetTickCount();
        Quick_Sort(Data, 0, pow(10, Magnitude) - 1);
        endTime = GetTickCount();
        cout << "    ---快速排序---" << Type << "---10^" << Magnitude << "---用时:" << endTime - startTime << "ms------" << endl
             // cout << "    ==========排序结束---快速排序---"<<Type<<"---10^"<<Magnitude<<"---用时:" << endTime - startTime << "ms------" << endl
             << endl
             << endl;
    }
     
    /*直接选择排序*/
    void SelectSort(long int q[], long int n)
    {
        long int index;
        for (long int i = 1; i < n; i++)
        {
            index = i;
            for (long int j = i + 1; j <= n; j++)
            {
                if (q[j] < q[index])
                {
                    index = j;
                }
            }
            if (index != i)
            {
                swap(q[i], q[index]);
            }
        }
    }
     
    void Test_Select_Sort(char Type[], int Magnitude)
    {
        // 构建文件Path
        char Data_Path[50];
        strcpy(Data_Path, TEST_DATA_PATH);
        strcat(Data_Path, Type);
        strcat(Data_Path, "/10^");
        char mag[5];
        itoa(Magnitude, mag, 10);
        strcat(Data_Path, mag);
        strcat(Data_Path, ".tds");
     
        // cout << "{----------10^" << Magnitude << "级----------}" << endl;
        // cout << "                             [数据读入中...]" << endl;
        Load(Data, Data_Path);
        // cout << "    ==========开始排序==========" << endl;
        startTime = GetTickCount();
        SelectSort(Data, pow(10, Magnitude));
        endTime = GetTickCount();
        cout << "    ---直接选择排序---" << Type << "---10^" << Magnitude << "---用时:" << endTime - startTime << "ms------" << endl
             // cout << "    ==========排序结束---直接选择排序---"<<Type<<"---10^"<<Magnitude<<"---用时:" << endTime - startTime << "ms------" << endl
             << endl
             << endl;
    }
     
    /*堆排序*/
    /**
     * @description: 堆调整
     * @param {int} r 堆
     * @param {int} k 筛选结点的编号
     * @param {int} m 堆中最后一个结点的编号
     * @return {*}
     */
    void sift(long int q[], long int k, long int m)
    {
        long int i = k, j = 2 * i;
        while (j <= m) // 筛选还没有进行到叶子
        {
            if (j < m && q[j] < q[j + 1])
                j++; // 左右孩子中取较大者
            if (q[i] >= q[j])
                break;
            else
            {
                swap(q[i], q[j]);
                i = j;
                j = 2 * i;
            }
        }
    }
     
    void HeapSort(long int q[], long int n)
    {
        for (long int i = n >> 1; i >= 1; i--) // 建初始堆
        {
            sift(q, i, n);
        }
        for (long int i = 1; i < n; i++)
        {
            swap(q[1], q[n - i + 1]); // 移走堆顶
            sift(q, 1, n - i);        // 重建堆
        }
    }
     
    void Test_Heap_Sort(char Type[], int Magnitude)
    {
        // 构建文件Path
        char Data_Path[50];
        strcpy(Data_Path, TEST_DATA_PATH);
        strcat(Data_Path, Type);
        strcat(Data_Path, "/10^");
        char mag[5];
        itoa(Magnitude, mag, 10);
        strcat(Data_Path, mag);
        strcat(Data_Path, ".tds");
     
        // cout << "{----------10^" << Magnitude << "级----------}" << endl;
        // cout << "                             [数据读入中...]" << endl;
        Load(Data, Data_Path);
        // cout << "    ==========开始排序==========" << endl;
        startTime = GetTickCount();
        HeapSort(Data, pow(10, Magnitude));
        endTime = GetTickCount();
        cout << "    ---堆排序---" << Type << "---10^" << Magnitude << "---用时:" << endTime - startTime << "ms------" << endl
             // cout << "    ==========排序结束---堆排序---"<<Type<<"---10^"<<Magnitude<<"---用时:" << endTime - startTime << "ms------" << endl
             << endl
             << endl;
    }
     
    int main()
    {
        cout << "**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&*--|直接插入排序" << endl;
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|随机数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Insert_Sort("Random", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|顺序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Insert_Sort("Order", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|逆序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Insert_Sort("ReverseOrder", i);
        }
        //-----------------------------------------------------------------------------------------------------------------------------//
        cout << "**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&*--|希尔排序" << endl;
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|随机数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Shell_Sort("Random", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|顺序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Shell_Sort("Order", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|逆序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Shell_Sort("ReverseOrder", i);
        }
        //-----------------------------------------------------------------------------------------------------------------------------//
        cout << "**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&*--|冒泡排序" << endl;
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|随机数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Bubble_Sort("Random", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|顺序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Bubble_Sort("Order", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|逆序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Bubble_Sort("ReverseOrder", i);
        }
        //-----------------------------------------------------------------------------------------------------------------------------//
        cout << "**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&*--|快速排序" << endl;
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|随机数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Quick_Sort("Random", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|顺序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Quick_Sort("Order", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|逆序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Quick_Sort("ReverseOrder", i);
        }
        // -----------------------------------------------------------------------------------------------------------------------------//
        cout << "**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&*--|直接选择排序" << endl;
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|随机数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Select_Sort("Random", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|顺序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Select_Sort("Order", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|逆序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Select_Sort("ReverseOrder", i);
        }
        // -----------------------------------------------------------------------------------------------------------------------------//
        cout << "**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&**&*--|堆排序" << endl;
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|随机数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Heap_Sort("Random", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|顺序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Heap_Sort("Order", i);
        }
        cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--|逆序数据" << endl;
        for (int i = 2; i <= MAX_TEST_DATA_MAGNITUDE; i += 2)
        {
            Test_Heap_Sort("ReverseOrder", i);
        }
        //-----------------------------------------------------------------------------------------------------------------------------//
        system("pause");
        system("pause");
        system("pause");
        system("pause");
        system("pause");
        return 0;
    }

在主函数里操作每个算法的测试函数去测试不同的算法，Test_xxx_Sort("ReverseOrder", i) 型的函数是xxxSort的测试函数，需要传入两个参数：测试数据类型、数据量。这两个传参都是为了构建测试数据文件的路径。（所以可以改改直接传入测试文件路径）

走到一个Test_xxx_Sort("ReverseOrder", i)型函数里面看看，最先的几行是测试数据文件路径的构建，就是个简单的字符串拼接（所以要按照上面说的来构建文件结构）。然后就是Load(Data, Data_Path)载入测试数据到Data数组，Data在最开始的时候开了1e8，够用的（数据也会有1e8的，所以int都用long int）。

之后就是传数组到函数里去排序，各个算法的传参基本上一样，就不赘述了。

关于如何算时间的问题，这个我之前写过一篇笔记，可以去看看，补充一点，那个函数是windows.h提供的，要记得引入。