编辑代码

#include <stdio.h>

int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low;
    int j = high + 1;

    while (1) {
        while (arr[++i] < pivot) {
            if (i == high)
                break;
        }
        while (arr[--j] > pivot) {
            if (j == low)
                break;
        }
        if (i >= j)
            break;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    int temp = arr[low];
    arr[low] = arr[j];
    arr[j] = temp;

    return j;
}

int quickSelect(int arr[], int low, int high, int k) {
    if (low == high)
        return arr[low];

    int pivotIndex = partition(arr, low, high);

    if (pivotIndex == k - 1)
        return arr[pivotIndex];
    else if (pivotIndex < k - 1)
        return quickSelect(arr, pivotIndex + 1, high, k);
    else
        return quickSelect(arr, low, pivotIndex - 1, k);
}

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

int main() {
    int arr[] = {3, 7, 1, 12, 9, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    int kthLargest = findKthLargest(arr, size, k);
    printf("The %dth largest element is %d\n", k, kthLargest);

    printf("====================================\n");

    int arr0[] = {-3, 7, -1, 12, -9, 2};
    size = sizeof(arr0) / sizeof(arr[0]);
    k = 4;
    kthLargest = findKthLargest(arr0, size, k);
    printf("The %dth largest element is %d\n", k, kthLargest);

    printf("====================================\n");

    int arr1[] = {1};
    size = sizeof(arr1) / sizeof(arr[0]);
    k = 2;
    kthLargest = findKthLargest(arr1, size, k);
    printf("The %dth largest element is %d\n", k, kthLargest);

    return 0;
}