C语言 利用线性时间选择查找无序数组中第K大元素

可以使用快速选择算法，在O(n)的时间复杂度内查找无序数组中第K大的元素。具体实现可以参考以下代码：

#include <stdio.h>

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

int kthLargest(int arr[], int low, int high, int k) {
    if (k > 0 && k <= high - low + 1) {
        int pos = partition(arr, low, high);
        if (pos - low == k - 1) {
            return arr[pos];
        } else if (pos - low > k - 1) {
            return kthLargest(arr, low, pos - 1, k);
        } else {
            return kthLargest(arr, pos + 1, high, k - pos + low - 1);
        }
    }
    return -1;
}

int main() {
    int arr[] = {3, 2, 1, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    int kth = kthLargest(arr, 0, n - 1, k);
    printf("%dth largest element is %d\n", k, kth);
    return 0;
}

对于无序数组{3, 2, 1, 5, 6, 4}，查找第2大的元素，输出结果为：

2th largest element is 5