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

1.测试数据集的生成

为了测试快速排序算法在不同大小数据集上的性能，我们需要生成不同大小的随机数组。以下是生成随机数组的代码：

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

using namespace std;

// 生成指定长度的随机数组
void generateRandomArray(int arr[], int length)
{
    // 以当前时间为种子，生成随机数
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    default_random_engine generator(seed);

    uniform_int_distribution<int> distribution(0, length);

    for (int i = 0; i < length; i++)
    {
        arr[i] = distribution(generator);
    }
}

int main()
{
    int arr1[100];
    int arr2[1000];
    int arr3[10000];
    int arr4[100000];

    generateRandomArray(arr1, 100);
    generateRandomArray(arr2, 1000);
    generateRandomArray(arr3, 10000);
    generateRandomArray(arr4, 100000);

    // 输出数组中前10个元素，以验证随机性
    for (int i = 0; i < 10; i++)
    {
        cout << arr1[i] << " ";
    }
    cout << endl;

    for (int i = 0; i < 10; i++)
    {
        cout << arr2[i] << " ";
    }
    cout << endl;

    for (int i = 0; i < 10; i++)
    {
        cout << arr3[i] << " ";
    }
    cout << endl;

    for (int i = 0; i < 10; i++)
    {
        cout << arr4[i] << " ";
    }
    cout << endl;

    return 0;
}

2.快速排序算法的实现

快速排序算法的核心思想是分治法，通过选取一个基准元素，将数组分为两个子数组，其中一个子数组的元素都比基准元素小，另一个子数组的元素都比基准元素大。然后对两个子数组分别递归地进行快速排序，最终得到有序数组。

以下是快速排序算法的代码实现：

#include <iostream>
#include <chrono>

using namespace std;

// 快速排序
void quickSort(int arr[], int left, int right)
{
    if (left >= right)
    {
        return;
    }

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

    while (i <= j)
    {
        while (arr[i] < pivot)
        {
            i++;
        }

        while (arr[j] > pivot)
        {
            j--;
        }

        if (i <= j)
        {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }

    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

int main()
{
    int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    quickSort(arr, 0, 9);

    for (int i = 0; i < 10; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

3.快速排序算法在测试集上的性能分析

我们使用前面生成的四个随机数组，分别对其进行快速排序，并计算排序时间。以下是快速排序算法在不同大小数据集上的性能分析代码：

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

using namespace std;

// 生成指定长度的随机数组
void generateRandomArray(int arr[], int length)
{
    // 以当前时间为种子，生成随机数
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    default_random_engine generator(seed);

    uniform_int_distribution<int> distribution(0, length);

    for (int i = 0; i < length; i++)
    {
        arr[i] = distribution(generator);
    }
}

// 快速排序
void quickSort(int arr[], int left, int right)
{
    if (left >= right)
    {
        return;
    }

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

    while (i <= j)
    {
        while (arr[i] < pivot)
        {
            i++;
        }

        while (arr[j] > pivot)
        {
            j--;
        }

        if (i <= j)
        {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }

    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

// 计算快速排序时间
double calculateQuickSortTime(int arr[], int length)
{
    auto start = chrono::high_resolution_clock::now();
    quickSort(arr, 0, length - 1);
    auto end = chrono::high_resolution_clock::now();

    chrono::duration<double> diff = end - start;

    return diff.count();
}

int main()
{
    int arr1[100];
    int arr2[1000];
    int arr3[10000];
    int arr4[100000];

    generateRandomArray(arr1, 100);
    generateRandomArray(arr2, 1000);
    generateRandomArray(arr3, 10000);
    generateRandomArray(arr4, 100000);

    cout << "快速排序在数组长度为100的数据集上的运行时间为：" << calculateQuickSortTime(arr1, 100) << "秒" << endl;
    cout << "快速排序在数组长度为1000的数据集上的运行时间为：" << calculateQuickSortTime(arr2, 1000) << "秒" << endl;
    cout << "快速排序在数组长度为10000的数据集上的运行时间为：" << calculateQuickSortTime(arr3, 10000) << "秒" << endl;
    cout << "快速排序在数组长度为100000的数据集上的运行时间为：" << calculateQuickSortTime(arr4, 100000) << "秒" << endl;

    return 0;
}

通过运行上面的代码，我们可以得到快速排序算法在不同大小数据集上的运行时间