该算法由Blum、Floyd、Pratt、Rivest、Tarjan在1973年提出，最坏时间复杂度为O(n)，最差的空间复杂度为O(logn)。

在计算机科学中，中位数的中位数是一种近似(中位数)选择算法，通常用于为精确选择算法(主要是快速选择)提供良好的枢轴，该算法选择第k个最小元素。

算法步骤
(1)：将n个元素划分为 ⌊n/5⌋ 个组，每组5个元素，若有剩余，舍去；
(2)：使用排序方法找到 ⌊n/5⌋ 个组中每一组的中位数；
(3)：对于(2)中找到的所有中位数，递归(1)(2)查找中位数的中位数，作为Partition划分过程的主元
(4)：进行Partition划分，即一次快排
(5)：判断主元的位置与k的大小，有选择的对左边或右边递归。

算法应用
BFPRT算法的一个经典应用就是TOP-K问题，即在一组数据中寻找第K大或第K小的元素。
这类问题可以分为对数据完全排序，部分排序和不排序。
完全排序情况下可以使用快速排序等排序方法能达到O(nlogn)的时间复杂度。
部分排序可以使用冒泡排序，选择排序等方法也能达到O(kn)的时间复杂度。
不排序的情况可以使用堆排序的方法，时间复杂度为O(nlogk)。
而BFPRT算法解决这类问题能达到O(n)的时间复杂度！！

这是Go程序的源代码，用于查找第K个最小元素的中位数。

package main

import (
	"fmt"
	"sort"
)

func medianOfMedians(sliceList []int, k, r int) int {

	num := len(sliceList)
	if num < 10 {
		sort.Ints(sliceList)
		return sliceList[k-1]
	}
	med := (num + r - 1) / r

	medians := make([]int, med)

	for i := 0; i < med; i++ {
		v := (i * r) + r
		var arr []int
		if v >= num {
			arr = make([]int, len(sliceList[(i*r):]))
			copy(arr, sliceList[(i*r):])
		} else {
			arr = make([]int, r)
			copy(arr, sliceList[(i*r):v])
		}
		sort.Ints(arr)
		medians[i] = arr[len(arr)/2]
	}
	pivot := medianOfMedians(medians, (len(medians)+1)/2, r)

	var leftSide, rightSide []int

	for i := range sliceList {
		if sliceList[i] < pivot {
			leftSide = append(leftSide, sliceList[i])
		} else if sliceList[i] > pivot {
			rightSide = append(rightSide, sliceList[i])
		}
	}

	switch {
	case k == (len(leftSide) + 1):
		return pivot
	case k <= len(leftSide):
		return medianOfMedians(leftSide, k, r)
	default:
		return medianOfMedians(rightSide, k-len(leftSide)-1, r)
	}
}

func main() {
	intSlice := []int{5, 9, 77, 62, 71, 11, 22, 46, 36, 18, 19, 33, 75, 17, 39, 41, 73, 50, 217, 79, 120}
	sort.Ints(intSlice)

	for _, j := range []int{5, 10, 15, 20} {
		i := medianOfMedians(intSlice, j, 5)
		fmt.Println(j, "smallest element = ", i)
		v := intSlice[j-1]
		fmt.Println("arr[", j-1, "] = ", v)
		if i != v {
			fmt.Println("Oops! Algorithm is wrong")
		}
	}
}

输出：

5 smallest element =  18
arr[ 4 ] =  18
10 smallest element =  39
arr[ 9 ] =  39
15 smallest element =  71
arr[ 14 ] =  71
20 smallest element =  120
arr[ 19 ] =  120