请用C++语言完整的写一遍代码
时间: 2024-10-02 21:01:07 浏览: 14
当然可以,这里是一个简单的C++代码示例,它展示了如何使用快速选择算法找到一个整数数组中的第\( K \)小元素:
```cpp
#include <vector>
#include <cstdlib>
#include <ctime>
// 用于交换两个元素的辅助函数
void swap(std::vector<int>& a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// 分区函数,将数组分为两部分,左边的元素都小于基准值
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 使用最后一个元素作为基准
int i = low - 1;
for (int j = low; j <= high - 1; ++j) {
if (arr[j] < pivot) {
++i;
swap(arr, i, j);
}
}
swap(arr, i + 1, high); // 把基准放到正确的位置
return i + 1;
}
// 快速选择函数
int quick_select(std::vector<int>& arr, int low, int high, int k) {
if (low == high) {
return arr[low]; // 如果只有一个元素,那就是最小的
}
int pivot_index = partition(arr, low, high);
// 根据基准的位置调整k
if (k == pivot_index) {
return arr[k];
} else if (k < pivot_index) {
return quick_select(arr, low, pivot_index - 1, k);
} else {
return quick_select(arr, pivot_index + 1, high, k - pivot_index - 1);
}
}
int main() {
const int size = 10;
std::vector<int> arr(size);
srand(time(0)); // 初始化随机数生成器
// 填充随机整数到数组
for (int& num : arr) {
num = rand() % size;
}
int k;
std::cout << "请输入要找的第 K 小元素的位置:";
std::cin >> k;
int kth_smallest = quick_select(arr, 0, arr.size() - 1, k - 1); // 注意索引是从0开始的
std::cout << "第 " << k << " 小的元素是:" << kth_smallest << "\n";
return 0;
}
```
这个程序首先创建了一个随机整数数组,然后从用户输入获取 \( K \) 的值,最后调用 `quick_select` 函数找到第 \( K \) 小的元素并打印出来。