C语言算法问答集：算法竞赛的入门与实战

#include <stdio.h>
#include <stdlib.h>

// 快速排序分区函数
int partition(int *arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= (high - 1); 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);
}

// 快速排序
void quickSort(int *arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 查找第 k 大的元素
int findKthLargest(int *arr, int n, int k) {
    quickSort(arr, 0, n - 1);
    return arr[n - k];
}

int main() {
    int arr[] = {4, 2, 9, 7, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    int k = 3;

    int result = findKthLargest(arr, n, k);

    printf("第 %d 大的元素是 %d\n", k, result);

    return 0;
}