编辑代码

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

int quick_select(int arr[], int low, int high, int k) {
    if(low == high) {
        return arr[low];
    }
    
    int pivotIndex = partition(arr, low, high);
    int rank = pivotIndex - low + 1; // 排名
    
    if(k == rank) {
        return arr[pivotIndex];
    }
    else if (k < rank) {
        return quick_select(arr, low, pivotIndex - 1, k);
    }
    else {
        return quick_select(arr, pivotIndex + 1, high, k - rank);
    }
}

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

int main() {
    int arr[] = {7, 10, 4, 3, 20, 15};
    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);
    
    return 0;
}