C++ 快速排序算法实现及性能分析

本文介绍了快速排序算法的 C++ 实现，并通过测试数据集分析了其性能。

1. 测试数据集的生成

为了评估快速排序算法的性能，需要生成不同大小的测试数据集。代码中使用 srand(time(NULL)) 函数以当前时间作为随机数种子，并利用 rand() % size 生成 0 到 size-1 之间的随机数，来填充数组。

2. 快速排序算法的实现

快速排序算法的核心是分治法。其基本思想是：

选择数组中的一个元素作为基准（pivot）。
将数组划分为两个子数组，一个子数组包含所有小于基准的元素，另一个子数组包含所有大于基准的元素。
递归地对两个子数组进行排序。

以下代码展示了 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;
}

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

代码中使用 clock() 函数记录排序开始和结束的时间，并计算排序所花费的时间。测试结果如下：

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

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

总结

本文介绍了快速排序算法的 C++ 实现，并通过测试数据集分析了其性能。快速排序算法是一种高效的排序算法，其平均时间复杂度为 O(nlogn)，适用于对大量数据进行排序。