C++ 寻找第 K 大的数：快速选择算法优化

C++:\u00a0可多和班级里的朋友在玩数字排序的游戏，可多想要找到n个数x中第k大的数是多少？如果不存在第k大的数，则输出NULL。\n输入描述：总共输入两行\n\n第一行两个整数，分别表示n和k\n第二行有n个乱序的数据x\n输出描述：输出一个，表示第k大的数是多少\n使用选择排序算法，时间复杂度要多低有多低\n\n选择排序的时间复杂度是O(n^2)，对于较大的n值可能效率较低。如果要求时间复杂度更低的算法，可以使用快速选择算法。\n\n快速选择算法的基本思想是利用快速排序的分区操作，每次选取一个基准元素将数组分为两部分，并确定基准元素的位置。如果基准元素的位置等于k，则该元素即为第k大的数；如果基准元素的位置大于k，则在左半部分继续进行快速选择；如果基准元素的位置小于k，则在右半部分继续进行快速选择。\n\n下面是使用快速选择算法实现找到第k大的数的示例代码：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nint quickSelect(std::vector<int>& nums, int left, int right, int k) {\n int pivot = nums[right];\n int i = left;\n for (int j = left; j < right; j++) {\n if (nums[j] >= pivot) {\n std::swap(nums[i], nums[j]);\n i++;\n }\n }\n std::swap(nums[i], nums[right]);\n\n if (i - left + 1 == k) {\n return nums[i];\n } else if (i - left + 1 > k) {\n return quickSelect(nums, left, i - 1, k);\n } else {\n return quickSelect(nums, i + 1, right, k - (i - left + 1));\n }\n}\n\nint main() {\n int n, k;\n std::cin >> n >> k;\n\n std::vector<int> nums(n);\n for (int i = 0; i < n; i++) {\n std::cin >> nums[i];\n }\n\n int result = quickSelect(nums, 0, n - 1, k);\n if (result != INT_MIN) {\n std::cout << result << std::endl;\n } else {\n std::cout << "NULL" << std::endl;\n }\n\n return 0;\n}\n\n\n这段代码将输入的n个数存储在一个vector中，然后调用quickSelect函数找到第k大的数，并输出结果。如果不存在第k大的数，则输出"NULL"。