编辑代码

#include <stdio.h>

// 根据基准值进行分区，把比基准值大的元素放右边，小的元素放左边
// 返回值：基准值在排序后的位置
int partition(int arr[], int arrStart, int arrEnd) {
    int pivotValue = arr[arrEnd - 1];
    int pivotIndex = arrStart;
    for (int i = arrStart; i < arrEnd - 1; i++) {
        if (arr[i] > pivotValue) {
            int temp = arr[i];
            arr[i] = arr[pivotIndex];
            arr[pivotIndex] = temp;
            pivotIndex++;
        }
    }
    int temp = arr[pivotIndex];
    arr[pivotIndex] = arr[arrEnd - 1];
    arr[arrEnd - 1] = temp;
    return pivotIndex;
}

// 在无序数组中查找第 k 大元素的函数
int findKthLargest(int arr[], int arrStart, int arrEnd, int k) {
    int pos = partition(arr, arrStart, arrEnd);
    int rank = pos - arrStart + 1;
    if (rank == k) {
        return arr[pos];
    } else if (rank < k) {
        return findKthLargest(arr, pos + 1, arrEnd, k - rank);
    } else {
        return findKthLargest(arr, arrStart, pos, k);
    }
}

int main() {
    int arr[] = {3,44,38,5,47,15,36,27,2,46,4,19,50,48}; 
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("数组arr：");
    for (int i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    int k = 2; // 要找的第 k 大的元素
    int result = findKthLargest(arr, 0, n, k);
    printf("第%d大的元素是：%d", k, result);
    return 0;
}