BFPRT算法是解决从n个数中选择第k大或第k小的数这个经典问题的著名算法，但很多人并不了解其细节。本文将首先介绍求解这个第k小数字问题的几个思路，然后重点介绍在最坏情况下复杂度仍然为O(n)的BFPRT算法。 部分的快速排序（快速选择算法），每次划分之后判断第k个数在左右哪个部分，然后递归对应的部分，平均时间复杂度为O(n)。但最坏情况下复杂度为O(n^2)。 BFPRT算法，修改快速选择算法的主元选取规则，使用中位数的中位数的作为主元，最坏情况下时间复杂度为O(n)。 但是两者在最坏情况下的时间复杂度均为O(n^2)，出现在每次划分之后左右总有一边为空的情况下。为了避免这个问题，需要谨慎地选取划分的主元，一般的方法有： 固定选择首元素或尾元素作为主元。 随机选择一个元素作为主元。 为了方便，这里把前面的代码也放在这里。 int partition(int a[], int l, int r) //对数组a下标从l到r的元素进行划分 { //随机选取一个数作为划分的基数 int rd = l + rand() % (r-l+1); swap(a[rd], a[r]); int j = l - 1; //左边数字最右的下标 for (int i = l; i < r; i++) if (a[i] <= a[r]) swap(a[++j], a[i]); swap(a[++j], a[r]); return j; } int NthElement(int a[], int l, int r, int id) //求数组a下标l到r中的第id个数 { if (l == r) return a[l]; //只有一个数 int m = partition(a, l, r), cur = m - l + 1; if (id == cur) return a[m]; //刚好是第id个数 else if(id < cur) return NthElement(a, l, m-1, id);//第id个数在左边 else return(a, m+1, r, id-cur);
Read full article from BFPRT算法 » NoAlGo博客
