BFPRT算法（TOPK問題的O(n)時間複雜度方法）

        TOPK問題，在一堆無序數組中找到最大或者最小的K個數。一般使用快速排序，然後查找K個數字，時間複雜度最好在nlog，最壞情況O(n2)。而BFPRT算法，又叫做中位數的中位數算法，由五個發明人的名字縮寫構成，其最壞的時間複雜度O(n)。

        證明方法參考：這篇文章

        快速排序因為基準點預設選取第一個位置，是以在一定情況下會退化為O(n^2)。bfprt通過修改基準點選擇方法，以達到穩定的時間複雜度。

        代碼參考上文連結。

#include<iostream>
#include<algorithm>
using namespace std;

/* 對arry[left]...arry[right]進行插入排序（升序） */
void InsertSort(int arry[], int left, int right)
{
    for (int i = left + 1; i <= right; i++)
    {
        int j = i;
        while (j - 1 >= left&&arry[j] < arry[j - 1])  //j - 1 >= left避免數組越界
        {
            swap(arry[j - 1], arry[j]);
            j--;
        }
    }
}

/* 找到中位數的中位數，傳回其下标 */
int FindMidMid(int arry[], int left, int right)
{
    if (right - left + 1 <= 5)  //如果不足5個
    {
        InsertSort(arry, left, right);
        return (left + right) >> 1;
    }

    int j = left - 1;
    for (int i = left; i <= right; i += 5)  //5個一組插入排序取中位數，并統一放在左側
    {
        InsertSort(arry, i, i + 4);
        swap(arry[++j], arry[i + 2]);
    }

    return FindMidMid(arry, left, j);  //直至僅出現一個的中位數
}

/* 劃分，pivot_index為劃分基準的下标 */
int Partion(int arry[], int left, int right, int pivot_index)
{
    swap(arry[pivot_index], arry[right]);  //把基準放置右側末尾

    int j = left;
    for (int i = left; i < right; i++)  //比基準小的都放在左側
    {
        if (arry[i] <= arry[right])
            swap(arry[j++], arry[i]);
    }

    swap(arry[j], arry[right]);  //最後把基準換回來
    return j;
}

void BFPRT(int arry[], int left, int right, int k)
{
    if (left == right)
        return;
    int pivot_index = FindMidMid(arry, left, right);      //找到中位數的中位數的下标，其值作為基準
    int index = Partion(arry, left, right, pivot_index);  //以基準劃分
    int num = index - left + 1;
    if (num == k)
        return;
    else if (num > k)
        BFPRT(arry, left, index - 1, k);
    else
        BFPRT(arry, index + 1, right, k - num);
}

int main()
{
    int k = 1;
    int arry[10] = { 1,1,2,3,1,5,-1,7,8,-10 };
    BFPRT(arry, 0, 9, k);

    for (int i = 0; i < 10; i++)
        cout << arry[i] << " ";
    cout << endl;
    return 0;
}