编辑代码

#include <stdio.h>

// 交换两个整数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 划分函数，返回枢轴位置
int partition(int arr[], int left, int right) {
    // 选择最右边的元素作为枢轴
    int pivot = arr[right];
    int i = left - 1;
    
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    
    swap(&arr[i + 1], &arr[right]);
    return i + 1;
}

// 随机选择枢轴并进行划分
int randomPartition(int arr[], int left, int right) {
    // 为简单起见，这里直接使用最右元素作为枢轴
    // 实际应用中可以随机选择枢轴以提高效率
    return partition(arr, left, right);
}

// 快速选择算法
int quickSelect(int arr[], int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }
    
    int pivotIndex = randomPartition(arr, left, right);
    int count = pivotIndex - left + 1; // 枢轴是第几小的元素
    
    if (count == k) {
        return arr[pivotIndex];
    } else if (k < count) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k - count);
    }
}

int main() {
    int n, k;
    int arr[100]; // 题目说明n最大为100
    
    while (scanf("%d %d", &n, &k) != EOF) {
        // 读取数组元素
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
        
        // 找出第k小的元素
        int result = quickSelect(arr, 0, n - 1, k);
        printf("%d\n", result);
    }
    
    return 0;
}