求解中位数的c语言算法,BFPRT 算法（TOP-K 问题）

BFPRT算法是一种解决Top-K问题的算法，其中K为要找的第K大的元素。该算法的时间复杂度为O(n)。

BFPRT算法的基本思想是通过划分算法来找到中位数，然后根据中位数将数组分成两部分，只需要在一部分中查找Top-K，另一部分不用查找。

以下是BFPRT算法的c语言实现：

#include <stdio.h>
#include <stdlib.h>

#define SWAP(a, b) {int temp = a; a = b; b = temp;}

// 求中位数
int median(int arr[], int left, int right) {
    int center = (left + right) / 2;
    if (arr[left] > arr[center]) SWAP(arr[left], arr[center])
    if (arr[left] > arr[right]) SWAP(arr[left], arr[right])
    if (arr[center] > arr[right]) SWAP(arr[center], arr[right])
    SWAP(arr[center], arr[right - 1])
    return arr[right - 1];
}

// 划分函数
int partition(int arr[], int left, int right, int pivot) {
    int i, j;
    for (i = left, j = right - 2;;) {
        while (arr[++i] < pivot);
        while (arr[--j] > pivot);
        if (i < j) SWAP(arr[i], arr[j])
        else break;
    }
    SWAP(arr[i], arr[right - 1])
    return i;
}

// BFPRT算法
int bfprt(int arr[], int left, int right, int k) {
    if (left + 1 == right) return arr[left];
    int pivot = median(arr, left, right);
    int mid = partition(arr, left, right, pivot);
    int num = mid - left + 1;
    if (k == num) return arr[mid];
    else if (k < num) return bfprt(arr, left, mid, k);
    else return bfprt(arr, mid + 1, right, k - num);
}

int main() {
    int arr[] = {3, 4, 2, 1, 5, 6, 8, 7, 9};
    int len = sizeof(arr) / sizeof(int);
    int k = 5;
    int kth = bfprt(arr, 0, len, k);
    printf("The %dth number is: %d\n", k, kth);
    return 0;
}

该算法的核心是BFPRT划分算法，该算法是一个递归算法，每次递归的时间复杂度为O(n)，因此总的时间复杂度为O(nlogn)。