在 n 个数当中找第k小元素 (BFPRT算法，最坏情况为线性时间的选择问题)

题目描述

问题描述：

在 n 个数当中找第k小元素。

输入：

第一行输入n的值，第二行输入n个数，第三行输入k的值。

输出：

n 个数中的第k小元素。

要求：

你的算法最坏情况下应该在线性时间内完成。

示例1 ：

输入:

8 1 3 6 9

输出: 6

示例 2：

输入:

72 6 57 88 60 42 83 73 48 85

输出: 60

思路分析

对于常规解法，我们随机在数组中选择一个数作为划分值（pivot），然后进行快排的partation过程（将小于pivot的数放到数组左边，大于pivot的数放到数组右边），划分完之后pivot的下标为i，然后判断k与等于i的相对关系，如果k正好在等于i，那么数组第k小的数就是pivot，如果k小于i，那么我们递归对左边再进行上述过程，如果k大于i，那我们递归对右边再进行上述过程。常规解法的应用及代码实现见这篇文章。

对于最好的情况：每次所选的pivot划分之后正好在数组的正中间，那么递归方程为T(n) = T(n/2) + n，解得T(n) = O(n)，所以此时此算法是O(n)线性复杂度的。

对于最坏情况：每次所选的pivot划分之后都好在数组最边上，那么时间复杂度为O(n²)。

BFPRT算法就是在这个pivot上做文章，BFPRT算法能够保证每次所选的pivot划分之后在数组的中间位置，那么时间复杂度就是O(n)。

BFPRT算法流程

这题规定了要在线性时间内完成第k小元素的选择，在算法导论这本书里面的第九章有讲解过这种问题，算法的基本思想是修改快速排序算法中的主元选取方法，降低算法在最坏情况下的时间复杂度。

　　下述步骤来自《算法导论(第3版)》第9.3节。

在快速排序中，我们始终选择第一个元素或者最后一个元素作为pivot，而在此算法中，每次选择五分中位数的中位数作为pivot，这样做的目的就是使得划分比较合理，从而避免了最坏情况的发生。通过执行下列步骤，算法Select可以确定一个有个不同元素的输入数组中第i小的元素：

(1) 将n个元素划为组，每组5个，至多只有一组由剩下的n mod 5个元素组成。

(2) 寻找这个组中每一个组的中位数，这个过程可以用插入排序，然后确定每组有序元素的中位数。

(3) 对第2步中找出的个中位数，重复步骤1和步骤2，递归下去，直到剩下一个数字。

(4) 最终剩下的数字即为主元pivot，用快速排序的划分思想，把小于pivot的数全放左边，大于它的数全放右边。跟快速排序不同的是，这里只是划分，并没有排序。

(5) 判断pivot的位置与k的大小，有选择的对左边或右边递归。

  1 #include <iostream>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #include <time.h>
  5 #include <algorithm>
  6  
  7 using namespace std;
  8  
  9 //插入排序
 10 void InsertSort(int a[], int l, int r)
 11 {
 12     for(int i = l + 1; i <= r; i++)
 13     {
 14         if(a[i - 1] > a[i])
 15         {
 16             int t = a[i];
 17             int j = i;
 18             while(j > l && a[j - 1] > t)
 19             {
 20                 a[j] = a[j - 1];
 21                 j--;
 22             }
 23             a[j] = t;
 24         }
 25 }
 26 }
 27  
 28 //寻找中位数的中位数
 29 int FindMid(int a[], int l, int r)
 30 {
 31     if(l == r) return l;
 32     int i = 0;
 33     int n = 0;
 34     for(i = l; i < r - 5; i += 5)
 35     {
 36         InsertSort(a, i, i + 4);
 37         n = i - l;
 38         //插入排序之后，a[i+2]就是a[i,...,i+5]的中位数
 39         //把中位数都放到前面 
 40         swap(a[l + n / 5], a[i + 2]);
 41     }
 42  
 43     //处理剩余元素
 44     int num = r - i + 1;
 45     if(num > 0)
 46     {
 47         InsertSort(a, i, i + num - 1);
 48         n = i - l;
 49         swap(a[l + n / 5], a[i + num / 2]);
 50     }
 51     n /= 5;
 52     if(n == l) 
 53         return l;
 54     
 55     //前n个数就是上述找出来的每一组的中位数 
 56     return FindMid(a, l, l + n);
 57 }
 58  
 59 //进行划分过程，就是一趟快速排序的过程，返回划分后的基准数的下标i 
 60 int Partition(int a[], int l, int r, int p)
 61 {
 62     swap(a[p], a[l]);
 63     int i = l;
 64     int j = r;
 65     int pivot = a[l];
 66     while(i < j)
 67     {
 68         while(a[j] >= pivot && i < j)
 69             j--;
 70         while(a[i] <= pivot && i < j)
 71             i++;
 72         swap(a[j], a[i]);
 73     }
 74     swap(a[l], a[i]);
 75     
 76     return i;
 77 }
 78  
 79 int Select(int a[], int l, int r, int k)
 80 {
 81     int p = FindMid(a, l, r);       //寻找中位数的中位数
 82     int i = Partition(a, l, r, p);  //划分之后的下标 
 83  
 84     int m = i - l + 1;
 85     if(m == k) 
 86         return a[i];
 87     if(m > k)  
 88         return Select(a, l, i - 1, k);
 89         
 90     return Select(a, i + 1, r, k - m);
 91 }
 92  
 93 int main()
 94 {
 95     int n, k;
 96     scanf("%d", &n);
 97     int *a = new int[n];
 98     for(int i = 0; i < n; i++)
 99         scanf("%d", &a[i]);
100     scanf("%d", &k);
101     printf("%d", Select(a, 0, n - 1, k));
102     
103     delete[] a;
104     return 0;
105 }

复杂度分析

思考与引申

快速排序的 Partition 划分思想可以用于计算某个位置的数值等问题，可以实现 O(n)复杂度的选择问题，之所以这种选择算法具有线性时间，是因为没有进行排序，并且每次都有选择的只对左右其中的一边进行递归处理，而排序需要进行比较，并且快速排序左右两边都需要进行递归处理，即使是在平均情况下，排序也需要 O(nlogn)的时间复杂度，而这个线性时间的选择算法没有使用排序就解决了选择问题。

优缺点

但缺点也很明显，最主要的就是内存问题，在海量数据的情况下，很有可能没办法一次性将数据全部加载入内存，这个时候这个方法就无法完成使命了。此时可以利用堆来解决，维护一个大小为 K 的小顶堆，依次将数据放入堆中，当堆的大小满了的时候，只需要将堆顶元素与下一个数比较：如果大于堆顶元素，则将当前的堆顶元素抛弃，并将该元素插入堆中。遍历完全部数据，Top K 的元素也自然都在堆里面了。但是使用堆解决这个问题，时间花费为 O(nlogk)。

参考

《算法导论 (第3版)》第9.3节

bfprt算法解析

知乎 - BFPRT算法原理