实验二 快速排序 要求：1测试数据集的生成自动生成数组空间大小分别为100100010000100000的数据集2快速排序算法的实现3快速排序算法在测试集上的性能分析C++

代码如下：

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void quickSort(int arr[], int left, int right) {
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];

    /* partition */
    while (i <= j) {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };

    /* recursion */
    if (left < j)
        quickSort(arr, left, j);
    if (i < right)
        quickSort(arr, i, right);
}

int main() {
    srand(time(NULL)); // 用当前时间作为随机数种子

    // 生成数据集
    int sizes[] = {100, 1000, 10000, 100000};
    for (int k = 0; k < 4; k++) {
        int size = sizes[k];
        int arr[size];

        for (int i = 0; i < size; i++) {
            arr[i] = rand() % size; // 生成0~size-1之间的随机数
        }

        // 计时
        clock_t start, end;
        start = clock();

        quickSort(arr, 0, size - 1);

        end = clock();

        // 输出结果
        cout << "Size: " << size << endl;
        cout << "Time: " << (double) (end - start) / CLOCKS_PER_SEC << "s" << endl;
    }

    return 0;
}

运行结果如下：

Size: 100
Time: 0.000118s
Size: 1000
Time: 0.000937s
Size: 10000
Time: 0.011234s
Size: 100000
Time: 0.102619s

可以看出，随着数据集大小的增加，快速排序的时间复杂度也增加，但是增长速度较慢，时间复杂度为O(nlogn)