C++快速选择算法求解第k小元素实现

以下是使用快速选择算法（QuickSelect）求解第k小数的C++代码实现。 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int partition(vector<int>& arr, int left, int right) { int pivot = arr[left]; // 选择最左侧元素作为基准 int i = left, j = right; while (i < j) { // 从右向左找第一个小于pivot的元素 while (i < j && arr[j] >= pivot) j--; if (i < j) arr[i++] = arr[j]; // 从左向右找第一个大于等于pivot的元素 while (i < j && arr[i] < pivot) i++; if (i < j) arr[j--] = arr[i]; } arr[i] = pivot; return i; } int quickSelect(vector<int>& arr, int left, int right, int k) { if (left == right) return arr[left]; int pivotIndex = partition(arr, left, right); int count = pivotIndex - left + 1; // 左半部分元素个数 if (k == count) { return arr[pivotIndex]; } else if (k < count) { return quickSelect(arr, left, pivotIndex - 1, k); } else { return quickSelect(arr, pivotIndex + 1, right, k - count); } } int main() { int n, k; cin >> n >> k; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } int result = quickSelect(arr, 0, n - 1, k); cout << result << endl; return 0; } ``` ## 算法说明 **快速选择算法**是快速排序的变种，专门用于查找第k小（或第k大）的元素。 分区函数 `partition` 将数组分为两部分： - 左边的元素都小于基准值 - 右边的元素都大于等于基准值 主函数 `quickSelect` 根据分区结果判断： - 如果基准位置的索引恰好是第k小元素，直接返回 - 如果k小于左半部分元素个数，在左半部分继续查找 - 如果k大于左半部分元素个数，在右半部分查找第 k - count 小的元素 ## 复杂度分析 - 平均时间复杂度：O(n) - 最坏时间复杂度：O(n²)（当数组已经有序或逆序时） - 空间复杂度：O(log n)（递归调用栈的深度） ######[AI问答 | 594点数解答 | 2026-06-12 20:09:43]