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

利用线性时间选择算法，可以在无序数组中找到第K大的元素。以下是一个基于快速选择算法的简单实现：

#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;
}

// 线性时间选择算法，找到数组中第K大的元素
int kthLargest(int arr[], int low, int high, int k) {
    if (k > 0 && k <= high - low + 1) {
        // 执行分区操作，获取枢轴位置
        int pivotIndex = partition(arr, low, high);

        // 如果枢轴的位置等于要找的位置K，则返回该元素
        if (pivotIndex - low == k - 1) {
            return arr[pivotIndex];
        }

        // 如果枢轴的位置大于K，则在左侧递归查找
        if (pivotIndex - low > k - 1) {
            return kthLargest(arr, low, pivotIndex - 1, k);
        }

        // 在右侧递归查找
        return kthLargest(arr, pivotIndex + 1, high, k - pivotIndex + low - 1);
    }

    // 如果K不在有效范围内，返回一个标志值
    return -1;
}

int main() {
    int arr[] = {12, 3, 5, 7, 4, 19, 26};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3; // 要找的第K大的元素

    int result = kthLargest(arr, 0, n - 1, k);

    if (result != -1) {
        printf("第%d大的元素是：%d\\n", k, result);
    } else {
        printf("无效的K值\\n");
    }

    return 0;
}

这个程序中，kthLargest函数使用快速选择算法，在给定的无序数组中查找第K大的元素。