C++ 查找第 k 大的数 - 选择排序算法实现

本篇文章将介绍如何使用 C++ 实现查找数组中第 k 大的数，并使用选择排序算法进行演示。

算法原理

选择排序算法的思路是，每次从未排序的子序列中找到最大（或最小）的元素，将其与子序列的第一个元素交换位置。经过 n-1 次迭代，数组就被排序了。在本例中，我们只需要进行 k 次迭代，找到前 k 个最大的元素，最后返回第 k 个元素即可。

代码实现

#include <iostream>
using namespace std;
int findKthLargest(int arr[], int n, int k) {
for (int i = 0; i < k; i++) {
int maxIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
swap(arr[i], arr[maxIndex]);
}
if (k &lt;= n) {
    return arr[k-1];
} else {
    return NULL;
}

}
int main() {
int n, k;
cin >> n >> k;
int arr[n];
for (int i = 0; i &lt; n; i++) {
    cin &gt;&gt; arr[i];
}

int kthLargest = findKthLargest(arr, n, k);
if (kthLargest == NULL) {
    cout &lt;&lt; "NULL" &lt;&lt; endl;
} else {
    cout &lt;&lt; kthLargest &lt;&lt; endl;
}

return 0;

}

示例

输入示例

5 3
4 2 7 1 6

输出示例

4

在上述示例中，输入的数组为 {4, 2, 7, 1, 6}，k 为 3。代码会找出前 3 个最大的元素 {7, 6, 4}，并返回第 3 大的元素 4。

总结

本文介绍了如何使用 C++ 和选择排序算法查找数组中第 k 大的数。该代码简单易懂，并附带示例输入和输出，方便理解和使用。