计算机算法设计与分析，运用c++完成下列题目：K小值问题（推荐使用分区函数，随机选择基准元素进行快速选择） 给定一个数组，要求找出数组中第k小的元素。 例如，给定数组[3, 2, 1, 5, 4]，要求找出第3小的元素，即3。 输出结果：3

在计算机算法设计中，K小值问题是求解数组中第k个最小元素的问题。快速选择（QuickSelect）是对快速排序的一种变种，专门用于解决这个问题。它的核心思想是利用了快速排序的分区过程，不过不再进行完全排序，而是找到第k个分割点。

以下是C++实现快速选择算法的示例：

#include <iostream>
#include <cstdlib> // 需要用到rand()
#include <ctime>

// 交换两个元素的位置
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 随机选择基准元素
int randomPartition(int arr[], int low, int high) {
    int rand_idx = low + rand() % (high - low + 1); // 随机索引
    swap(&arr[rand_idx], &arr[high]);
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速选择函数，找到第k小的元素
int quickSelect(int arr[], int low, int high, int k) {
    if (low == high) { // 只有一个元素的情况
        return arr[low];
    }

    int pivot_index = randomPartition(arr, low, high);

    // 如果 k 等于分区后的中间值，直接返回
    if (pivot_index == k)
        return arr[pivot_index];
    else if (pivot_index > k) // k 在左半边
        return quickSelect(arr, low, pivot_index - 1, k);
    else // k 在右半边
        return quickSelect(arr, pivot_index + 1, high, k);
}

// 测试示例
int main() {
    int arr[] = {3, 2, 1, 5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3; // 要找的第k小的元素

    int kthSmallest = quickSelect(arr, 0, n - 1, k - 1); // 注意这里是k-1，因为索引从0开始计数

    cout << "The kth smallest element is: " << kthSmallest << endl;

    return 0;
}

上述代码会在数组`arr`中找到第k小的元素。对于给定的数组 `[3, 2, 1, 5, 4]` 和 k=3，输出结果将是 `3`。