编辑代码

#include <stdio.h>

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

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 quickSelect(int arr[], int low, int high, int k) {
    if (k > 0 && k <= high - low + 1) {
        int pi = partition(arr, low, high);
        if (pi - low == k - 1) {
            return arr[pi];
        }
        if (pi - low > k - 1) {
            return quickSelect(arr, low, pi - 1, k);
        }
        return quickSelect(arr, pi + 1, high, k - pi + low - 1);
    }
    return -1;
}

int main() {
    int arr[] = {9,4,8,7,5,2,1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    int result = quickSelect(arr, 0, n - 1, k);
    if (result == -1) {
        printf("K超出界限\n");
    } else {
        printf("第%d大的元素为：%d\n", k, result);
    }
    return 0;
}