请用C语言实现程序-查找数组中第K大的数字要求不能使用排序预处理数组

一种常见的解法是使用快速选择算法，它可以在平均情况下在O(n)时间内找到第K大的数字。具体实现如下：

#include <stdio.h>

// 交换两个数的值
void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 在数组a的[l, r]区间内选择一个枢轴元素，并把小于枢轴的元素放在左边，大于枢轴的元素放在右边
// 返回枢轴元素的下标
int partition(int a[], int l, int r) {
    int pivot = a[r]; // 选择最后一个元素作为枢轴
    int i = l - 1; // i是小于枢轴的元素的右边界
    for (int j = l; j < r; j++) {
        if (a[j] >= pivot) { // 把大于等于枢轴的元素放在右边
            i++;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i + 1], &a[r]); // 把枢轴放在它正确的位置上
    return i + 1;
}

// 在数组a的[l, r]区间内查找第k大的元素
int quick_select(int a[], int l, int r, int k) {
    if (l == r) {
        return a[l]; // 如果区间只有一个元素，那么它就是第1大的元素
    }
    int pivot_index = partition(a, l, r); // 获取枢轴的下标
    int rank = pivot_index - l + 1; // 计算枢轴的排名
    if (k == rank) {
        return a[pivot_index]; // 如果k刚好等于枢轴的排名，那么枢轴就是第k大的元素
    } else if (k < rank) {
        return quick_select(a, l, pivot_index - 1, k); // 如果k小于枢轴的排名，那么在左边区间查找第k大的元素
    } else {
        return quick_select(a, pivot_index + 1, r, k - rank); // 如果k大于枢轴的排名，那么在右边区间查找第k - rank大的元素
    }
}

int main() {
    int a[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 3;
    int kth_largest = quick_select(a, 0, n - 1, k); // 查找第k大的元素
    printf("The %dth largest number is %d.\n", k, kth_largest);
    return 0;
}

这个程序的核心是quick_select函数，它实现了快速选择算法的递归过程。在每次递归中，我们选择一个枢轴元素，并把小于枢轴的元素放在左边，大于枢轴的元素放在右边。然后我们计算枢轴的排名，如果它就是我们要找的第k大的元素，就返回它；否则，如果k小于它的排名，就在左边区间递归查找第k大的元素，否则就在右边区间递归查找第k - rank大的元素。在这个过程中，我们不需要对整个数组进行排序，只需要递归处理一部分数组，所以时间复杂度为O(n)。