请用C语言实现程序-查找数组中第K大的数字要求时间复杂度nlogn

一种常见的解法是使用快速排序的思想，每次将数组分成两部分，一部分大于某个数，一部分小于等于某个数，然后根据第K大的位置在哪一部分递归查找，直到找到第K大的数为止。时间复杂度为O(nlogn)。

具体实现如下：

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

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

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

输出结果为：

The 4th largest element is 5