特定分治查找第K小 BFPRT算法

 1 /* 区间快排，各组返回中位数下标 */
 2 int GetPivotIndex(int left, int right) {
 3     sort(Array + left, Array + right + 1)
 4     return (right - left) >> 1) + left
 5 }
 6 
 7 /* 返回中位数的中位数下标 */
 8 int GetPivotOfPivotIndex(int left, int right) {
 9     if right - left < 5
10         return GetPivotIndex(left, right)
11     pos <- left - 1
12     for i <- left  and i + 4 <= right  and i += 5
13         index <- GetPivotIndex(i, i + 4)  //找到五个元素的中位数的下标
14         swap(Array[++pos], Array[index])   //依次放在左侧
15         
16     return KthNumber(left, pos, ((pos - left + 1) >> 1) + 1)
17 }
18 
19 /* 利用中位数的中位数的下标进行划分，返回分界线下标 */
20 int Partition(int left, int right, int pivot_index) {
21     swap(Array[pivot_index], Array[right])  //把基准放置于末尾
22     divide_index <- left  //跟踪划分的分界线
23     for i <- left to right
24         if Array[i] < Array[right]
25             swap(Array[divide_index++], Array[i]) //比基准小的都放在左侧
26     }
27     swap(Array[divide_index], Array[right]);  //最后把基准换回来
28     return divide_index
29 }
30 
31 int KthNumber(int left, int right, const int& k) {
32     pivot_index <- GetPivotOfPivotIndex(left, right)   //得到中位数的中位数下标
33     divide_index <- Partition(left, right, pivot_index)  //进行划分，返回划分边界
34     num <- divide_index - left + 1
35     if (num == k)//如果分界线刚好在k位置，直接返回该下标
36         return divide_index
37     else if (num > k)//如果分界线在k左边，递归左区间
38         return KthNumber(left, divide_index - 1, k)
39     else //如果分界线在k右边，递归右区间，并修改k值
40         return KthNumber(divide_index + 1, right, k - num)
41 }