用c语言实现：查找一个数组中第k大的元素，时间复杂度为o(n)

可以使用快速选择算法（QuickSelect Algorithm）来实现在 O(n) 时间复杂度内查找数组中第 k 大的元素。

快速选择算法的基本思路与快速排序类似，都是通过分治的思想将问题规模不断缩小。但是，快速选择算法只需要对单边递归进行处理，而不需要对两边都递归处理。具体步骤如下：

1. 选择数组中的一个元素作为 pivot 元素。
2. 将数组中小于 pivot 的元素放在 pivot 左边，大于 pivot 的元素放在 pivot 右边。这个过程可以使用 partition 函数实现，可以参考快速排序的实现。
3. 如果 pivot 的位置恰好为 k-1，则 pivot 就是第 k 大的元素，直接返回。
4. 如果 pivot 的位置小于 k-1，则第 k 大的元素在 pivot 右边，对右边的元素再进行快速选择。
5. 如果 pivot 的位置大于 k-1，则第 k 大的元素在 pivot 左边，对左边的元素再进行快速选择。

下面是一个基于快速选择算法的实现：

int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; 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[right];
    arr[right] = temp;
    return i + 1;
}

int quickSelect(int arr[], int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }
    int pivotIndex = partition(arr, left, right);
    if (pivotIndex == k - 1) {
        return arr[pivotIndex];
    } else if (pivotIndex < k - 1) {
        return quickSelect(arr, pivotIndex + 1, right, k);
    } else {
        return quickSelect(arr, left, pivotIndex - 1, k);
    }
}

int findKthLargest(int arr[], int size, int k) {
    return quickSelect(arr, 0, size - 1, size - k + 1);
}

其中，`partition` 函数用于将数组分成左右两个部分，`quickSelect` 函数用于递归地进行快速选择，`findKthLargest` 函数是对外的接口，用于调用 `quickSelect` 函数并返回结果。

需要注意的是，在 `quickSelect` 函数中，`k` 的值是倒数第 k 大的元素在数组中的位置，因此需要将 `size - k + 1` 作为 `quickSelect` 的参数传入，最终返回的是第 k 大的元素的值。