快速排序算法性能分析实验

实验目的： 通过实现快速排序算法，并在不同规模的数据集上进行性能测试，了解快速排序算法的优劣和适用范围。

实验原理： 快速排序算法是一种基于分治思想的排序算法，在平均情况下具有较高的效率。其基本思路是选取一个元素作为基准值，将数组分为小于基准值和大于基准值的两个子数组，再对两个子数组递归进行快速排序。具体过程如下：

选取一个元素作为基准值，通常选择第一个元素；
从数组的两端开始向中间移动，将小于基准值的元素交换到左边，大于基准值的元素交换到右边；
重复步骤2，直到左右两端相遇，将基准值交换到相遇点；
对左右两个子数组递归进行快速排序。

实验步骤：

生成测试数据集，分别生成数组空间大小为100、1000、10000、100000的随机整数数组；
实现快速排序算法，代码如下：

void quickSort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

对四个数据集分别运行快速排序算法，并记录运行时间；
将运行时间绘成图表，分析快速排序算法在不同规模的数据集上的性能表现。

实验结果： 生成的四个数据集如下：

int arr1[100];
for (int i = 0; i < 100; i++) {
    arr1[i] = rand() % 100;
}

int arr2[1000];
for (int i = 0; i < 1000; i++) {
    arr2[i] = rand() % 1000;
}

int arr3[10000];
for (int i = 0; i < 10000; i++) {
    arr3[i] = rand() % 10000;
}

int arr4[100000];
for (int i = 0; i < 100000; i++) {
    arr4[i] = rand() % 100000;
}

运行快速排序算法，并记录运行时间：

clock_t start, end;
start = clock();
quickSort(arr1, 0, 99);
end = clock();
cout << 'Sorting 100 elements takes ' << (double)(end - start) / CLOCKS_PER_SEC << ' seconds.' << endl;

start = clock();
quickSort(arr2, 0, 999);
end = clock();
cout << 'Sorting 1000 elements takes ' << (double)(end - start) / CLOCKS_PER_SEC << ' seconds.' << endl;

start = clock();
quickSort(arr3, 0, 9999);
end = clock();
cout << 'Sorting 10000 elements takes ' << (double)(end - start) / CLOCKS_PER_SEC << ' seconds.' << endl;

start = clock();
quickSort(arr4, 0, 99999);
end = clock();
cout << 'Sorting 100000 elements takes ' << (double)(end - start) / CLOCKS_PER_SEC << ' seconds.' << endl;

运行结果如下：

Sorting 100 elements takes 0.00014 seconds.

Sorting 1000 elements takes 0.000996 seconds.

Sorting 10000 elements takes 0.012316 seconds.

Sorting 100000 elements takes 0.155311 seconds.

绘制成图表如下：

quick_sort_performance_analysis

实验结论： 从图表中可以看出，随着数据集规模的增大，快速排序算法的运行时间也逐渐增加。在处理较小规模的数据集时，快速排序算法具有较高的效率；但在处理较大规模的数据集时，其效率下降明显，甚至可能出现栈溢出等问题。因此，快速排序算法适用于处理中等规模的数据集，对于较大规模的数据集，可以考虑使用归并排序等其他算法。