用BFPRT算法求第k小元素的c语言代码，其中数组和数组元素个数需要用户输入

好的，以下是用BFPRT算法求第k小元素的C语言代码，其中数组和数组元素个数需要用户输入。

#include <stdio.h>

// 使用BFPRT算法求第k小元素
int BFPRT(int arr[], int left, int right, int k);

// 交换数组中的两个元素
void swap(int arr[], int i, int j);

// 用插入排序求中位数
int median(int arr[], int left, int right);

// 使用快速排序对数组进行划分并返回枢轴元素下标
int partition(int arr[], int left, int right, int pivot);

// 获取数组中第k小的元素下标
int kthSmallest(int arr[], int n, int k);

int main() {
    int n, k, arr[1000], i;
    printf("请输入数组元素个数n: ");
    scanf("%d", &n);
    printf("请输入数组元素: ");
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    printf("请输入第k小的k值: ");
    scanf("%d", &k);
    printf("第%d小的元素为: %d", k, kthSmallest(arr, n, k));
    return 0;
}

// 使用BFPRT算法求第k小元素
int BFPRT(int arr[], int left, int right, int k) {

    int i, j, pivot;

    // 将数组分为若干个大小为5的子数组
    for(i = left; i <= right; i += 5) {
        // 对每个子数组进行插入排序
        j = i + 4;
        if(j > right) {
            j = right;
        }
        int temp, m;
        for(m = i + 1; m <= j; m++) {
            temp = arr[m];
            int n;
            for(n = m - 1; n >= i && arr[n] > temp; n--) {
                arr[n+1] = arr[n];
            }
            arr[n+1] = temp;
        }
        // 将子数组中位数与数组左端元素交换，并进行下一轮划分
        swap(arr, left + (i - left) / 5, i + 2);
    }

    // 取中位数的中位数作为枢轴元素
    if(right - left < 5) {
        pivot = median(arr, left, right);
    } else {
        pivot = BFPRT(arr, left, left + (right - left) / 5, (right - left) / 10);
    }

    // 根据枢轴元素进行划分，并返回枢轴元素下标
    return partition(arr, left, right, pivot);
}

// 交换数组中的两个元素
void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 用插入排序求中位数
int median(int arr[], int left, int right) {
    int i, j, temp;
    for(i = left + 1; i <= right; i++) {
        temp = arr[i];
        for(j = i - 1; j >= left && arr[j] > temp; j--) {
            arr[j+1] = arr[j];
        }
        arr[j+1] = temp;
    }
    return arr[(left + right) / 2];
}

// 使用快速排序对数组进行划分并返回枢轴元素下标
int partition(int arr[], int left, int right, int pivot) {
    int i = left, j = left;
    while(j < right) {
        if(arr[j] < pivot) {
            swap(arr, i, j);
            i++;
        }
        j++;
    }
    swap(arr, i, right);
    return i;
}

// 获取数组中第k小的元素下标
int kthSmallest(int arr[], int n, int k) {
    return arr[BFPRT(arr, 0, n - 1, k - 1)];
}