zhe.ink该算法由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
苏公网安备
32050902101537号